旅行商问题
问题分析
带权邻接矩阵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,则进入该方向方格,使其成为当前的扩展结点。以此类推,搜索过程一直持续到起始结点结束。
算法实现
//定义结构体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)。
文章评论