通运输上使用动态规划求解最短路径.pdf

《通运输上使用动态规划求解最短路径.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、袁佳乐1黄兆华2YuanJialeHuangZhaohua(I．西安文理学院计算机科学系，陕西西安710065；2．华东交通大学信息学院，江西南昌330013)(1．DepartmentofComputerScience，Xi’anUniversityofArtandScience，Shanxixi’an701165；2．SchoolofInformationEng．，EastChinaJiaotongUniversity，JiangxiNanchang330013)摘要：随着我国交通运输事业的发展．降低运输成本成为

2、日益关注的问题。动态规划在工程技术、经济管理、工业生产、交通运输等众多领域都有广泛的应用．其中最短路径问题是动态规划在管理领域的一个重要应用。本文通过具体实例说明动态规划在交通运输方面求解最短路径的过程．方法简便，思路清晰。关键词：交通运输：动态规划：最短路径，中图分类号：TP311文献标识码：A文章编号：1671—4792一(2008)5一008l-02Abstract：Alongwiththetransportationsystemdevelopment，peopleputnloreattentiontorele

3、asetheexpenseintransportation．Dynamicprogramminghasalreadyapplledtoprojecttechnique，economymanagement．industryproductionandtraffictransportation．Theproblemoftraffictransportationisanimportanceapplicationinthefieldofdynamicprogramming．Thepaperusedynamicprogrammi

4、ngtheoriestosearchtheshortestrouteinthetransportationsystem，theideaisclearandthetheoryisreliable．Kevwords：Transportation；DynamicProgramming；ShortestRoute0引言’随着国际油价的不断上涨，日益冲击着我国的交通运输事业。如何能快速的找到两地之间的最短路径，加快交通运输速度，提高服务质量，降低交通运输中的成本，增加经济效益成为运输公司和运输个体经营户关心的问题。在交通运输示

5、意图中(见图一)，有n个结点a，、a，、a，⋯⋯a。，计算从点a，到点a．之间的最短路径。常用d，。表示点a。到点a。之间的距离，如果两地间没有通路，则d；l'*，用z’(a；)表示从a。点到终点a．的最短路径。假设点a。可以通过点f1．到达终点a．，点a。到点a；的距离为d¨从a。点到达终点a。的最短路径为Z’(a；)，则由点a。到达终点的最短路径可表示为z’(a．)=min{d，。q-Z‘(a。))。把网络中的结点按离终点最多的步数划分为k个集合，为满足动态规划方法中阶段“无后效性”的限制，在阶段与阶段的空处添加

6、若干个虚结点，对于每个添加的虚结点，使之满足从该虚结点到其后结点的值为原路径的数值，从前一结点到该虚结点的值为0。Zk。(a。)表示从第k阶段的点a．到终点a．的最短路径，可列出方程：z。’(a。)=min{d。．+z。‘(a；))(1)Z。．。’(a)--O(2)其中，i

7、结点间的连线代表两地之闻有通路，其上的数值表示两地之问的距离，如果图中两点问没有连线则说明这两个地区还没有建设通路。运用动态旁劲各径，⑤集合x。=“)。它最多四步就可以到达结点A7；薯l岛终点～最；．5个集如图所示将问题划分为四个阶段，即k=4．由公式(2)可得Z。‘(A7)：o．在①集合x5-一，；先求第四个阶段：交②集合×4-J通又s,7；Z4‘(A5)=12+Zs。沁)=12x4‘=^7运⑦集合x3--．z4‘(A3)=2+z5‘(A，)---2X4‘=A7输④集合x2-＆～，；z4‘(B。)=4+zs‘(A，

8、)=4x4’=A7上④集合Xl=再求第三个阶段：使：第一阶l_Z3。(B2)=8+z4。(As)=8+12=20x3‘=As用Iz3。(B3)=9+z4‘(A)---9+2=IIx3‘=Aa动l态：rz。‘(B4)=lo+z。’(A3)=10+2=I2x3‘=～规z3’(A6)铷in／6屹4’(A3)=6+2=8划(≯，＼，习眦。饥，4L≮詈’