《算法设计与分析》第五六章：回溯法与分支限界法

文章目录

  • 回溯法
  • 分支限界法
  • 一、本章作业
    • 1.活动安排问题
    • 2.旅行商问题
    • 3.单源最短路径
    • 4.任务分配问题
  • 二、算法积累
    • 1.回溯法求解01背包问题
    • 2.回溯法求解最大团问题
    • 3.回溯法求解n皇后问题
    • 4.回溯法求解地图着色
    • 5.回溯法求解哈密尔顿图
    • 6.回溯法求活动安排
    • 7.分支限界法求01背包问题
    • 8.分支限界法求单源最短路径
    • 9.分支限界法求解八数码问题
    • 10.流水作业调度

回溯法

回溯法类似于枚举(穷举、蛮力)，通过深度优先搜索策略遍
历问题的所有可能解的通路，发现此路不通时，回溯到上一
步继续尝试别的通路。
回溯法适用于查找问题的所有解集或符合某种限制条件的最
佳解集。具体实现时，采用剪枝策略进行搜索范围控制，提
高效率。但其最坏时间复杂度仍然很高。
对于NPC问题来说，回溯法被认为是目前较为有效的方法。
回溯算法的基本步骤：

(1)定义问题的解空间(描述解)：用一个什么样的向量表示
问题的解？该向量中的每个变量如何取值？
(2)确定解空间的结构：子集树? 排列树? 以及每个节点和
边的含义。
(3)确定剪枝函数，以深度优先搜索解空间。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

分支限界法

分支限界法对问题的解空间树进行 广度搜索的过程。其
步骤如下：

（1）生成根节点，进队列；
（2）只要队列不空：

（a）出队一个结点（FIFO或优先队列）作为扩展结点；
（b）产生其所有孩子结点，抛弃那些不可能产生可行解
或最优解的结点，将其余的孩子结点加入活结点表。

应用分支限界法的关键问题，主要包括：

（1）如何确定合适的限界函数，用于剪枝
（2）如何组织待处理活结点表（ FIFO；优先队列）
（3）如何确定最优解中的各个分量(各结点存储；全局变量存储；构建树 )

队列式分支限界法：

（1）按照队列先进先出原则选取下一个结
点为扩展结点。
（2）优先队列式分支限界法：以最小耗费（最大效益）优先的
方式搜索解空间树，即按照优先队列中规定的优先级选取
优先级最高的结点成为当前扩展结点。常用堆（大根堆 /小
根堆)来实现。

一、本章作业

1.活动安排问题

假设有个活动需要使用某一资源，该资源任何时刻只能被一个活动所占用，每个活动i有一个开始时间bi和结束时间ei（bi<ei），且一旦某个活动开始执行，中间不能被打断，直到其执行完毕。如何安排活动，使得能安排尽可能多的活动。

  • 可行性： 在每次递归调用中，首先检查当前活动是否可以选择。这是通过检查当前要选择的活动 A[x[i]] 是否与已经选择的活动时间兼容来完成的。
  • 递归回溯： 如果当前活动不能选择，直接递归到下一个活动；如果可以选择，则选择并递归进入下一个活动。
  • 最优性： 在完成一次完整的活动选择后，检查当前的活动选择方案是否比记录的最优方案更优。如果是，则更新最优解向量 bestx[] 和最大兼容活动数 maxsum。
