求解最优巡回路问题算法

《求解最优巡回路问题算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第7卷第6期2006年12月解放军理工大学学报(自然科学版)JournalofPLAUniversityofScienceandTechnologyV01．7No．6Dec．2006文章编号：1009—3443(2006)06—0553—04求解最优巡回路问题算法付成群1，刘建永2，孙叶钢1，陈文柏1(1．解放军理工大学工程兵工程学院，江苏南京210007；2．解放军理工大学科研部，江苏南京210007)摘要：为找一种简便、实用的求解最优巡回路的方法，在给定2个基本假设的前提下，在局部上运用Dijk—stra算法求出两顶点间的最

2、短旅行费，再求出各顶点间的最短旅行费，得到各节点间的有向图距离矩阵。在全局上运用匈牙利法求出全局最优巡回路，并对出现的局部回路问题进行了讨论，即建立了用“四阶段法”求解无数量限制的最优巡回路问题的算法。用无向图和有向图2个实例进行了计算，验证了求解无数量限制的最优巡回路问题的算法。关键词：Dijkstra算法；匈牙利法；最优巡回路中图分类号：TP301文献标识码：AAlgorithmonextendingquestionofoptimumcircuitrouteFUCheng—qunl，L，UJian—yon92，SUNYe—gan91

3、，CHENWen—bail(1．EngineeringInstituteofCorpsofEngineers，PLAUniv．ofSci．＆Tech．，Nanjing210007。China；2．DepartmentofScientificResearch，PLAUniv．ofSei．＆Tech．，Nanjing210007，China)Abstract：Inordertofindasimpleandefficientwaytoresolvethequestionofoptimumcircuitroute，un—dertwobasica

4、ssumptions，firstlytheDijkstraalgorithmwasappliedtoworkingoutthecostoftheshort—esttravelbetweentopsinpartanddistancematrixofgraphwitharrowbetweennodeswasobtained；andthenonthewholetheHungarymethodwasmadeuseoftoobtaintheoveralloptimumcircuitroute。andthequestionofpartcircuit

5、wasdiscussed．Finally，analgorithmnamedfour—phaseonextendingquestionofoptimumcircuitroutewasfounded，whichwasunlimitedbythenumberofnodes．Andcalculatingre—sultsshowthatthealgorithmisreliablethroughexamples．Keywords：Dijkstraalgorithm；Hungarymethod；optimumcircuitroute最优巡回问题的实质

6、是给定一个连通赋权图(非负权)，要找一个经过图中每个节点至少1次，而且总权最小的圈[1]。但在现实中，遇到的往往是求解有向图的最优巡回路问题，A到B的旅行费不等于B到A的旅行费，比如单行道问题等。本文以有向图为例进行讨论，无向图的问题可以看成有向图的特例，即Ⅳ(A—B)=W(A—B)，所以本文的解法对无向图同样适用。最优巡回路问题的最简单解法是枚举法，这种算法的好处是求解结果为最优解。但枚收稿日期：2006—05一11．作者简介：付成群(1975一)，男，讲师；研究方向：运筹与优化E—mail：fcq一7505@sohu．corn．举法

7、是按阶层递增的，运算量大，城市数量超过10个时就难以求解。采用分枝定界法求解时，在计算城市数量超过14个以上时就非常困难嘲。在实际中，通常运用一些近似算法，如划分几个局部区域，分区域进行求解，显然这种解法的误差很大嘲。1算法思想本文的算法思想是先从全局考虑，求得总体旅行费最小的巡回路啪，然后对解的可行性进行讨论和调整。通过调整，使之不出现直接回路和局部回路的解即为问题的满意解‘51。万方数据554解放军理工大学学报(自然科学版)第7卷2基本假设(1)顶点间的最小旅行费可以不是初等路定义1给定一个赋权有向图D一(y，A)，对于每一个弧岛一

8、(口i，，)，相应地，有权W(口)一甜玎，又给定2个顶点秽；和可，。设尸是D中从V，到珥的一条路，定义路尸的权是P中所有弧的权之和，记为W(P)。称P。为D中从口，到口，的最短路[6]，当P。满足W(P。)