《算法设计与分析》第五六章：回溯法与分支限界法
文章目录
- 回溯法
- 分支限界法
- 一、本章作业
- 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;
}