#include <bits/stdc++.h>using namespace std;const int MAXN = 100;struct Action 
{int b; // 开始时间int e; // 结束时间
};int n = 4;
Action A[] = {{0, 0}, {1, 3}, {2, 5}, {4, 8}, {6, 10}};int x[MAXN]; // 临时解向量
int bestx[MAXN]; // 最优解向量
int laste = 0; // 结束时间
int sum = 0; 
int maxsum = 0;void dfs(int i) 
{if (i > n) {if (sum > maxsum) {maxsum = sum;for (int j = 1; j <= n; j++)bestx[j] = x[j];}} else {// 不选择第i个活动x[i] = 0;dfs(i + 1);// 选择第i个活动if (A[i].b >= laste) {int sum1 = sum;int laste1 = laste;sum++;laste = A[i].e;x[i] = 1;dfs(i + 1);// 回溯sum = sum1;laste = laste1;}}
}void dispasolution() 
{int laste = 0;cout << "最优调度方案:\n";for (int j = 1; j <= n; j++) {if (bestx[j] == 1) {cout << "选取活动" << j << " [" << A[j].b << "," << A[j].e << "]\n";laste = A[j].e; // 更改为当前活动的结束时间}}cout << "兼容活动的个数=" << maxsum << endl;
}int main() 
{for (int i = 1; i <= n; i++) {x[i] = 0;}dfs(1); // 从第1个活动开始搜索dispasolution(); // 输出结果return 0;
}

2.旅行商问题

从某个固定的顶点出发，求解旅行商问题，输出一个最优解（包含路径和总费用）。

  • 用排列树求解
  • backtrack 函数：如果当前已经排列了 n 个节点，并且形成了一个回路且成本小于当前最优解，则更新最优解。否则，遍历剩下的节点，尝试每个节点作为当前节点，并递归求解。
  • 边的存在性检查：在尝试选择一个节点作为下一个节点时，首先检查从当前节点到下一个节点是否有一条边存在，即a[x[t-1]][x[i]]是否为非零。
    如果不存在这条边，则跳过这个选择，避免无效的搜索。
  • 当前成本检查：在选择一个节点作为下一个节点时，检查当前成本加上从当前节点到下一个节点的边的成本是否小于当前已知的最优成本bestc。如果当前成本加上这条边的成本已经超过最优成本，则剪枝，避免进一步的搜索。
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int x[maxn];        // 当前解
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本
int cc = 0;          // 当前成本void backtrack(int t)
{if (t == n + 1)  // 修改判断条件，确保包含所有节点{if (a[x[n]][x[1]] && (cc + a[x[n]][x[1]] < bestc)){for (int j = 1; j <= n; j++)bestx[j] = x[j]; // 最优解bestc = cc + a[x[n]][x[1]];}}else{for (int i = t; i <= n; i++){if (a[x[t-1]][x[i]] && (cc + a[x[t-1]][x[i]] < bestc)){swap(x[t], x[i]);cc += a[x[t-1]][x[t]];backtrack(t + 1);  // 递归cc -= a[x[t-1]][x[t]];  // 回溯swap(x[t], x[i]);}}}
}int main()
{cout << "请输入节点数：";cin >> n;cout << "请输入邻接矩阵：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)x[i] = i;backtrack(2);  // 从第2个节点开始，因为第1个节点是固定的起点if (bestc == INT_MAX)cout << "No Solution!" << endl;else{cout << "最优解的路径为：";for (int i = 1; i <= n; i++)cout << bestx[i] << "-";cout << bestx[1] << endl;cout << "最小成本为：" << bestc << endl;}return 0;
}
  • 分支限界：
#include <bits/stdc++.h>using namespace std;const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本struct Node 
{vector<int> path; // 当前路径int cost; // 当前路径的成本int bound; // 当前节点的下界int level; // 当前节点在搜索树中的层次bool operator<(const Node& other) const {return bound > other.bound; // 优先选择下界值较小的节点}
};// 计算当前节点的下界
int calculateBound(Node node) 
{int cost = node.cost;int bound = cost;bool visited[maxn] = { false };for (int i : node.path) {visited[i] = true;}// 计算还没有访问的节点的最小边for (int i = 1; i <= n; i++) {if (!visited[i]) {int minEdge = INT_MAX;for (int j = 1; j <= n; j++) {if (!visited[j] && a[i][j] < minEdge && a[i][j] > 0) {minEdge = a[i][j];}}bound += minEdge;}}return bound;
}void branchAndBound() 
{priority_queue<Node> pq;Node startNode;startNode.path.push_back(1); // 从第1个节点开始startNode.cost = 0;startNode.bound = calculateBound(startNode);startNode.level = 1;pq.push(startNode);while (!pq.empty()) {Node currentNode = pq.top();pq.pop();if (currentNode.level == n) {if (a[currentNode.path.back()][1] > 0 && (currentNode.cost + a[currentNode.path.back()][1] < bestc)) {bestc = currentNode.cost + a[currentNode.path.back()][1];for (int i = 0; i < n; i++) {bestx[i + 1] = currentNode.path[i];}}} else {for (int i = 2; i <= n; i++) {if (find(currentNode.path.begin(), currentNode.path.end(), i) == currentNode.path.end() && a[currentNode.path.back()][i] > 0) {Node nextNode = currentNode;nextNode.path.push_back(i);nextNode.cost += a[currentNode.path.back()][i];nextNode.bound = calculateBound(nextNode);nextNode.level = currentNode.level + 1;if (nextNode.bound < bestc) {pq.push(nextNode);}}}}}
}int main()
{cout << "请输入节点数：";cin >> n;cout << "请输入邻接矩阵：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];branchAndBound();if (bestc == INT_MAX)cout << "No Solution!" << endl;else{cout << "最优解的路径为：";for (int i = 1; i <= n; i++)cout << bestx[i] << "-";cout << bestx[1] << endl;cout << "最小成本为：" << bestc << endl;}return 0;
}

3.单源最短路径

给定带权有向图G=(V,E)，其中每条边的权是非负实数。给定一个源点，设计算法求解从源点到所有其它各顶点的最短路径，输出到每个点的路径长度及路径。

  • 采用FIFO队列式分支限界法求解
  • 剪枝：只有下一步达到的点，可以更新该点的最短距离才可以向下走，不然就剪枝
    在这里插入图片描述
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点struct NodeType         // 队列结点类型
{int vno;            // 顶点编号int length;         // 路径长度
};void bfs(int v)         // 求解算法
{NodeType e, e1;queue<NodeType> qu;e.vno = v;          // 建立源点结点e（根结点）e.length = 0;       // 源点结点e进队qu.push(e);dist[v] = 0;while(!qu.empty())  // 队列不空循环{e = qu.front(); qu.pop(); // 退出队列结点efor (int j = 0; j < n; j++){if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j]){// 算法：e.vno到顶点j有边并且路径长度更短dist[j] = e.length + a[e.vno][j];previous[j] = e.vno;  // 建立相应顶点j的结点e1e1.vno = j;e1.length = dist[j];  // 结点e1进队qu.push(e1);}}}
}int main()
{// 读入图的顶点个数scanf("%d", &n);// 读入图的邻接矩阵for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){scanf("%d", &a[i][j]);}}// 读入源点scanf("%d", &v);// 初始化dist数组for (int i = 0; i < n; i++){dist[i] = INF;previous[i] = -1;}// 调用bfs算法bfs(v);// 输出最短路径长度for (int i = 0; i < n; i++){if (dist[i] == INF){printf("INF ");}else{printf("%d ", dist[i]);}}printf("\n");// 输出最短路径的前驱节点for (int i = 0; i < n; i++){printf("%d ", previous[i]);}printf("\n");return 0;
}

4.任务分配问题

有n（n≥1）个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。第i个人执行第j个任务的成本是c[i][j]（1≤i，j≤n）。求出总成本最小的分配方案。
在这里插入图片描述

  • 剪枝策略：限界函数 bound(Node& e) 确定了每个节点的下界，以便优先队列能够以最优的方式扩展节点。条件 if (e1.lb <= mincost) 确保只有当新生成的节点有可能带来更优解时，才会继续扩展。如果不可能，就会提前停止无效搜索路径，提高了算法的效率。
#include<bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f
#define MAXN 21struct Node		//队列结点类型
{int no;			    //结点编号int i;			    //表示当前结点属于解空间的第i层（根节点的层次为0），即准备为人员i分配任务int x[MAXN];		//x[i]为人员i分配的任务编号bool worker[MAXN];	//worker[i]=true表示任务i已经分配int cost;			//已经分配任务所需要的成本int lb;			    //下界bool operator<(const Node& s) const	//重载<关系函数>{return lb > s.lb;   }
};
//问题表示
int n = 4;
int c[MAXN][MAXN] = { {0},{0,9,2,7,8},{0,6,4,3,7},{0,5,8,1,8},{0,7,6,9,4} };
//下标0的元素不用
int bestx[MAXN];		//最优分配方案
int mincost = INF;		//最小成本
int total = 1;			//结点个数累计
void bound(Node& e)     //求结点e的限界值
{int minsum = 0;for (int i1 = e.i + 1;i1 <= n;i1++)      //寻找每一行的最小值{                                        //如果找到e这个节点，如果说他选择了某个任务的话，就不能选择那一列的值了int minc = INF;for (int j1 = 1;j1 <= n;j1++)if (e.worker[j1] == false && c[i1][j1] < minc)           minc = c[i1][j1];                       minsum += minc;              }e.lb = e.cost + minsum;          //e.cost代表选择的结点成本+剩下的最小的成本//cout << e.lb << " ";           //可以自行选择输出不输出
}void bfs()
{int j;Node e, e1;                  //e,e1相当于两个儿，帮忙运进队列的priority_queue<Node> qu;                  memset(e.x, 0, sizeof(e.x));               //解向量memset(e.worker, 0, sizeof(e.worker));     //任务是否分配e.i = 0;                      //根节点也是虚结点e.cost = 0;bound(e);e.no = total++;qu.push(e);while (!qu.empty()){e = qu.top();qu.pop();if (e.i == n){if (e.cost < mincost){mincost = e.cost;for (j = 1;j <= n;j++)bestx[j] = e.x[j];}}e1.i = e.i + 1;         //相当于在根节点的情况下开始拓展进行下一个节点for (j = 1;j <= n;j++){if (e.worker[j])     //查看任务j是否分配continue;for(int i1 = 1;i1 <= n;i1++)e1.x[i1] = e.x[i1];         //相当于对e1初始化（1）e1.x[e1.i] = j;             for (int i2 = 1;i2 <= n;i2++)e1.worker[i2] = e.worker[i2];     //相当于对e1初始化（2)  :::(1)(2)就相当于创建了一个新的结点并且对他初始化e1.worker[j] = true;           //这个代表的是它的第几个任务被选择e1.cost = e.cost + c[e1.i][j];bound(e1);e1.no = total++;if (e1.lb <= mincost)     //剪枝qu.push(e1);}}
}
int main()
{bfs();cout << "最优方案：" << endl;for (int k = 1;k <= n;k++){cout << "第" << k << "个人员分配第" << bestx[k] << "个任务" << endl;}cout << "总成本" << mincost;return 0;
}

二、算法积累

1.回溯法求解01背包问题

在这里插入图片描述

  • 运用子集树进行求解
    在这里插入图片描述
  • 两个限制条件：
  • 超过最大重量：
    在这里插入图片描述
  • 不能满足最优解，即已经小于当前得出的最大价值
    在这里插入图片描述
#include <bits/stdc++.h>using namespace std;const int MMM = 1e5 + 20;
int n;
int c;
int w[MMM],v[MMM];
int x[MMM],op[MMM];
int maxv;void dfs(int i, int tw, int tv, int rv, int op[])
{int j;if(i>n){if(tw <= c && tv > maxv){maxv = tv;for(j = 1; j <= n; j ++ )x[j] = op[j];}}else{if(tw + w[i] <= c){op[i] = 1;dfs(i + 1, tw + w[i], tv + v[i], rv - v[i], op);}if(tv + rv - v[i] > maxv){op[i] = 0;dfs(i + 1, tw, tv, rv-v[i], op);}}
}int main()
{cout << "输入物品数和限重："<<endl;cin >> n >> c;cout << "输入每个物品的重量和价值"<<endl;int rv = 0;for(int i = 1; i <= n; i ++ ){cin >> w[i] >> v[i];rv += v[i];}dfs(0, 0, 0,rv,op);for(int i = 1; i <= n; i ++ ){cout << x[i] << ' ';}
}

2.回溯法求解最大团问题

在这里插入图片描述

  • 用子集树：
    在这里插入图片描述
  • 剪枝：
    在这里插入图片描述
#include <bits/stdc++.h>using namespace std;#define MAXN 1000int n;
bool graph[MAXN][MAXN];
bool cand[MAXN]; // 候选解
bool best[MAXN]; // 当前最优解
int maxsize; // 当前最优解大小// 检查是否满足约束条件
bool check(int i) 
{for (int j = 0; j < n; j++) {if (cand[j] && !graph[i][j]) return false; // 如果候选解中有与i不相邻的顶点，则返回false}return true; // 否则返回true
}// 回溯法求解最大团
void backtrack(int i, int size) 
{// 如果考虑完所有顶点if (i >= n) {if (size > maxsize) {maxsize = size; // 更新当前最优解大小for (int j = 0; j < n; j++) {best[j] = cand[j]; // 更新当前最优解}}} else {// 如果满足约束条件if (check(i)) {cand[i] = true; // 将i加入候选解backtrack(i + 1, size + 1); // 递归考虑下一个顶点}// 如果满足限界条件if (n - i + size > maxsize) {cand[i] = false; // 不将i加入候选解backtrack(i + 1, size); // 递归考虑下一个顶点}}
}void output() 
{printf("给定无向图中最大团中定点的个数为：%d\n", maxsize); // 输出当前最优解大小printf("具体定点为：");for (int i = 0; i < n; i++) {if (best[i]) printf("%d ", i + 1); // 输出当前最优解中的顶点}printf("\n");
}int main() 
{cin >> n;cout << "输入邻接矩阵（如果两个顶点之间有边，则输入1；否则输入0）：" << endl;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int x;scanf("%d", &x);graph[i][j] = x == 1;}}backtrack(0, 0); // 调用回溯法函数求解最大团output(); // 输出结果及其文字说明return 0;
}
//5
//0 1 1 1 1
//1 0 1 0 1
//1 1 0 0 1
//1 0 0 0 1
//1 1 1 1 0

3.回溯法求解n皇后问题

在这里插入图片描述

  • 用m叉树求解：

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  • 用排列数求解：

在这里插入图片描述

#include <bits/stdc++.h>using namespace std;int x[100];        //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n;            //棋盘规格
int sum = 0;bool Place(int t)    //实现限界约束判断
{//检查与之前放置的是否冲突for (int i = 1; i < t;i++)if(abs(i-t)==abs(x[i]-x[t])||x[i]==x[t])return false;return true;
}void Backtrack(int t)
{if(t>n){sum++;for (int i = 1; i <= n;i++)cout << "(" << i << "," << x[i] << ")"<< " ";cout << endl;}else{for (int i = t; i <= n;i++){swap(x[i], x[t]);if(Place(t))Backtrack(t + 1);swap(x[i], x[t]);}}
}
int main()
{cout << "请输入棋盘规格或者皇后数量" << endl;cin >> n;for (int i = 1; i <= n;i++)x[i] = i;Backtrack(1);cout << sum << endl;return 0;
}

4.回溯法求解地图着色

在这里插入图片描述

  • 利用m叉树求解：
    在这里插入图片描述

  • 剪枝：
    在这里插入图片描述

  • isSafe 函数用于检查是否可以为当前节点 node 着色。它检查与当前节点相邻的所有节点，如果任一相邻节点已经着色并且颜色与当前尝试的颜色 c 相同，则返回 false。否则返回 true。

  • graphColoringUtil 是递归函数，用于尝试为每个节点着色。主要逻辑如下：

    • 如果所有节点都已着色（node == SIZE），则返回 true。
    • 否则，尝试为当前节点着色，从颜色 1 到 m（最大颜色数）。
    • 如果可以安全地为当前节点着色，则递归调用自身处理下一个节点。
    • 如果无法为当前节点找到合适的颜色，则回溯，将当前节点颜色重置为 0。
#include <iostream>
#define SIZE 5using namespace std;void inputGraph(int graph[][SIZE])
{int i, j;for (i = 0; i < SIZE; i++){for (j = 0; j < SIZE; j++){cin >> graph[i][j];}}
}bool isSafe(int node, int graph[][SIZE], int color[], int c)
{for (int i = 0; i < SIZE; i++){if (graph[node][i] && c == color[i]){return false;}}return true;
}bool graphColoringUtil(int graph[][SIZE], int m, int color[], int node)
{if (node == SIZE){return true;}for (int c = 1; c <= m; c++){if (isSafe(node, graph, color, c)){color[node] = c;if (graphColoringUtil(graph, m, color, node + 1)){return true;}color[node] = 0; // backtrack}}return false;
}bool graphColoring(int graph[][SIZE], int m, int color[])
{return graphColoringUtil(graph, m, color, 0);
}void output(int color[])
{for (int i = 0; i < SIZE; i++){cout << "第" << i + 1 << "个区域的颜色是" << color[i] << endl;}
}int main()
{int graph[SIZE][SIZE];int color[SIZE];for (int i = 0; i < SIZE; i++){color[i] = 0;}cout << "请输入图的邻接矩阵：" << endl;inputGraph(graph);int m = 4; // 最大颜色数if (graphColoring(graph, m, color)){output(color);}else{cout << "无法使用" << m << "种颜色着色图" << endl;}return 0;
}

5.回溯法求解哈密尔顿图

在这里插入图片描述
在这里插入图片描述

  • 用排列树求解
  • backtrack 函数：如果当前已经排列了 n 个节点，并且形成了一个回路且成本小于当前最优解，则更新最优解。否则，遍历剩下的节点，尝试每个节点作为当前节点，并递归求解。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int x[maxn];        // 当前解
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本
int cc = 0;          // 当前成本void backtrack(int t)
{if (t == n + 1)  // 修改判断条件，确保包含所有节点{if (a[x[n]][x[1]] && (cc + a[x[n]][x[1]] < bestc)){for (int j = 1; j <= n; j++)bestx[j] = x[j]; // 最优解bestc = cc + a[x[n]][x[1]];}}else{for (int i = t; i <= n; i++){if (a[x[t-1]][x[i]] && (cc + a[x[t-1]][x[i]] < bestc)){swap(x[t], x[i]);cc += a[x[t-1]][x[t]];backtrack(t + 1);  // 递归cc -= a[x[t-1]][x[t]];  // 回溯swap(x[t], x[i]);}}}
}int main()
{cout << "请输入节点数：";cin >> n;cout << "请输入邻接矩阵：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)x[i] = i;backtrack(2);  // 从第2个节点开始，因为第1个节点是固定的起点if (bestc == INT_MAX)cout << "No Solution!" << endl;else{cout << "最优解的路径为：";for (int i = 1; i <= n; i++)cout << bestx[i] << "-";cout << bestx[1] << endl;cout << "最小成本为：" << bestc << endl;}return 0;
}

6.回溯法求活动安排

在这里插入图片描述

  • 利用子集树求解：
    在这里插入图片描述
  • 利用排列数求解：
    在这里插入图片描述
  • 排列树求解：
  • 采用回溯法求解，相当于找到S={1，…，n}的某个排列即调度方案，使得其中所有兼容活动个数最多，显然对应的解空间是一个是排列树。直接采用排列树递归框架实现，对于每一种调度方案求出所有兼容活动个数，通过比较求出最多活动个数maxsum，对应的调度方案就是最优调度方案bestx，即为本问题的解。
#include <bits/stdc++.h>using namespace std;const int MAXN = 100;struct Action 
{int b; // 开始时间int e; // 结束时间
};int n = 4;
Action A[] = {{0, 0}, {1, 3}, {2, 5}, {4, 8}, {6, 10}};int x[MAXN]; // 临时解向量
int bestx[MAXN]; // 最优解向量
int laste = 0; // 结束时间
int sum = 0; 
int maxsum = 0;void dfs(int i) 
{if (i > n) {if (sum > maxsum) {maxsum = sum;for (int j = 1; j <= n; j++)bestx[j] = x[j];}} else {for (int j = i; j <= n; j++) {swap(x[i], x[j]);int sum1 = sum;int laste1 = laste;if (A[x[i]].b >= laste) { // 开始时间大于当前结束时间sum++;laste = A[x[i]].e;}dfs(i + 1);// 回溯swap(x[i], x[j]);sum = sum1;laste = laste1;}}
}void dispasolution() 
{int laste = 0;cout << "最优调度方案:\n";for (int j = 1; j <= n; j++) {if (A[bestx[j]].b >= laste) {cout << "选取活动" << bestx[j] << " [" << A[bestx[j]].b << "," << A[bestx[j]].e << "]\n";laste = A[bestx[j]].e; // 更改为当前活动的结束时间}}cout << "兼容活动的个数=" << maxsum << endl;
}int main() 
{for (int i = 1; i <= n; i++) {x[i] = i;}dfs(1); // 从第1个活动开始搜索dispasolution(); // 输出结果return 0;
}

7.分支限界法求01背包问题

在这里插入图片描述

  • 采用队列式分枝限界法求解0/1背包问题的算法
//将物体按单位价值从高到低排序 
#include <stdio.h>
#include <queue>
using namespace std;
#define MAXN 20						//最多可能物品数
//问题表示
//int n=3,C=30;
//int w[]={0,16,15,15};				//重量，下标0不用
//int v[]={0,45,25,25};  			//价值，下标0不用int n=5,C=37;
int w[]={0,8,16,21,17,12};			//重量，下标0不用
int v[]={0,48,14,16,11,7};  		//价值，下标0不用//求解结果表示
int maxv=-9999;						//存放最大价值,初始为最小值
int bestx[MAXN];					//存放最优解,全局变量
int total=1;						//解空间中结点数累计,全局变量
struct NodeType						//队列中的结点类型
{	int no;							//结点编号int t;							//当前结点在搜索空间中的层次int w;							//当前结点的总重量int v;							//当前结点的总价值int x[MAXN];					//当前结点包含的解向量double leftV;			   	    //剩余物品价值上界
};void EnQueue(NodeType e,queue<NodeType> &qu)	//结点e进队qu
{if (e.t==n+1)					//到达叶子结点{			if (e.v>maxv && e.w<=C)			//找到更大价值的解{maxv=e.v;for (int j=1;j<=n;j++)bestx[j]=e.x[j];}}else qu.push(e);			//非叶子结点进队
}
void bfs()							//求0/1背包的最优解
{int j;NodeType e,e1,e2;				//定义3个结点queue<NodeType> qu;				//定义一个队列e.no=total++; e.t=1;							//根结点置初值，其层次计为1e.w=0; e.v=0;	e.leftV=0;for (j=1;j<=n;j++){e.x[j]=0;    //根结点的解向量 e.leftV+=v[j];  //求根结点的上界}		qu.push(e);						//根结点进队while (!qu.empty())				//队不空循环{e=qu.front(); qu.pop();		//出队结点e，对第e.t物品进行决策 //if (e.w+w[e.t+1]<=C )		//装入e.t物品。剪枝：检查左孩子结点 if (e.w+w[e.t]<=C && e.v+e.leftV > maxv ) //剪枝：检查左孩子结点,{e1.no=total++; e1.t=e.t+1;				//建立左孩子结点e1.w=e.w+w[e.t];e1.v=e.v+v[e.t];for (j=1;j<e.t;j++)		//复制解向量e1.x[j]=e.x[j];e1.x[e.t]=1;e1.leftV=e.leftV-v[e.t];			EnQueue(e1,qu);			//左孩子结点进队操作//qu.push(e1);	}if(e.v+e.leftV-v[e.t] > maxv)   //不装入e.t物品，右剪枝 {e2.no=total++;				//建立右孩子结点e2.t=e.t+1;e2.w=e.w; e2.v=e.v;for (j=1;j<e.t;j++)			//复制解向量e2.x[j]=e.x[j];e2.x[e.t]=0;e2.leftV=e.leftV-v[e.t];EnQueue(e2,qu);}}
}
int main()
{bfs();					//调用队列式分枝限界法求0/1背包问题printf("分支限界法FIFO求解0/1背包问题:\n  X=[");	//输出最优解for(int i=1;i<=n;i++)printf("%2d",bestx[i]);		//输出所求X[n]数组printf("]，装入总价值为%d\n",maxv);printf("生成的结点总个数:%d\n",total-1); return 0;
}
  • 采用队列式分枝限界法求解0/1背包问题的算法
//将物体按单位价值从高到低排序 
#include <stdio.h>
#include <queue>
using namespace std;
#define MAXN 20						//最多可能物品数
//问题表示
//int n=3,C=30;
//int w[]={0,16,15,15};				//重量，下标0不用
//int v[]={0,45,25,25};  			//价值，下标0不用int n=5,C=37;
int w[]={0,8,16,21,17,12};			//重量，下标0不用
int v[]={0,48,14,16,11,7};  		//价值，下标0不用//求解结果表示
int maxv=-9999;						//存放最大价值,初始为最小值
int bestx[MAXN];					//存放最优解,全局变量
int total=1;						//解空间中结点数累计,全局变量
struct NodeType						//队列中的结点类型
{	int no;							//结点编号int t;						//当前结点在搜索空间中的层次int w;							//当前结点的总重量int v;							//当前结点的总价值int x[MAXN];					//当前结点包含的解向量double leftV;			   	    //剩余物品价值上界bool operator<(const NodeType &s) const	//重载<关系函数{//return leftV < s.leftV;		//剩余物品价值越大，优先级越高，优先出队//return v < s.v;		        //已选物品价值越大，优先级越高，优先出队return v+leftV < s.v+s.leftV;	//已选物品价值+剩余物品价值越大，优先级越高，优先出队}
};void EnQueue(NodeType e,priority_queue<NodeType> &qu)	//结点e进队qu
{if (e.t==n+1)					//到达叶子结点{   		if (e.v>maxv && e.w<=C)			//找到更大价值的解{maxv=e.v;for (int j=1;j<=n;j++)bestx[j]=e.x[j];}}else qu.push(e);			//非叶子结点进队
}
void bfs()							//求0/1背包的最优解
{int j;NodeType e,e1,e2;				//定义3个结点priority_queue<NodeType> qu;	//定义一个优先级队列e.t=1;							//根结点置初值，其层次计为1e.w=0; e.v=0;e.no=total++; e.leftV=0;for (j=1;j<=n;j++){e.x[j]=0;    //根结点的解向量 e.leftV+=v[j];  //求根结点的上界}					qu.push(e);						//根结点进队while (!qu.empty())				//队不空循环{e=qu.top(); qu.pop();		//出队结点eif (e.w+w[e.t]<=C && e.v+e.leftV > maxv)		//剪枝：检查左孩子结点{e1.no=total++; e1.t=e.t+1;				//建立左孩子结点e1.w=e.w+w[e.t];e1.v=e.v+v[e.t];for (j=1;j<e.t;j++)		//复制解向量e1.x[j]=e.x[j];e1.x[e.t]=1;			e1.leftV=e.leftV-v[e.t];EnQueue(e1,qu);			//左孩子结点进队操作}if(e.v+e.leftV-v[e.t] > maxv)   //右剪枝 {e2.no=total++;				//建立右孩子结点e2.t=e.t+1;e2.w=e.w; e2.v=e.v;for (j=1;j<e.t;j++)			//复制解向量e2.x[j]=e.x[j];e2.x[e.t]=0;			e2.leftV=e.leftV-v[e.t];EnQueue(e2,qu);}}
}
int main()
{bfs();					//调用队列式分枝限界法求0/1背包问题printf("分支限界法优先队列求解0/1背包问题:\n  X=[");	//输出最优解for(int i=1;i<=n;i++)printf("%2d",bestx[i]);		//输出所求X[n]数组printf("]，装入总价值为%d\n",maxv);printf("生成的结点总个数:%d\n",total-1); return 0;
}

8.分支限界法求单源最短路径

在这里插入图片描述

  • 采用FIFO队列式分支限界法求解
    在这里插入图片描述
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点struct NodeType         // 队列结点类型
{int vno;            // 顶点编号int length;         // 路径长度
};void bfs(int v)         // 求解算法
{NodeType e, e1;queue<NodeType> qu;e.vno = v;          // 建立源点结点e（根结点）e.length = 0;       // 源点结点e进队qu.push(e);dist[v] = 0;while(!qu.empty())  // 队列不空循环{e = qu.front(); qu.pop(); // 退出队列结点efor (int j = 0; j < n; j++){if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j]){// 算法：e.vno到顶点j有边并且路径长度更短dist[j] = e.length + a[e.vno][j];previous[j] = e.vno;  // 建立相应顶点j的结点e1e1.vno = j;e1.length = dist[j];  // 结点e1进队qu.push(e1);}}}
}int main()
{// 读入图的顶点个数scanf("%d", &n);// 读入图的邻接矩阵for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){scanf("%d", &a[i][j]);}}// 读入源点scanf("%d", &v);// 初始化dist数组for (int i = 0; i < n; i++){dist[i] = INF;previous[i] = -1;}// 调用bfs算法bfs(v);// 输出最短路径长度for (int i = 0; i < n; i++){if (dist[i] == INF){printf("INF ");}else{printf("%d ", dist[i]);}}printf("\n");// 输出最短路径的前驱节点for (int i = 0; i < n; i++){printf("%d ", previous[i]);}printf("\n");return 0;
}
  • 采用优先队列式分枝限界法求解
    在这里插入图片描述
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点struct NodeType         // 队列结点类型
{int vno;            // 顶点编号int length;         // 路径长度bool operator<(const NodeType& node) const{return length > node.length; // length 越小越优先出队}
};void bfs(int v)         // 求解算法
{NodeType e, e1;priority_queue<NodeType> pqu;    // 定义优先队列e.vno = v;                       // 建立源点结点ee.length = 0;                    // 源点结点e进队pqu.push(e);dist[v] = 0;while(!pqu.empty())              // 队列不空循环{e = pqu.top(); pqu.pop();    // 退出队列结点efor (int j = 0; j < n; j++){if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j]){// 算法：e.vno到顶点j有边且路径长度更短dist[j] = e.length + a[e.vno][j];previous[j] = e.vno; // 建立相应顶点j的结点e1e1.vno = j;e1.length = dist[j]; // 结点e1进队pqu.push(e1);}}}
}int main()
{// 读入图的顶点个数scanf("%d", &n);// 读入图的邻接矩阵for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){scanf("%d", &a[i][j]);}}// 读入源点scanf("%d", &v);// 初始化dist数组for (int i = 0; i < n; i++){dist[i] = INF;previous[i] = -1;}// 调用bfs算法bfs(v);// 输出最短路径长度for (int i = 0; i < n; i++){if (dist[i] == INF){printf("INF ");}else{printf("%d ", dist[i]);}}printf("\n");// 输出最短路径的前驱节点for (int i = 0; i < n; i++){printf("%d ", previous[i]);}printf("\n");return 0;
}

9.分支限界法求解八数码问题

在这里插入图片描述

  • 剪枝：
    在这里插入图片描述
    在这里插入图片描述
#include<bits/stdc++.h>using namespace std;struct state
{int a[3][3];int zx,zy;int integer;//map->9位数int useful;//若0位置越界或节点重复，则为无效节点 
};state start;
queue<state> q;
map<int,int> used;
map<int,int> step;int walk[4][2]=
{0,-1,//left+1,0,//down0,+1,//right-1,0//up
};int bfs();
int setinteger(state n);
state move(state now,int i);void init()
{for(int i=0;i<3;i++)for(int j=0;j<3;j++){cin>>start.a[i][j];if(start.a[i][j]==0){start.zx=i;start.zy=j;}}start.integer=setinteger(start);used[start.integer]=1;step[start.integer]=0;q.push(start);
}int setinteger(state n)
{n.integer=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++){n.integer*=10;n.integer+=n.a[i][j];}
//	cout<<n.integer<<endl;return n.integer;
}int bfs()
{state now,next;while(!q.empty()){now=q.front();q.pop();for(int i=0;i<4;i++){next=move(now,i);if(next.useful){if(next.integer==123456780)return step[next.integer];elseq.push(next);}}}return -1;
}state move(state now,int i)
{int newx,newy;state next;next.useful=0;for(int j=0;j<3;j++)for(int k=0;k<3;k++){next.a[j][k]=now.a[j][k];
//			cout<<next.a[j][k]<<endl;}	newx=now.zx+walk[i][0];newy=now.zy+walk[i][1];
//	cout<<newx<<newy<<endl;if(newx>=0 && newx<3 && newy>=0 && newy<3){swap(next.a[now.zx][now.zy],next.a[newx][newy]);next.zx=newx;next.zy=newy;next.integer=setinteger(next);if(!used.count(next.integer)){used[next.integer]=1;step[next.integer]=step[now.integer]+1;next.useful=1;}}
//	cout<<next.integer<<endl;return next;
}int main()
{init();cout<<bfs()<<endl;return 0;
}

10.流水作业调度

在这里插入图片描述

  • 回溯法：
#include <bits/stdc++.h>using namespace std;const int MAX = 5; // 假设最大作业数为5int n = 4; // 作业数
int a[MAX] = {0, 5, 12, 4, 8}; // M1上的执行时间, 下标0不用
int b[MAX] = {0, 6, 2, 14, 7}; // M2上的执行时间, 下标0不用
int f1 = 0, f2[MAX + 1] = {0}; // 初始执行时间和f2数组初始化为0
int x[MAX] = {1, 2, 3, 4}; // 作业序列，假设初始顺序为1, 2, 3, 4
int bestf = INT_MAX; // 最优解的f2[n]值
int bestX[MAX] = {0}; // 最优解的作业序列
int leftT = 0; // 剩余作业在M2上的总时间void dfs(int i) 
{if (i > n) {if (f2[n] < bestf) {bestf = f2[n]; // 找到更优解for (int j = 1; j <= n; j++) {bestX[j] = x[j]; // 复制解向量}}} else {for (int j = i; j <= n; j++) {swap(x[i], x[j]);f1 += a[x[i]]; // 选择作业x[i]，在M1上执行完的时间f2[i] = max(f1, f2[i - 1]) + b[x[i]];leftT -= b[x[i]]; // 更新剩余作业时间if (f2[i] + leftT < bestf) // 剪枝{dfs(i + 1);}f1 -= a[x[i]]; // 回溯leftT += b[x[i]]; // 回溯更新剩余作业时间swap(x[i], x[j]);}}
}int main() 
{for (int i = 1; i <= n; i++) {leftT += b[i]; // 计算所有作业在M2上的总时间}dfs(1);cout << "最优解的M2完成时间为: " << bestf << endl;cout << "最优解的作业序列为: ";for (int i = 1; i <= n; i++) {cout << bestX[i] << " ";}cout << endl;return 0;
}
  • 分支限界法：
#include <bits/stdc++.h>using namespace std;const int MAX = 5; // 假设最大作业数为5struct NodeType 
{int no; // 结点编号int x[MAX + 1]; // x[i]表示第i步分配作业编号int y[MAX + 1]; // y[i]=1表示编号为i的作业已经分配int i; // 步骤编号int f1; // 已经分配作业在M1的执行时间int f2; // 已经分配作业在M2的执行时间int lb; // 下界bool operator<(const NodeType &s) const {return lb > s.lb; // lb越小越优先出队}
};int n = 4; // 作业数
int a[MAX] = {0, 5, 12, 4, 8}; // M1上的执行时间, 下标0不用
int b[MAX] = {0, 6, 2, 14, 7}; // M2上的执行时间, 下标0不用
int bestf = INT_MAX; // 最优解的f2[n]值
int bestX[MAX + 1] = {0}; // 最优解的作业序列void bound(NodeType &e) // 求结点e的限界值
{int sum = 0;for (int i = 1; i <= n; i++) // 仅累计还没有分配的作业的b时间if (e.y[i] == 0) sum += b[i];e.lb = e.f2 + sum;
}void dfs(int i)
{priority_queue<NodeType> pq;NodeType u, v;v.i = 0; v.f1 = v.f2 = 0;for (int j = 1; j <= n; j++) {v.y[j] = 0;}bound(v);pq.push(v);while (!pq.empty()) {v = pq.top(); pq.pop();if (v.i == n) {if (v.f2 < bestf) {bestf = v.f2;for (int j = 1; j <= n; j++) {bestX[j] = v.x[j];}}} else {v.i++;for (int j = 1; j <= n; j++) {if (v.y[j] == 0) {u = v;u.x[u.i] = j;u.y[j] = 1;u.f1 += a[j];u.f2 = max(u.f1, u.f2) + b[j];bound(u);if (u.lb < bestf) {pq.push(u);}}}}}
}int main() 
{dfs(1);cout << "最优解的M2完成时间为: " << bestf << endl;cout << "最优解的作业序列为: ";for (int i = 1; i <= n; i++) {cout << bestX[i] << " ";}cout << endl;return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/354078.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

DIVE INTO DEEP LEARNING 36-49

DIVE INTO DEEP LEARNING 36-49

文章目录 36. Data augmentation36.1 Training with enhanced data36.2 Enhancement measures36.3 Data augmentation summary 37. Fine tuning37.1 Fine tuning Introduce37.2 Fine tuning Step37.3 Fine tuning summary 38. Object detection38.1 Object detection38.2 Edge …
阅读更多...
SpringBoot+Vue实现Excel文档导入和导出

SpringBoot+Vue实现Excel文档导入和导出

1.准备工作 1.1.前端程序 在前端首先加上批量导出的按钮&#xff0c;如下 <el-button size"small" type"warning" plain click"exportData"> 批量导出 </el-button> 在添加了点击事件之后&#xff0c;在methods中要与之对应的添加上…
阅读更多...
汽车IVI中控开发入门及进阶（二十七）：车载摄像头vehicle camera

汽车IVI中控开发入门及进阶（二十七）：车载摄像头vehicle camera

前言： 在车载IVI、智能座舱系统中，有一个重要的应用场景就是视频。视频应用又可分为三种，一种是直接解码U盘、SD卡里面的视频文件进行播放，一种是手机投屏，就是把手机投屏软件已视频方式投屏到显示屏上显示，另外一种就是对视频采集设备（主要就是摄像头Camera）的视频源…
阅读更多...
3ds Max软件下载安装：3D建模软件 轻松开启你的建模之旅！

3ds Max软件下载安装：3D建模软件 轻松开启你的建模之旅！

3ds Max&#xff0c;在建模过程中&#xff0c;网格建模和NURBS建模两大技术发挥着不可或缺的作用。网格建模允许用户通过顶点、边和面等元素的调整&#xff0c;精确地塑造出模型的形态&#xff1b;而NURBS建模则以其优秀的曲线和曲面处理能力&#xff0c;为设计师们提供了更为平…
阅读更多...
二分+ST表+递推，Cf 1237D - Balanced Playlist

二分+ST表+递推，Cf 1237D - Balanced Playlist

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1237D - Codeforces 二、解题报告 1、思路分析 case3提示我们一件事情&#xff1a;如果存在某个位置永远不停止&#xff0c;那么所有位置都满足永远不停止 很容易证明 随着下标右移&#xff0c…
阅读更多...
【Ruby基础01】windows和termux中搭建Ruby开发环境

【Ruby基础01】windows和termux中搭建Ruby开发环境

windows下环境搭建 railsinstaller官方git地址 按照文档安装git、nodejs、yarn&#xff0c;安装教程百度一下。railsinstall可以从release页面下载最新版本4.1.0。 安装完成如下 安装RubyMine 下载RubyMine RubyMine下载地址 安装激活 下载文件&#xff0c;按照里面的流程…
阅读更多...
Houdini到UE地形流程

Houdini到UE地形流程

目录 Houidni地形制作 UE地形设置 Houdini engine插件安装 B站参考视频 Houidni地形制作 使用Terrain的HeightField相关节点制作地形&#xff1b;设置地形相关的材质层&#xff08;如rock、soil、grass等&#xff09;&#xff0c;注意材质的重叠&#xff1b; //detail层级&…
阅读更多...
Python网络爬虫4-实战爬取pdf

Python网络爬虫4-实战爬取pdf

1.需求背景 爬取松产品中心网站下的家电说明书。这里以冰箱为例&#xff1a;松下电器-冰箱网址 网站分析&#xff1a; 第一步&#xff1a; 点击一个具体的冰箱型号&#xff0c;点击了解更多&#xff0c;会打开此型号电器的详情页面。 第二步&#xff1a;在新打开的详情页面中…
阅读更多...
Linux top 命令使用教程

Linux top 命令使用教程

转载请标明出处&#xff1a;https://blog.csdn.net/donkor_/article/details/139775547 文章目录 一、top 是什么二、top的基础语法三、top输出信息解读 一、top 是什么 Linux top 是一个在Linux和其他类 Unix 系统上常用的实时系统监控工具。它提供了一个动态的、交互式的实时…
阅读更多...
关于Mysql 中 Row size too large (＞ 8126) 错误的解决和理解

关于Mysql 中 Row size too large (＞ 8126) 错误的解决和理解

提示&#xff1a;啰嗦一嘴 &#xff0c;数据库的任何操作和验证前&#xff0c;一定要记得先备份&#xff01;&#xff01;&#xff01;不会有错&#xff1b; 文章目录 问题发现一、问题导致的可能原因1、页大小2、行格式2.1 compact格式2.2 Redundant格式2.3 Dynamic格式2.4 Co…
阅读更多...
Redis的安装及详解

Redis的安装及详解

1.Redis介绍&#xff1f; 1.1 Redis是什么&#xff1f; Redis&#xff08;Remote Dictionary Server,远程字典服务器&#xff09;是一个开源免费的&#xff0c;用C语言编写的一个高性能的分布式内存数据库&#xff0c;基于内存运行并支持持久化的NoSQL数据库。是当前最热门的…
阅读更多...
Apache Doris 基础 -- 部分数据类型及操作

Apache Doris 基础 -- 部分数据类型及操作

您还可以使用SHOW DATA TYPES;查看Doris支持的所有数据类型。 部分类型如下&#xff1a; Type nameNumber of bytesDescriptionSTRING/可变长度字符串&#xff0c;默认支持1048576字节(1Mb)&#xff0c;最大精度限制为2147483643字节(2gb)。大小可以通过BE配置string_type_le…
阅读更多...
【Perl】与【Excel】

【Perl】与【Excel】

引言 perl脚本语言对于文本的处理、转换很强大。对于一些信息量庞大的文本文件&#xff0c;看起来不直观&#xff0c;可以将信息提取至excel表格中&#xff0c;增加数据分析的可视化。perl语言的cpan提供了大量模块。对于excel文件的操作主要用到模块&#xff1a; Spreadshee…
阅读更多...
Elasticsearch过滤器（Filter）：原理及使用

Elasticsearch过滤器（Filter）：原理及使用

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…
阅读更多...
【数据库编程-SQLite3（一）】sqlite3数据库在Windows下的配置及测试

【数据库编程-SQLite3（一）】sqlite3数据库在Windows下的配置及测试

学习分析 1、资源准备2、环境配置2.1、将资源包下载解压缩保存。2.2、在QT中创建工程,配置环境 3、测试配置3.1、 sqlite3_open函数3.2、sqlite3_close函数3.3、代码测试 1、资源准备 资源包 2、环境配置 2.1、将资源包下载解压缩保存。 解压缩得到以下文件 2.2、在QT中创建…
阅读更多...
第十五章 观察者模式

第十五章 观察者模式

目录 1 观察者模式介绍 2 观察者模式原理 3 观察者模式实现 4 观察者模式应用实例 5 观察者模式总结 1 观察者模式介绍 观察者模式的应用场景非常广泛&#xff0c;小到代码层面的解耦&#xff0c;大到架构层面的系统解耦&#xff0c;再或者 一些产品的设计思路&#xff0c…
阅读更多...
图卷积网络（Graph Convolutional Network, GCN）

图卷积网络（Graph Convolutional Network, GCN）

图卷积网络&#xff08;Graph Convolutional Network, GCN&#xff09;是一种用于处理图结构数据的深度学习模型。GCN编码器的核心思想是通过邻接节点的信息聚合来更新节点表示。 图的表示 一个图 G通常表示为 G(V,E)&#xff0c;其中&#xff1a; V 是节点集合&#xff0c;…
阅读更多...
【perl】环境搭建

【perl】环境搭建

1、Vscode Strawberry Perl 此过程与tcl环境搭建很类似&#xff0c;请参考我的这篇文章&#xff1a; 【vscode】 与 【tclsh】 联合搭建tcl开发环境_tclsh软件-CSDN博客 perl语言的解释器可以选择&#xff0c;strawberry perl。Strawberry Perl for Windows - Releases。 …
阅读更多...
对于补码的个人理解

对于补码的个人理解

1. 十进制的取模计算 现在我想要使另一个数加上2后用8取模后也等于1&#xff0c;这个数可以是哪些&#xff1f; 这个问题比较简单&#xff0c;只需要-1加上8的倍数即可 例如&#xff1a; 如果我们想要得到距离-1这个负数最近的一个正数7&#xff0c;直接使用-18即可。反过来想…
阅读更多...
C# WinForm —— 36 布局控件 GroupBox 和 Panel

C# WinForm —— 36 布局控件 GroupBox 和 Panel

1. 简介 两个可以盛放其他控件的容器&#xff0c;可以用于把不同的控件分组&#xff0c;一般不会注册事件 GroupBox&#xff1a;为其他控件提供可识别的分组。可通过Text属性设置标题&#xff1b;有边框&#xff1b;没有滚动条&#xff0c;一般用于按功能分组 Panel&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发