算法笔记之回溯法（3）
最优加工顺序
问题描述
现在有3个机器零件{J1,J2,J3}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？
问题分析
我们通过分析可以发现，第一台机器可以连续加工，而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。
实际上就是找到n个机器零件的一个排列，使总的加工时间最短。
算法设计
- 定义问题的解空间。解的形式为n元组：{x1,x2,...,xi,...,xn}，分量xi表示第i个加工的零件号，n个零件组成的集合为S={1,2,...,n}，xi取值为S-{x1,x2,...,xi-1}。
- 解空间的组织形式为一颗排列数，深度为n。
- 搜索解空间。
- 约束条件：无约束条件。
- 限界条件：用f2表示当前已完成的零件在第二台机器加工结束所用的时间，用bestf表示当前找到的最优加工方案的完成时间。显然，继续向深处搜索时，f2不会减少，只会增加。因此，当f2≥bestf时，没有继续向深处搜索的必要。限界条件可以描述为：f2<bestf。f2初值为0，bestf的初值为无穷大。
- 搜索过程。扩展结点沿着某个分支扩展时需要判断限界条件，如果满足，则进入深一层继续搜索；如果不满足，则剪掉该分支。搜索到叶子结点的时候，即找到当前最优解。搜索直到全部活结变成死结点为止。
代码实现
1.数据结构
|
1 2 3 4 5 6 |
struct node { //机器零件在第一台机器上的加工时间x和第二胎机器上的加工时间y int x,y; }T[MAX]; |
2.按限界条件进行搜索求解：t表示当前扩展结点在第t层，f1表示当前第一台机器上加工的完成时间，f2表示当前第二台机器上加工的完成时间。如果t>n表示已经到达叶子结点，记录最优值和最优解，返回。否则，分别判断每个分支是否满足约束条件，若满足则进入下一层backtrack(t+1)；如果不满足则反操作复位，考察下一个分支（兄弟结点）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
void Backtrack(int t) { if(t>n) { for(int i=1;i<=n;i++) bestx[i]=x[i];//记录最优队列 bestf=f2;//更新最优值 return ; } for(int i=t;i<=n;i++) { f1+=T[x[i].x; int temp=f2; f2=max(f1,f2)+T[x[i]].y; if(f2<bestf)//满足限界条件 { swap(x[t],x[i]);//交换 Backtrack(t+1);//继续搜索 swap(x[t],x[i]);//复位，反操作 } f1-=T[x[i]].x;//复位，反操作 f2=temp;//复位，反操作 } } |
算法复杂度分析
时间复杂度为O(nn!)≈O((n+1)!)，空间复杂度为O(n)。
算法优化改进
新的算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。利用贝尔曼规则，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<iostream> #include<algorithm> using namespace std ; const int MX=10000+5 ; int n; struct node { int id; int x,y; }T[MX] ; bool cmp(node a,node b) { return min(b.x,a.y)>=min(b.y,a.x);//按照贝尔曼规则排序 } int main() { cout<<"请输入机器零件的个数 n:"; cin>>n; cout<<"请依次输入每个机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y:"; for(int i=0;i<n;i++) { cin>>T[i].x>>T[i].y; T[i].id=i+1; } sort(T,T+n,cmp); //排序 int f1=0,f2=0; for(int i=0;i<n;i++) //计算总时间 { f1+=T[i].x; f2=max(f1,f2)+T[i].y; } cout<<"最优的机器零件加工顺序为:"; for(int i=0;i<n;i++) //输出最优加工顺序 cout<<T[i].id<<" "; cout<<endl; cout<<"最优的机器零件加工的时间为:"; cout<<f2<<endl; return 0 ; } |
旅行商问题
问题描述
假设有5个点，这五个点之间是用无向边来连接的，但是每一个边是有权重的，这实际上是一个无向带权图。我们希望在最小权重的情况下走过这5个点，且不重复，那应该怎样来实现呢？
算法设计
- 定义问题的解空间：问题解的形式为n元组{x1,x2,...,xi,...,xn}，分量xi表示第i个要去的旅游景点编号，景点的集合为S={1,2,...,N}。因为景点不可重复走，因此在确定xi时，前面走过的景点{x1,x2,...,xi,...,xi-1}不能再走。xi的取值为S-{x1,x2,...,xi,...,xi-1}。
- 解空间的组织形式：解空间是一颗排列树，树的深度为n=5。除了开始结点1之外，一共有24种排列方式。
- 搜索解空间：约束条件：用二维数组g[][]储存无向带权图的邻接矩阵，如果g[i][j]≠无穷表示城市i和城市j又边相连，能走通。限界条件：cl<bestl。cl的初始值为0，表示当前已经走过的城市所用的路径长度；bestl初始值为无穷，表示当前找到的最短路径的路径长度。
- 搜索过程：扩展结点沿着某个分支扩展时需要判断约束条件和限界条件，如果满足，则进入深一层继续搜索，如果不满足，则剪掉该分支。搜索到叶子结点时，即找到了当前最优解。搜索直到全部的活结点变成死结点为止。
完美图解
（1）数据结构：如下表所示的邻接矩阵。
| 3 | 8 | 9 | ||
|---|---|---|---|---|
| 3 | 3 | 10 | 5 | |
| 3 | 4 | 3 | ||
| 8 | 10 | 4 | 20 | |
| 9 | 5 | 3 | 20 |
（图中未填的就是无穷）
（2）初始化：cl=0,bestl=无穷，解分量x[i]和最优解bestx[i]初始化为：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x[i] | 1 | 2 | 3 | 4 | 5 |
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| bestx[i] | 0 | 0 | 0 | 0 | 0 |
（3）开始搜索第一层（t=1）
扩展A0结点，因为我们是从1号结点出发，所以x[1]=1，生成A结点。
（4）扩展A结点（t=2）
沿着x[2]=2分支扩展，因为1号结点和2号结点有边相连，且cl+g[1][2]=0+3<bestl，满足限界条件，生成B结点。
（5）扩展B结点（t=3）
沿着x[3]=3分支扩展，因为2号结点和3号结点有边相连，且cl+g[2][3]=3+3=6<bestl，满足限界条件，生成C结点。
（6）扩展C结点（t=4）
沿着x[4]=4分支扩展，因为3号结点和4号结点有边相连，且cl+g[3][4]=6+4=10<bestl，满足限界条件，生成D结点。
（7）扩展D结点（t=5）
沿着x[5]=5分支扩展，因为4号结点和5号结点有边相连，且cl+g[3][4]=10+20=30<bestl，满足限界条件，生成E结点。
（8）扩展E结点（t=6）
t>n，判断5号结点是否和1号结点相连，确认有，且cl+g[5][1]=30+9=39<bestl，找到一个当前最优解（1,2,3,4,5,1），更新bestl=39。
（9）向上回溯到D，D的孩子已经生成完毕，成为死结点，继续回溯到C，C结点还有一个孩子未生成。
（10）重新扩展C结点（t=4）。沿着x[4]=5分支扩展，因为3号结点和5号结点有边相连，且cl+g[3][5]=6+3=9<bestl=39，满足限界条件，生成F结点。
（11）扩展F结点（t=5）。
沿着x[5]=4分支扩展，因为5号结点和4号结点有边相连，且cl+g[5][4]=9+20=29<bestl=39，满足限界条件，生成G结点。
（12）扩展G结点（t=6）。t>n，判断4号结点是否和1号结点相连，确认有，且cl+g[4][1]=29+8=37<bestl=39，找到一个当前最优解（1,2,3,5,4,1），更新bestl=37。
不断搜索下去，到最后有以下组合和其值。
| i | 1 | 2 | 3 | 4 | 5 | 权值 |
|---|---|---|---|---|---|---|
| 结点组合 | 1 | 2 | 3 | 4 | 5 | 39 |
| 结点组合 | 1 | 2 | 3 | 5 | 4 | 37 |
| 结点组合 | 1 | 2 | 4 | 3 | 5 | 29 |
| 结点组合 | 1 | 2 | 5 | 3 | 4 | 23 |
| 结点组合 | 1 | 4 | 3 | 2 | 5 | 29 |
| 结点组合 | 1 | 4 | 3 | 5 | 2 | 23 |
| 结点组合 | 1 | 5 | 2 | 3 | 4 | 29 |
综上所述，bestl=23，路径为1-2-5-3-4-1。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
//初始化 void init() { bestl = INF; cl = 0; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) g[i][j] = g[j][i] = INF; for (int i = 0; i <= n; i++) { x[i] = i; bestx[i] = 0; } } //邻接矩阵赋值 void createMatrix() { int u, v, w;//结点u和v，权值w cout << "请依次输入两个结点u和v之间的权值w。" << endl; cout << "格式：结点u 结点v 距离w" << endl; for (int i = 1; i <= m; i++) { cin >> u >> v >> w; g[u][v] = g[v][u] = w; } } //回溯法核心 void backTrack(int t) { if (t > n) //到达叶子结点 //最后一个结点与第一个结点有边相连且路径长度比当前最优值最小 //说明找到了一条更优路径，记录相关信息 { if (g[n][1] != INF && (cl + g[x[n]][1] < bestl)) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestl = cl + g[x[n]][1]; } } else { //没有到达叶子结点 for (int j = t; j <= n; j++) { //搜索扩展结点的所有分支 //如果第t-1个结点与第t个结点有边相连且可以得到更短路径 if (g[x[t - 1]][x[j]] != INF && (cl + g[x[t - 1]][x[j]] < bestl)) { //保存第t个结点到x[t]中，进入第t+1个 swap(x[t], x[j]);//交换两个元素的值 cl = cl + g[x[t - 1]][x[t]]; backTrack(t + 1); cl = cl - g[x[t - 1]][x[t]]; swap(x[t], x[j]); } } } } //打印路径 void print() { cout << "最短路径：" << endl; for (int i = 1; i <= n; i++) cout << bestx[i] << "--->"; cout << "1" << endl; cout << "最短路径长度：" << bestl << endl; } |
算法复杂度分析
- 时间复杂度：除了最后一层外，有1+(n-1)+...+(n-1)(n-2)...2<=n(n-1)!个结点需要判断约束函数和限界函数，判断两个函数需要O(1)的时间，因此耗时O(n!)。在叶子节点处记录当前最优解需要耗时O(n)，在最坏情况下回搜索到每一个叶子结点，叶子数为(n-1)!，所以时间复杂度为O（n!）。
- 空间复杂度：O(n)。
