最短路径Floyd算法动态规划问题及其程序设计样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
最短路径动态规划问题及其程序设计

林旭东
(深圳大学　管理学院,广东　深圳　518060)
[摘　要]本文以最短路径问题为例,在给出佛洛伊德算法的基础上,设计了求解该算法的计算程序,这样可大大提高最短路径计算的效率。

[关键词]最短路径; 动态规划; 程序设计

1 　佛洛伊德算法
已知有n个顶点的有向图,佛洛伊德算法能够求解出每一对顶点之间的最短路径。假设使用邻接矩阵d ( i, j)来对图进行存储, d ( i, j)表示υi 到υj 之间的距离,可是该距离不一定是最短距离。佛洛伊德算法的基本思想是:为求顶点υi→υj 之间的最短距离,需要进行n次试探。首先将υ0 加入路[收稿日期] - 12 - 22[作者简介]林旭东(1972 - ) ,男, 湖北武汉人,深圳大学管理学院副教授,博士后,主要研究方向:数量模型与决策分析。径,考虑路径υi →υ0 →υj 是否存在,如果存在,则比较υi →υj和υi →υ0 →υj 的路径长度,取长度短的路径作为υi →υj 的路径,记作(υi ,υj ) 。接着在路径上再增加一个顶点υ1 ,比较υi→υ1 →υj 和(υi ,υj )的路径长度, 取长度短的路径作为(υi ,υj) 。不断将顶点υ2 ,υ3 , .,υn - 1加入进行试探, 最后得到的(υi ,υj )必定为υi →υj 的最短路径。若使用数组dk ( i, j)表示加入顶点k后,最短路径长度的变化情况,使用数组pk ( i, j)表示加入顶点k后,最短路径上顶点的变化情况,这样佛洛伊德算法就会产生一组d 0 ( i, j) ,d1 ( i, j) , ., dn - 1 ( i, j)和一组p0 ( i, j) , p1 ( i, j) , ., pn - 1 ( i, j) 。

R2 =
01314 014 01286 0
01197 01263 01394 01146
01211 01281 01392 01116
01231 01308 01346 01115 ,
R3 =
01367 01409 01224 0
01402 01412 01186 0
01367 01409 01224 0
01326 01435 01239 0 。
(2) 利用层次分析法确定指标权重:A = (01123, 01769,01108) ,
A1 = (01201, 01206, 01324, 01269) , A2 = (01189,01323, 01195, 01293) ,
A3 = (01203, 01286, 01168, 01343) 。
(3) 对Vi和U作综合评价。对Vi作综合评价,则有B1 =A1 ×R1 = (01356 8, 01380 3, 01222 2, 01040 6) , B2 = A2 ×R2= (01231 8, 01305 6, 01359 1, 01103 5) , B3 =A3 ×R3 = (01362 9,
01418 8, 01218 3)。对U作综合评价,则有B = A ×R = A ×[B1 ,B2 , B3 ]T = (01261 3, 01327 0, 01327 1, 01084 6) 。
(4) 计算综合评价值:W = B ×CT = 21765,表明广西北部湾经济区物流竞争力相对比较强,这主要得益于该区域优越的物流竞争环境和强的竞争潜力。因此, 广西北部湾经济区物流业有比较好的发展前景。

4 　结束语
实践表明,灰色综合评价法应用于区域物流竞争力的综合评价是有效的、 可靠的, 既能够评价一个区域物流竞争力所属的评价灰类,又能够对不同区域的物流竞争力进行选优排序,还能得出评价指标各组成要素的优劣排序, 所得评价信息可满足不同的评价需求。然而,同其它定量分析方法一样,灰色综合评价法对区域物流竞争力的评价, 仍有一定的局限性和不确定性。比如指标设置的代表性程度、 专家评分以及指标权重的确定等都具有一定的主观性和随机性。因此,在实际工作中应及时剔除突发因素的影响, 使模型评估结果更加符合实际。

