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

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

摘要：

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

关键字:

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

引言:

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

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

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

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

1、贪心法

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

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

Ｄiｊkstra算法就是一种最短路径算法，用于计算一个节点到其它所有节点得最短路径，动态路由协议OＳＰＦ中就用到了Diｊkstra算法来为路由计算最短路径。

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

Ｄijkstｒa算法得大概过程:

假设有两个集合或者说两个表,表A与表B

表A表示生成路径,表B表示最后确定得路径

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

2、将代价最小得代价值与这两节点移动到表B中（其中一个就是原点)。

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

4、重复第二步与第三步直到表Ａ为空．然后根据表Ｂ中得数据算出最优树。

维基百科中还有另一种说法,Ｄijksｔｒａ算法得输入包含了一个有权重得有向图G,以及Ｇ中得一个来源顶点S。?我们以V表示G中所有顶点得集合。?每一个图中得边，都就是两个顶点所形成得有序元素对。(u,v