分支界限法求单元点最短路径.docx

分支界限法求单元点最短路径.docx

《分支界限法求单元点最短路径.docx》由会员分享，可在线阅读，更多相关《分支界限法求单元点最短路径.docx（9页珍藏版）》请在冰点文库上搜索。

分支界限法求单元点最短路径

一．分支界限法的基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

对已处理的各结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大/极小）的结点优先进行广度优先搜索不断调整搜索方向，尽快找到解。

特点：

限界函数常基于问题的目标函数，适用于求解最优化问题。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

二．单源最短路径问题

1.问题描述

下面以一个例子来说明单源最短路径问题：

在下图所给的有向图G中，每一边都有一个非负边权。

要求图G的从源顶点s到目标顶点t之间的最短路径。

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

2.算法思想

解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。

其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。

结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个结点的扩展过程一直继续到活结点优先队列为空时为止。

3.剪枝策略

在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。

在算法中，利用结点间的控制关系进行剪枝。

从源顶点s出发，2条不同路径到达图G的同一顶点。

由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。

三．程序设计：

#include

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;//图顶点个数加1

intprev[n];//图的前驱顶点

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=（front+1）%size;//队列在循环意义下加1

returndata[front];

}

}

//读取队头元素，但不出队

MinHeapNodegetQuery（）{

if（rear!

=front）{

returndata[（front+1）%size];

}

}

//判断队列是否为空

boolempty（）{

returnfront==rear;

}

//判断队列是否为满

boolfull（）{

return（rear+1）%size==front;

}

};//CirQueue结束

//图的表示

classGraph{

public:

/**

*单源最短路径问题的优先队列式分支限界法

*/

voidshortestPath（intv）{

//创建队列

CirQueueqq;

//定义源为初始扩展结点

MinHeapNodee;

e.i=v;

e.length=0;

dist[v]=0;

qq.queryIn（e）;

//搜索问题的解空间

while（true）{

for（intj=1;j

if（j>=n）{

break;

}

MinHeapNodem=qq.getQuery（）;

if（（c[m.i][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（））{

break;

}

qq.queryIn（mi）;//元素入队

}

}//for循环结束

if（qq.empty（））{

break;

}

qq.queryOut（）;//当该结点的孩子结点全部入队后，删除该结点

}//while循环结束

}//方法结束

};//类结束

intmain（）{

Graphg;

g.shortestPath

（1）;

cout<<"最短路径长为"<

cout<<"中间路径为：

";

for（inti=3;i

cout<

}

cout<

return0;

}

四．程序示例：

五．算法优缺点：

每一步的扩散为当前耗散度的最优。

队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。

按照规则，这样的结点不被列入活结点表。

A->E->Q->M

优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。

结点的优先级常用一个与该结点有关的数值p来表示。

最大优先队列规定p值较大的结点点的优先级较高。

在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。

类似地，最小优先队列规定p值较小的结点的优先级较高。

在算法实现时，常用一个最小堆来实现，体现最小优先的原则。

采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p值