首页 > 代码库 > 中国邮路问题

中国邮路问题

中国邮递员问题      

一个邮递员送信,要走完他负责投递的所有街道(所有街道都是双向通行的且每条街道能够经过不止一次),完毕任务后回到邮局,应按如何的路线走,他所走的路程才会最短呢?

    

解决方式

1、图论建模

因为街道是双向通行的,我们能够把它看成是赋权无向连通图,将路口模型为点,街道模型为边,街道的长度就是每条边的权值,问题转化为在图中求一条回路,使得回路的总权值最小。

1.1最理想的情况

若图中有欧拉回路,由于欧拉回路通过全部的边,因此不论什么一个欧拉回路即为此问题的解。

1.2G仅仅有两个奇点Vi,Vj

则有从ViVj的欧拉迹,从Vj回到Vi则必须反复一些边,使反复边的总长度最小,转化为求从ViVj的最短路径。算法:

1) 找出奇点Vi,Vj之间的最短路径P

2) G’ = G + P

3) G’为欧拉图,G’的欧拉回路即为最优邮路。

1.3普通情况,奇点数大于2的时,邮路必须反复很多其它的边。

      Edmonds算法(匈牙利算法)

思想:

步骤:

1) 求出G全部奇点之间的最短路径和距离;

2) G的全部奇点为结点(必为偶数),以他们之间的最短距离为节点之间边的权值,得到一个全然图G1

3) M中的匹配边(ViVj)写成ViVj之间的最短路径经过的全部边集合Eij

4) G’ = G U { Eij | (Vi,Vj)属于M},则G’是欧拉图,求出最优邮路。

 

2、详细模块实现

2.1最短路径用 Dijkstra算法计算

Dijkstra算法是一种最短路径算法,用于计算一个节点到其他全部节点的最短路径。

2.1.1算法思想:

按路径长度递增次序产生最短路径算法:

  把V分成两组:

  1S:已求出最短路径的顶点的集合

  2V-S=T:尚未确定最短路径的顶点集合

T中顶点按最短路径递增的次序增加到S中,保证:

1)从源点V0S中各顶点的最短路径长度都不大于从V0T中不论什么顶点的最短路径长度

  2)每一个顶点相应一个距离值

  S中顶点:从V0到此顶点的最短路径长度

  T中顶点:从V0到此顶点的仅仅包含S中顶点作中间顶点的最短路径长度

 

2.1.2求最短路径步骤  

1)初始时令 S={V0},T={ 其余顶点}T中顶点相应的距离值  

     若存在<V0,Vi>d(V0,Vi)<V0,Vi>弧上的权值;若不存在<V0,Vi>d(V0,Vi)为∝  

2T中选取一个其距离值为最小的顶点W且不在S中,增加S  

3S中顶点的距离值进行改动:若加进W作中间顶点,从V0Vi的距离值缩短,则改动此距离值;

       反复上述步骤23,直到S中包括全部顶点,即W=Vi为止

 

2.2图的连通性測试

       检測用户输入的图是否是连通图,不是的话没办法求解,提醒用户又一次输入。分两种情况:

       1)先查找图中看是否有单点,假设存在,不连通,返回false

       2)对全部的顶点測试,假设存在顶点既不是单点,也不在连当前连通顶点集中,则表示存在多个连通分支,返回false

 

2.3计算奇点个数,处理奇点,利用奇点之间的完美匹配来确定反复边,使欧拉图具有最优邮路

 

2.4Fleury算法求最短欧拉回游

       如果迹wi=v0e1v1eivi已经选定,那么按下述方法从E-e1,e2,,ei}中选取边ei+1:

       1 ei+1vi+1相关联;

       2)除非没有别的边可选择,否则 ei+1不能是Gi=G-e1,e2,,ei}的割边。

       3)当(2)不能运行时,算法停止。

 

 代码没有弄完,看这个:

http://www.cnblogs.com/guocai/archive/2012/07/08/2581979.html

 

中国邮路问题