算法设计与分析-多段图最短路径问题

关于多段图最短路径问题的探讨

摘要：

本文主要描述的是分别用动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况，并在附录中附有实际问题的程序来辅助阐述观点。文章首先阐述了各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运行时间，以之为基础来分析、讨论三者的性能区别。另外，众所周知，多段图是有向图的一个简单的模型，它在有向图的基础上忽略了两点之间的线的双向性的问题，并且对点与点之间的线有很多的要求，从而把图简化为可分为几段的模式，文章最后讲述了若这几种方法运行到有向图中的情况，几种方法的对比和它们比较适应的使用情况的讨论，并给出了自己的建议。

关键字：

多段图最短路径问题动态规划法分支限界法多段图与有向图的关系有向图最短路径算法

引言：

当前社会，关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中，排除其他影响因素，从一个地点到另一点，这个时候必然是希望有一条距离最短的路程来尽量减少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很大的需求，因此，这里我将讨论多段图的最短路径的问题。

在早些时间的课程中，我们学习过数据结构这门课程，其中就包括最短路径这方面的讨论。当时老师给我们介绍了分别面向单源（Dijkstra算法）与非单源（Floyd算法）两种问题的算法法---，这是我们最早的对最短路径方面的理解，也是我们接触的比较早的关于图的问题。在这学期的算法课程中，我们学习了许多了方法，包括贪心法、动态规划法等算法，它们把以前学习的许多方法都命名并归纳分类起来，其中有许多算法都是可以用来解决这个最短路径的问题的，并且该问题作为一个图的问题，对该问题的继续探讨优化的需求很大，本文将就不同算法在解决该最短路径问题时的不同方法进行对比并给出该问题在不同基础上不同的最终解决方案。由于时间的限制，本文将重点分析动态规划法下的情况，并会对图的情况加以简化、限制，最后会对其他的图做一些拓展。

首先，对多段图最短路径问题进行介绍，设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集V i（2≤k≤n, 1≤i≤k），使得E中的任何一条边(u, v)，必有u∈V i，v∈V i+m（1≤i＜k, 1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈V k 为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。

这里我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图来说，图中是没有环的存在的。

1.贪心法

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

本例中利用的贪心算法，是每当要选择下一个结点时，总是选择与当前结点间代价最小的点，这就叫做总是优先局部最优解。以此得到最终的解序列。这里举一个贪心法的拓展例子Dijkstra算法。

Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路径，动态路由协议OSPF中就用到了Dijkstra算法来为路由计算最短路径。

算法本身并不是按照我们的正常思维习惯，我们一般会，从原点遍历所有与之相连的节点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点（原点除外），然后依次类推。这样做虽然可以算出一个树形，但是在大多数情况下，这种算法会产生很多次优路径，也就是说非最短路径。

Dijkstra算法的大概过程：

假设有两个集合或者说两个表，表A和表B

表A表示生成路径，表B表示最后确定的路径

1.从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中，并记录下两节点之间的代价。

2.将代价最小的代价值和这两节点移动到表B中（其中一个是原点）。

3.把这个节点所连接的子节点找出，放入到表A中，算出子节点到原点的代价

4.重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。

维基百科中还有另一种说法，Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。具体算法见附录。

2.动态规划法

这里先讨论用动态规划法的解法。考虑多段图的最短路径问题的填表形式。用一个数组cost[n]作为存储子问题解的表格，cost[i]表示从顶点i到终点n-1的最短路径，数组path[n]存储状态，path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则：cost[i]=min{c ij+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点) （式6.7）

path[i]=j (使c ij+cost[j]最小的j) （式6.8）

对多段图的边(u, v)，用c uv表示边上的权值，将从源点s到终点t的最短路径记为d(s, t)，则从源点0到终点9的最短路径d(0, 9)由下式确定：d(0, 9)=min{c01+d(1, 9), c02+d(2, 9),

c03+d(3, 9)}，这是最后一个阶段的决策，它依赖于d(1, 9)、d(2, 9)和d(3, 9)的计算结果，而由此模式推知，d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}，d(2, 9)=min{c24+d(4, 9), c25+d(5, 9),

c26+d(6, 9)}，d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)}，每一个d（i，n-1）都是通过min{c ik+d(k,n-1)}得到的k>i&&k

算法主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法的时间复杂性为O(n+m)。为了实现时间的分析，在程序后添加了输出运行时间的函数，以便于对比分析。具体算法、具体代码及实验结果见附录1。

3.分支限界法

再讨论当用分支限界法用来解决多段图路径问题的过程：

