求解最优巡回路问题算法

为找一种简便、实用的求解最优巡回路的方法,在给定2个基本假设的前提下,在局部上运用D ijkstra算法求出两顶点间的最短旅行费,再求出各顶点间的最短旅行费,得到各节点间的有向图距离矩阵。在全局上运用匈牙利法求出全局最优巡回路,并对出现的局部回路问题进行了讨论,即建立了用“四阶段法”求解无数量限制的最优巡回路问题的算法。用无向图和有向图2个实例进行了计算,验证了求解无数量限制的最优巡回路问题的算法。

Algorithm on extending question of optimum circuit route

In order to find a simple and efficient way to resolve the question of optimum circuit route,under two basic assumptions,firstly the Dijkstra algorithm was applied to working out the cost of the shortest travel between tops in part and distance matrix of graph with arrow between nodes was obtained;and then on the whole the Hungary method was made use of to obtain the overall optimum circuit route,and the question of part circuit was discussed.Finally,an algorithm named four-phase on extending question of optimum circuit route was founded,which was unlimited by the number of nodes.And calculating results show that the algorithm is reliable through examples.