主要参考文献
[ 1 ]姚建华. 物流产业竞争力评价指标体系研究[ J ]. 商业经济文荟, (1) : 20 - 23.
[ 2 ]李旭宏,李玉民,顾政华, 等. 基于层次分析法和熵权法的区域物流发展竞争态势分析[ J ]. 东南大学学报:自然科学版, , 34(3) : 398 - 401.
[3 ]谢如鹤,邱祝强,陈宝星. 区域物流产业竞争力指标体系及其应用
[ J ]. 工业工程, , 11 (1) : 109 - 112.
[ 4 ]邵万清. 物流产业评价指标与方法的探讨[ J ]. 物流科技, , 29(11) : 8 - 10.
[ 5 ]胡笙煌. 主观指标评价的多层次灰色评价法[ J ]. 系统工程理论与实践, 1996 (1) : 12 - 21.
[ 6 ]肖艳. 区域物流竞争力评价研究[D ]. 重庆:重庆大学机械工程学院, .
[ 7 ]苏飞,唐万生. 商业银行授信风险分析的灰色综合评价法[ J ]. 哈尔滨理工大学学报, , 9 (4) : 47 - 51.
[ 8 ]邓聚龙. 灰色系统理论教程[M ]. 武汉: 华中理工大学出版社,1991: 144 - 162.84经济管理

最后dn - 1 ( i, j)和pn - 1 ( i, j)就是顶点υi 到υj 之间的最短距离和相应路径。
2 　动态规划求解的佛洛伊德算法程序设计
如图1所示:给定一个线路网络,两点之间连线上的数字表示两点间的距离,求一条从A到E的路线,使总距离为最短。下面设计的程序要求用邻接矩阵存储图1 上三角阵。令υ1 ,υ2 , .,υ9 分别表示图1中点A, B1 , B2 , C1 , C2 , C3 , D1 ,D2 和E,则图1能够表示为(用99999表示∞) :

图1　动态规划的最短路径图

d ( i, j) =
99999 5 2 99999 99999 99999 99999 99999 99999
99999 99999 99999 3 7 99999 99999 99999 99999
99999 99999 99999 99999 6 3 99999 99999 99999
99999 99999 99999 99999 99999 99999 6 99999 99999
99999 99999 99999 99999 99999 99999 3 8 99999
99999 99999 99999 99999 99999 99999 99999 1 99999
99999 99999 99999 99999 99999 99999 99999 99999 3
99999 99999 99999 99999 99999 99999 99999 99999 7
99999 99999 99999 99999 99999 99999 99999 99999 99999

为了减少上述问题的计算工作量,我们编制求解动态规划算法的VBA程序如下:
Sub js ( )
Dim n, i, j, k As Integer
n = 9
Dim d (9, 9) , p (9, 9) , path (9) , distance As Integer
Rem将数据存于数组d ( i, j)中
For i = 1 To n
　For j = 1 To n
　　d ( i, j) =Cells ( i, j)
　Next j
Next i
For i = 1 To n
　For j = i + 1 To n
　　If d ( i, j) < 99999 Then
　　　d ( j, i) = d ( i, j)
　　End If
　Next j
Next i
Rem定义距离矩阵
For i = 1 To n
　For j = 1 To n
　　p ( i, j) = 0
　Next j
Next i
For i = 1 To n
　For j = 1 To n
　　If i = j Then
　　　p ( i, j) = 99999
　　Else
　　　p ( i, j) = i
　　End If
　Next j
Next i
Rem计算距离和路径
For k = 1 To n
　For i = 1 To n
　　For j = 1 To n
　　　If i < > j Then
　　　　If d ( i, k) + d ( k, j) < d ( i, j) Then
　　　　　d ( i, j) = d ( i, k) + d ( k, j)
　　　　　p ( i, j) = k
　　　　End If
　　　End If
　　Next j
　Next i
Next k
Rem输出距离和路径
distance = d (1, n)
For i = 1 To n
　path ( i) = 0
Next i
Count = 9
i = 1
While Count > 1
　path ( i) = p (1, Count)
　i = i + 1
　Count = p (1, Count)
Wend
Cells(20, 1) = distance
For i = 1 To n
　Cells (21, i) = path ( i)
Next i
End Sub

主要参考文献
[ 1 ]朱顺泉. 管理科学研究方法[M ]. 北京:清华大学出版社, .
[ 2 ]运筹学编写组. 运筹学[M ]. 北京:清华大学出版社, 1992.
[ 3 ]丁以中,等. 管理科学[M ]. 北京:清华大学出版社, .
[ 4 ]杨世胜. 计算机在企业管理中应用[M ]. 上海:上海交通大学出版社, 1985.85