首先对该多段图应用贪心法求得近似解，并算出其代价路径。将其作为多段图最短路径问题的上界。而把每一段最小的代价相加，可以得到一个非常简单的下界。于是，就可以得到了目标函数的一个大致的范围。

由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了i段（1≤i≤k），其路径为(r1, r2, …, r i, r i+1)，此时，该部分解的目标函数值的计算方法即限界函数如下：

应用分支限界法同样求解附录中图所示多段图的最短路径问题，具体的搜索过程是这样进行的，首先考虑根节点，根据限界函数算出目标函数的值，然后下一个结点的选择在本例中有三种情况，这里每种情况下的目标函数值下界都要算出来并且加以比较，下界的计算方法为除了加上选定点与初始点之间的距离外，以后的第一个点选择一选定点为初始点到下段最小代价的路径，以后的段与段之间的代价都按他们之间最小的代价来计算。这样再加上根节点与初始阶段之间的最小代价，就得到这种情况下的解了。在得到的代价中，找出最小的代价，并以之为初始结点循环往下做，直到到达目标结点。

结论：

程序的运行截图如附录所示。分析各个方法的整个过程得到以下思考：

1.贪心法、动态规划法和分支限界法都可以用来解决多段最短路径问题，然而在这种情况相比之下，贪心法的运算效率比较高，因为它不像另外两种方法一样，需要涉及到许多的点。由于这里并没有找到函数有效地给程序计时（time函数很不精确，而对于小程序来说，就没有什么参考性）。因此这里我们就以本题的数据为例，用一个笨方法，看各个方法访问了多少数据，可以看到，动态规划法由于需要填表，并有一个相关的迭代问题，它几乎涉及了所有的点；而分支限界法，它通过贪心法设置的上下限，并以他们为依据进行剪枝，减少了许多的运算量。而贪心法，访问了最少的点。

2.就结果准确性来看，就本题例子来看，贪心法结果为0 2 4 7 9，路径的代价为20；动态分配法采取的路径为：0 3 5 8 9，路径的代价为16；而分支限界法，结果为0 3 5 8 9，路径的代价为16。可以看出，在这个方面，动态分配法和分支限界法都达到了预期的结果，相比直线，贪心法的误差就比较大了。

由以上的讨论，我们可以看出分支限界法的综合性能比较好，他和动态规划法在解决多段最短路径问题时都可以得到正确解，而贪心法虽然可以省时间与空间，但结果不准确是它的缺点。各方法都是有利有弊的。因此在选择方法时，还应当根据实际情况。当只需要大概的一个解时，当然是要用省时省力的贪心法；如果对结果又比较高的要求的话，那么就要采取动态规划法或分支限界法。那么dijkstra算法呢，他的明显优点就是它的多用性，他可以求任意一点到其他某一点的距离，但是他访问的数据量很大，几乎要访问所有的边（相对于贪心法而言），因此这里来说，在单纯的解决多段最短路径问题时，他们的功能都差不多，而在解决其他较复杂的图时，Dijkstra算法有明显的优越性，但当然，作为贪心法的一种，他的结果的准确性不是那么的高。Dijkstra算法在本质上为贪心算法,每一步的选择为当前步的最优,复杂度为O(n*n)。动态规划法是可以看作是对分支限界法的改进。

分支限界算法,每一步的扩散为当前耗散度的最优,复杂度为(没算)

其实，他们各有各的优缺点，可以尝试将他们混合起来用，扬长避短，像动态规划法和分支限界法，我们是不是可以试着在动态规划法的过程中像分支限界法里一样，设置范围，并且过程中对肯定不会是最后结果的数据“剪枝”。这样就可以提高运行速率了。

结论（必须精确、有条理、清晰与简要）：

建议（直接从结论中得出）：

附录

