旅行商问题
问题分析
带权邻接矩阵g[][]如下所示,空表示为无穷,即没有路径。
15 | 30 | 5 | |
---|---|---|---|
15 | 6 | 12 | |
30 | 6 | 3 | |
5 | 12 | 3 |
算法设计
可以使用优先队列分支限界法,加快搜索速度。
设置优先级:当前已走过的城市所有的路径长度cl。cl越小,优先级越高。
从根节点开始,以广度优先的方式进行搜索。根节点首先成为活结点,也是当前的扩展结点。一次性生成所有的孩子结点,判断孩子结点是否满足约束条件和限界条件,如果满足,将其加入到队列中,反之,舍弃。然后再从队列中取出一个元素,作为当前扩展结点,搜索过程队列为空时为止。
代码实现
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.定义节点结构体
//定义结点,记录当前结点的解信息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.定义队列优先级
bool operator <(const Node &a, const Node &b){ return a.zl>b.zl;}
3.计算下界
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 为优化的优先队列式分支限界法
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,则进入该方向方格,使其成为当前的扩展结点。以此类推,搜索过程一直持续到起始结点结束。
算法实现
//定义结构体positiontypedef 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)。