算法笔记之分支限界法（2）
旅行商问题
问题分析
带权邻接矩阵g[][]如下所示，空表示为无穷，即没有路径。
| 15 | 30 | 5 | |
|---|---|---|---|
| 15 | 6 | 12 | |
| 30 | 6 | 3 | |
| 5 | 12 | 3 |
算法设计
可以使用优先队列分支限界法，加快搜索速度。
设置优先级：当前已走过的城市所有的路径长度cl。cl越小，优先级越高。
从根节点开始，以广度优先的方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有的孩子结点，判断孩子结点是否满足约束条件和限界条件，如果满足，将其加入到队列中，反之，舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时为止。
代码实现
|
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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
struct Node//定义结点,记录当前结点的解信息 { double cl; //当前已走过的路径长度 int id; //景点序号 int x[N];//记录当前路径 Node() {} Node(double _cl,int _id) { cl = _cl; id = _id; } }; //定义队列的优先级。 以cl为优先级，cl值越小，越优先 bool operator <(const Node &a, const Node &b) { return a.cl>b.cl; } //Travelingbfs 为优先队列式分支限界法搜索 double Travelingbfs() { int t; //当前处理的景点序号t Node livenode,newnode;//定义当前扩展结点livenode,生成新结点newnode priority_queue<Node> q; //创建一个优先队列,优先级为已经走过的路径长度cl,cl值越小，越优先 newnode=Node(0,2);//创建根节点 for(int i=1;i<=n;i++) { newnode.x[i]=i;//初时化根结点的解向量 } q.push(newnode);//根结点加入优先队列 cout<<"按优先级出队顺序："<<endl;//用于调试 while(!q.empty()) { livenode=q.top();//取出队头元素作为当前扩展结点livenode q.pop(); //队头元素出队 //用于调试 cout<<"当前结点的id值:"<<livenode.id<<"当前结点的cl值:"<<livenode.cl<<endl; cout<<"当前结点的解向量:"; for(int i=1; i<=n; i++) { cout<<livenode.x[i]; } cout<<endl; t=livenode.id;//当前处理的景点序号 // 搜到倒数第2个结点时个景点的时候不需要往下搜索 if(t==n) //立即判断是否更新最优解， //例如当前找到一个路径(1243)，到达4号结点时，立即判断g[4][3]和g[3][1]是否有边相连， //如果有边则判断当前路径长度cl+g[4][3]+g[3][1]<bestl，满足则更新最优值和最优解 { //说明找到了一条更好的路径，记录相关信息 if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF) if(livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]<bestl) { bestl=livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]; cout<<endl; cout<<"当前最优的解向量:"; for(int i=1;i<=n;i++) { bestx[i]=livenode.x[i]; cout<<bestx[i]; } cout<<endl; cout<<endl; } continue; } //判断当前结点是否满足限界条件，如果不满足不再扩展 if(livenode.cl>=bestl) continue; //扩展 //没有到达叶子结点 for(int j=t; j<=n; j++)//搜索扩展结点的所有分支 { if(g[livenode.x[t-1]][livenode.x[j]]!=INF)//如果x[t-1]景点与x[j]景点有边相连 { double cl=livenode.cl+g[livenode.x[t-1]][livenode.x[j]]; if(cl<bestl)//有可能得到更短的路线 { newnode=Node(cl,t+1); for(int i=1;i<=n;i++) { newnode.x[i]=livenode.x[i];//复制以前的解向量 } swap(newnode.x[t], newnode.x[j]);//交换x[t]、x[j]两个元素的值 q.push(newnode);//新结点入队 } } } } return bestl;//返回最优值。 } |
（1）时间复杂度：O(n!)。空间复杂度：O(n*n!)。
算法优化拓展
- 算法开始时创建一个用于表示活结点优先队列。每个结点的费用下界zl=cl+rl值作为优先级。cl表示已经走过的路径长度，rl表示剩余路径长度的下界，rl用剩余每个结点的最小出边之和来计算。初始时先计算图中每个顶点i的最小出边，并用minout[i]数组记录，minsum记录所有结点的最小出边之和。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法立即结束。
- 限界条件：zl<bestl，zl<cl+rl。
- 优先级：zl指已经走过的路径长度+剩余路径长度的下界。zl越小，优先级越高。
算法优化代码实现
1.定义节点结构体
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//定义结点,记录当前结点的解信息 struct Node { double cl; //当前已走过的路径长度 double rl; //剩余路径长度的下界 double zl; //当前路径长度的下界zl=rl+cl int id; //景点序号 int x[N];//记录当前解向量 Node() {} Node(double _cl,double _rl,double _zl,int _id) { cl = _cl; rl = _rl; zl = _zl; id = _id; } }; |
2.定义队列优先级
|
1 2 3 4 5 |
bool operator <(const Node &a, const Node &b) { return a.zl>b.zl; } |
3.计算下界
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
bool Bound()//计算下界（即每个景点最小出边权值之和） { for(int i=1;i<=n;i++) { double minl=INF;//初时化景点点出边最小值 for(int j=1;j<=n;j++)//找每个景点的最小出边 if(g[i][j]!=INF&&g[i][j]<minl) minl=g[i][j]; if(minl==INF) return false;//表示无回路 minout[i]=minl;//记录每个景点的最少出边 cout<<"第"<<i<<"个景点的最少出边:"<<minout[i]<<" "<<endl; minsum+=minl;//记录所有景点的最少出边之和 } cout<<"每个景点的最少出边之和:""minsum= "<<minsum<<endl; return true; } |
4.Travelingbfsopt 为优化的优先队列式分支限界法
|
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 73 74 |
double Travelingbfsopt() { if(!Bound()) return -1;//表示无回路 Node livenode,newnode;//定义当前扩展结点livenode,生成新结点newnode priority_queue<Node> q; //创建一个优先队列,优先级为当前路径长度的下界zl=rl+cl,zl值越小，越优先 newnode=Node(0,minsum,minsum,2);//创建根节点 for(int i=1;i<=n;i++) { newnode.x[i]=i;//初时化根结点的解向量 } q.push(newnode);//根结点加入优先队列 while(!q.empty()) { livenode=q.top();//取出队头元素作为当前扩展结点livenode q.pop(); //队头元素出队 cout<<"当前结点的id值:"<<livenode.id<<"当前结点的zl值:"<<livenode.zl<<endl; cout<<"当前结点的解向量:"; for(int i=1; i<=n; i++) { cout<<livenode.x[i]; } cout<<endl; int t=livenode.id;//当前处理的景点序号 // 搜到倒数第2个结点时个景点的时候不需要往下搜索 if(t==n) //立即判断是否更新最优解， //例如当前找到一个路径(1243)，到达4号结点时，立即判断g[4][3]和g[3][1]是否有边相连， //如果有边则判断当前路径长度cl+g[4][3]+g[3][1]<bestl，满足则更新最优值和最优解 { //说明找到了一条更好的路径，记录相关信息 if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF) if(livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]<bestl) { bestl=livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]; cout<<endl; cout<<"当前最优的解向量:"; for(int i=1;i<=n;i++) { bestx[i]=livenode.x[i]; cout<<bestx[i]; } cout<<endl; cout<<endl; } continue; } //判断当前结点是否满足限界条件，如果不满足不再扩展 if(livenode.cl>=bestl) continue; //扩展 //没有到达叶子结点 for(int j=t; j<=n; j++)//搜索扩展结点的所有分支 { if(g[livenode.x[t-1]][livenode.x[j]]!=INF)//如果x[t-1]景点与x[j]景点有边相连 { double cl=livenode.cl+g[livenode.x[t-1]][livenode.x[j]]; double rl=livenode.rl-minout[livenode.x[j]]; double zl=cl+rl; if(zl<bestl)//有可能得到更短的路线 { newnode=Node(cl,rl,zl,t+1); for(int i=1;i<=n;i++) { newnode.x[i]=livenode.x[i];//复制以前的解向量 } swap(newnode.x[t], newnode.x[j]);//交换两个元素的值 q.push(newnode);//新结点入队 } } } } return bestl;//返回最优值。 } |
算法复杂度分析
时间复杂度最坏为O(nn!)，空间复杂度为O(n2*(n+1)!)。
最优工程布线问题
问题描述
在3×3的方格阵列，灰色表示封锁，不能通过。将每个方格抽象为一个结点，方格和相邻4个方向（上下左右）中能通过的方格用一条线连接起来，不能通过的方格不连线。这样，可以把问题的解空间定义为一个图，如下图所示。
该问题是特殊的最短路径问题，特殊之处在于用布线走过的方格数代表布线的长度，布线时每一个方格，布线长度累加1.我们可以看出，从a到b有多种布线方案，最短的布线长度即从a到b的最短路径长度为4。
既然只能朝四个方向布线，也就是说如果从树型搜索的角度来看，我们可以把它看做为m叉树，那么问题的解空间就变成了一颗m叉树。
算法设计
（1）定义问题的解空间。可以把最优工程布线问题解的形式为n元组{x1,x2,...,xi,...,xn}，分量xi表示最优布线方案经过的第i个方格，而方格也可以用(x,y)表示第x行第y列。因为方格不可重复布线，所以在确定xi的时候，前面走过的方格{x1,x2,...,xi-1}都不可以再走，xi的取值范围为S-{x1,x2,...,xi-1}。
注意：和前面问题不同，因为不知道最优布线长度，所以n是未知的。
（2）解空间的组织结构：一颗m叉树，m=4，树的深度n未知。
（3）搜索解空间。搜索从起始结点a开始，到目标节点b结束。
- 约束条件：非障碍物或边界未曾布线。
- 限界条件：最先碰到的一定是距离最短的，因此无限界条件。
- 搜索过程：从a开始将其作为第一个扩展结点，沿a的右、下、左、上4个方向的相邻结点扩展。判断约束条件是否成立，若成立，则放入活结点中，并将这个方格标记为1。接着从活结点队列中取出队首结点作为下一个扩展结点，并沿当前扩展结点的右、下、左、上四个方向的相邻结点扩展，将满足约束条件的方格记为2，依此类推，一直继续搜索到目标方格或活结点为空为止，目标方格里的数据就是最优的布线长度。
构造最优解过程从目标节点开始，沿着右、下、左、上四个方向。判断如果某个方向方格里的数据比扩展结点方格的数据小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 73 74 75 76 77 78 79 80 81 82 83 84 85 |
//定义结构体position typedef struct { int x; int y; } Position;//位置 int grid[100][100];//地图 bool findpath(Position s, Position e, Position *&path, int &PathLen) { if ((s.x == e.x) && (s.y == e.y))//开始位置就是结束位置 { PathLen = 0; return true; } Position DIR[4], here, next; //定义方向数组DIR[4]，当前位置here，下一个位置next DIR[0].x = 0; DIR[0].y = 1; DIR[1].x = 1; DIR[1].y = 0; DIR[2].x = 0; DIR[2].y = -1; DIR[3].x = -1; DIR[3].y = 0; here = s; grid[s.x][s.y] = 0;//标记初始为0，未布线为-1，墙壁为-2 queue<Position> Q;//所使用队列 //按四个方向进行搜索 for (;;) { for (int i = 0; i < 4; i++)//四个方向前进，右下左上 { next.x = here.x + DIR[i].x; next.y = here.y + DIR[i].y; if (grid[next.x][next.y] == -1)//未布线 { grid[next.x][next.y] = grid[here.x][here.y] + 1; Q.push(next); } if ((next.x == e.x) && (next.y == e.y)) break;//找到了我们需要的目标 } if ((next.x == e.x) && (next.y == e.y)) break;//找到了我们需要的目标 if (Q.empty()) return false; else { here = Q.front(); Q.pop();//把Q队头的元素弹出 } } //逆向找回最短布线方案 PathLen = grid[e.x][e.y];//最短的长度 path = new Position[PathLen]; here = e; for (int j = PathLen - 1; j >= 0; j--) { path[j] = here; //沿着四个方向寻找，右下左上 for (int i = 0; i < 4; i++) { next.x = here.x + DIR[i].x; next.y = here.y + DIR[i].y; if (grid[next.x][next.y] == j) break; } here = next; } return true; } //初始化地图，标记大于0表示已经布线，-1未布线，-2墙壁 void init(int m, int n) { for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) grid[i][j] = -1; //上面是先将所有的格子都初始化为-1 //然后把本问题为了方便加上的第0行和第0列都设置为墙 for (int i = 0; i <= n + 1; i++) grid[0][i] = grid[m + 1][i] = -2; for (int i = 0; i <= m + 1; i++) grid[i][0] = grid[i][n + 1] = -2; } |
复杂度分析
时间复杂度O(nm)，构造最短布线需要O(L)，空间复杂度O(n)。
![[leetcode]populating next right pointers in each node](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=https://dqhplhzz2008-1251830035.cos.ap-guangzhou.myqcloud.com/wp-content/uploads/2019/04/pnrpien1.png&h=180&w=300&zc=1)
![[Leetcode]merge sorted array](http://www.yushuai.xyz/wp-content/themes/MyDream/img/random/16.jpg)