Dijstra算法（边的拓展）{

While（!(每一个d[v]==最短路径)）

If（存在一条从u到v的边）

If(d[u]+w(u,v)

d[v]= d[u]+w(u,v);

用动态规划法解决多段图的最短路径算法为：

1．初始化：数组cost[n]初始化为最大值，数组path[n]初始化为-1；

2．for (i=n-2; i>=0; i--)

2.1 对顶点i的每一个邻接点j，根据式6.7计算cost[i];

2.2 根据式6.8计算path[i];

3．输出最短路径长度cost[0];

4. 输出最短路径经过的顶点：

4.1 i=0

4.2 循环直到path[i]=n-1

4.2.1 输出path[i];

4.2.2 i=path[i];

用分支限界法求解多段图的最短路径问题的算法：

1．根据限界函数计算目标函数的下界down；采用贪心法得到上界up；

2．将待处理结点表PT初始化为空；

3．for (i=1; i<=k; i++) x[i]=0;

4．i=1; u=0; //求解第i段

5．while (i>=1)

5.1 对顶点u的所有邻接点v

5.1.1 根据式9.3计算目标函数值lb;

5.1.2 若lb<=up，则将i,,lb存储在表PT中；

5.2 如果i= =k-1且叶子结点的lb值在表PT中最小，

则输出该叶子结点对应的最优解；

5.3 否则，如果i= =k-1且表PT中的叶子结点的lb值不是最小，则

5.3.1 up=表PT中的叶子结点最小的lb值;

5.3.2 将表PT中目标函数值超出up的结点删除；

5.4 u=表PT中lb最小的结点的v值；

5.5 i=表PT中lb最小的结点的i值；i++;

动态规划法解决多段图最短路径问题：

/*多段图最短路径问题总结:

cost[i]表示从顶点i到终点n-1的最短路径，path[i]表示从顶点i到终点n-1的路径上顶点i 的下一个顶点；

下面的公式重点：

cost[i]=min{c(ij)+cost[j]}

path[i]=使c(ij)+cost[j]最小的j; c(ij)表示i和j顶点之间的距离*/

具体代码如下：

#include

#include

#define INFINITY 32767

#define MAX 20

__int64 start,end;

int min[6],Part;

typedef struct{

char vexs[MAX]; //顶点信息

int vexnum,arcnum;

int arcs[MAX][MAX]; //保存两个顶点之间的边长

}Graph; //图的结构体

struct node{

int part,node1,node2,lb,previous;

struct node *next;

};

void CreateGraph(Graph &G){//初始化多段图

int i,j;

start=clock();

printf("请输入顶点数和边数：");

//scanf("%d %d",&G.vexnum,&G.arcnum);

G.vexnum=10; //顶点数

G.arcnum=18; //边的数

for(i=0;i

G.vexs[i]=i;

}

for(i=0;i

for(j=0;j

G.arcs[i][j]=INFINITY;

}

printf("请按以下格式输入边的代价（顶点1 顶点2 两点之间边的代价，顶点标号从0开始）：\n");

for(k=0;k

scanf("%d %d %d",i,j,G.arcs[i][j]);

}

int getDown(Graph G){//分支限界法求下界

int j,k,i,n,n0,down=0,initial[6][20];//initial数组用来存储第i段有哪些结点

min[0]=INFINITY;

for(i=0;i<6;i++){

for(j=0;j<20;j++)

initial[i][j]=0;

}

j=0;

for(i=0;i

if(G.arcs[0][i]

initial[0][j++]=i;

if(G.arcs[0][i]

min[0]=G.arcs[0][i];

}

}

Part=1;

down+=min[i];

i=0;

while(initial[i++][0]!=G.vexnum-1){

n=0;j=0;min[i]=INFINITY;

while(initial[i-1][j++]!=0){

k=0;n0=n;

while((k++)

if(G.arcs[initial[i-1][j-1]][k-1]

initial[i][n++]=k-1;

if(G.arcs[initial[i-1][j-1]][k-1]

min[i]=G.arcs[initial[i-1][j-1]][k-1];

}

}

if(min[i]

down+=min[i];

Part++;

}

}

return down;

}

int Greedy(Graph G,int flag,int up){//贪心法

int min=INFINITY,m=flag;

printf("%d",flag);

for(int i=0;i

if(G.arcs[m][i]

min=G.arcs[m][i];

flag=i;

}

}

if(flag

printf("->");

up=Greedy(G,flag,up);

}

else printf("->%d\n",flag);

return up+min;

}

void path(Graph G,int up){//分支限界法

int down,i,j,k,u,lb,flag=1,previous=0;

struct node *p,*end,*PT,*q,*ST,*End,*mins;

down=getDown(G);

printf("\n若用分支限界法，该题的结果取值范围为[%d,%d]。\n",down,up);

PT=NULL;end=NULL;ST=NULL,End=NULL;//PT用来存储合格的点，ST表用来存储由于拓展被删除的点

i=1;u=0; //求解第i段,u表示顶点，u是那个已确定的顶点

while(flag){

// 5.1对顶点u的所有邻接点v

// 5.1.1 根据式9.3计算目标函数值lb;

// 5.1.2 若lb<=up，则将i,,lb存储在表PT中；

for(j=0;j

int mini=INFINITY;//mini是用来存储选择的那个下个结点所连接的最短的路径

if(mini>G.arcs[u][j]){

for(k=0;k

if(G.arcs[j][k]

mini=G.arcs[j][k];

}

lb=G.arcs[u][j]+mini;

for(int l=i+1;l

lb+=min[l];//min[]数组存的是每段中最短的路径长度

int Previous=previous;

int U=u;

if(U>0){//计算lb

lb+=G.arcs[Previous][U];

while(Previous!=0){

p=PT;

while(p!=NULL)

if(p->node1==Previous&&p->node2==U){

lb+=G.arcs[Previous][U];

U=Previous;

Previous=p->previous;

break;

}

}

}

if(lb<=up){

struct node *p=new struct node;

p->part=i+1;

p->node1=u;

p->node2=j;

p->lb=lb;

p->next=NULL;

p->previous=previous;

printf("%d->%d,代价%d,上一个结点为%d\n",p->node1,p->node2,p->lb,p->previous);

if(PT==NULL) PT=p;

else end->next=p;

end=p;

end->next=NULL;

}

}

}

q=PT;lb=INFINITY;

while(q!=NULL){

if(q->lb

mins=q;

lb=q->lb;

}

q=q->next;

}printf("%d %d lb=%d",mins->node1,mins->node2,lb);

if(p==q && G.arcs[end->node2][G.vexnum-1]

int dist=0,array[6]={0,0,0,0,0,0};

array[Part]=G.vexnum-1;

array[Part-1]=p->node2;

array[Part-2]=p->node1;

i=Part-3;

while(i>=0){

array[i]=p->previous;i--;

q=PT;

while(q->node2!=array[p->previous])

q++;

if(i>0)

array[i-1]=q->node1;

p=q;

}

printf("最短路径为：");

for(i=0;i

printf("%d->",array[i]);

if(i

dist+=G.arcs[i][i+1];

}

printf("%d",array[Part]);

printf("用分支限界法得到的最短路径长度为：%d",dist);

flag=0;

break;

}

p=PT;

if(p->node1==mins->node1&&p->node2==mins->node2){//删除PT链表中已被拓展的结点并把他添加到ST链表中

if(ST==NULL)

ST=p->next;

else

End->next=p->next;

End=p->next;

End->next=NULL;

PT=PT->next;

//printf("删除的结点是：%d %d\n",p->next->node1,p->next->node2);

}

/*else{

printf("删除的结点是：%d %d\n",p->next->node1,p->next->node2);

while(p->next!=NULL){

if(p->next->node1==mins->node1&&p->next->node2==mins->node2){

if(ST==NULL){

ST=p->next;

}

else{

End->next=p->next;

}

End=p->next;

End->next=NULL;

p->next=p->next->next;

printf("删除的结点是：%d %d\n",p->next->node1,p->next->node2);

break;

}

p=p->next;

}*/

previous=u;

u=mins->node2;

i=mins->part;

printf("最小的结点是%d,在第%d部分\n",u,i);

}

}

/*

5.2 如果i==k-1且叶子结点的lb值在表PT中最小，则输出该叶子结点对应的最优解；5.3 否则，如果i==k-1且表PT中的叶子结点的lb值不是最小，则

5.3.1 up=表PT中的叶子结点最小的lb值;

5.3.2 将表PT中目标函数值超出up的结点删除；

5.4 u=表PT中lb最小的结点的v值；

5.5 i=表PT中lb最小的结点的i值；i++;

*/

void Path(Graph G){//动态规划法

int i,j,temp=0;

int n=10;

int cost[10]; //存储子问题表的表格cost[i]表示从顶点i到终点n-1的最短路径

int path[10]; //存储状态,path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点

for(i=0;i

cost[i]=INFINITY;

path[i]=-1;

}

cost[G.vexnum-1]=0; //因为15到最后一个定点的距离0

for(i=n-2;i>=0;i--){

for(j=i+1;j<=n-1;j++){

if(G.arcs[i][j]+cost[j]<=cost[i]){

cost[i]=G.arcs[i][j]+cost[j];

path[i]=j;

}

}

}

i=0;

printf("动态规划法路径为：%d ",i);

while(path[i]<=n-1&&i

printf("->%d",path[i]);

i=path[i];

}

printf("\n");

printf("它的长度为：%d\n",cost[0]);

}

void main(){

Graph G;

int up;

CreateGraph(G);

printf("贪心法路径为：");

up=Greedy(G,0,0);

printf("它的长度为：%d\n\n",up);

Path(G);

//path(G,up);

}

书上的例子及运行其结果：

图1

由于时间有限，分支限界法有错误未能全部修改，到发论文的时刻还没有修改完毕，因此这里隐去了分支限界法的运行结果。文中的分析结论为研究实例以及具体运行过程得到：

然后我们同样对上图做测试，不过修改其中几个数据，将3->5的代价改为6，得到结果如下：

（范文素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）