分支界限法求单元点最短路径Word文件下载.docx
- 文档编号:870851
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:9
- 大小:84.86KB
分支界限法求单元点最短路径Word文件下载.docx
《分支界限法求单元点最短路径Word文件下载.docx》由会员分享,可在线阅读,更多相关《分支界限法求单元点最短路径Word文件下载.docx(9页珍藏版)》请在冰点文库上搜索。
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。
其中,每一个结点旁边的数字表示该结点所对应的当前路长。
2.算法思想
解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。
其优先级是结点所对应的当前路长。
算法从图G的源顶点s和空优先队列开始。
结点s被扩展后,它的儿子结点被依次插入堆中。
此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点。
如果从当前扩展结点i到顶点j有边可达,且从源出发,途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。
这个结点的扩展过程一直继续到活结点优先队列为空时为止。
3.剪枝策略
在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树。
在算法中,利用结点间的控制关系进行剪枝。
从源顶点s出发,2条不同路径到达图G的同一顶点。
由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。
三.程序设计:
#include<
iostream>
usingnamespacestd;
constintsize=100;
constintinf=5000;
//两点距离上界
//第一组测试参数
constintn=6;
//图顶点个数加1
intprev[n];
//图的前驱顶点
intdist[]={0,0,5000,5000,5000,5000};
//最短距离数组
intc[n][n]={{0,0,0,0,0,0},{0,0,2,3,5000,5000},//图的邻接矩阵
{0,5000,0,1,2,5000},{0,5000,5000,0,9,2},
{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};
/*
//第二组测试参数
constintn=5;
intdist[]={0,0,5000,5000,5000};
intc[][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0}};
*/
classMinHeapNode{
public:
inti;
//顶点编号
intlength;
//当前路长
};
//循环队列
classCirQueue{
private:
intfront,rear;
MinHeapNodedata[size];
public:
CirQueue(){
front=rear=0;
}
//元素入队操作
voidqueryIn(MinHeapNodee){
if((rear+1)%size!
=front){
rear=(rear+1)%size;
//队尾指针在循环意义下加1
data[rear]=e;
//在队尾插入元素
//元素出队操作
MinHeapNodequeryOut(){
if(rear!
front=(front+1)%size;
//队列在循环意义下加1
returndata[front];
//读取队头元素,但不出队
MinHeapNodegetQuery(){
returndata[(front+1)%size];
//判断队列是否为空
boolempty(){
returnfront==rear;
//判断队列是否为满
boolfull(){
return(rear+1)%size==front;
};
//CirQueue结束
//图的表示
classGraph{
/**
*单源最短路径问题的优先队列式分支限界法
*/
voidshortestPath(intv){
//创建队列
CirQueueqq;
//定义源为初始扩展结点
MinHeapNodee;
e.i=v;
e.length=0;
dist[v]=0;
qq.queryIn(e);
//搜索问题的解空间
while(true){
for(intj=1;
j<
n;
j++){
if(j>
=n){
break;
MinHeapNodem=qq.getQuery();
if((c[m.i][j]<
inf)&
&
(m.length+c[m.i][j]<
dist[j])){
//顶点i到顶点j可达,且满足控制约束
dist[j]=m.length+c[m.i][j];
prev[j]=m.i;
//加入活结点优先队列
MinHeapNodemi;
mi.i=j;
mi.length=dist[j];
if(qq.full()){
qq.queryIn(mi);
//元素入队
}//for循环结束
if(qq.empty()){
qq.queryOut();
//当该结点的孩子结点全部入队后,删除该结点
}//while循环结束
}//方法结束
//类结束
intmain(){
Graphg;
g.shortestPath
(1);
cout<
<
"
最短路径长为"
dist[n-1]<
endl;
中间路径为:
"
;
for(inti=3;
i<
i++){
prev[i]<
endl<
欢迎使用本系统"
return0;
}
四.程序示例:
五.算法优缺点:
每一步的扩散为当前耗散度的最优。
队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索,不同的是队列式分支限界法不搜索以不可行结点(已经被判定不能导致可行解或不能导致最优解的结点)为根的子树。
按照规则,这样的结点不被列入活结点表。
A->
E->
Q->
M
优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。
结点的优先级常用一个与该结点有关的数值p来表示。
最大优先队列规定p值较大的结点点的优先级较高。
在算法实现时通常用一个最大堆来实现最大优先队列,体现最大效益优先的原则。
类似地,最小优先队列规定p值较小的结点的优先级较高。
在算法实现时,常用一个最小堆来实现,体现最小优先的原则。
采用优先队列式分支定界算法解决具体问题时,应根据问题的特点选用最大优先或最小优先队列,确定各个结点点的p值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支 界限 单元 点最短 路径
![提示](https://static.bingdoc.com/images/bang_tan.gif)