旅行商问题的一种启发式算法

A heuristic algorithm for traveling salesman problem

用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.

A vector graph, composed of vertices and arcs, was adopted to express all the shortest paths to a vertex avoiding a certain city, and a linear list associated with each arc was defined to track the graphs including the corresponding arc. Thus, the problem whether a vertex or an arc is on the shortest path of a graph was turned to a linear list operation. With the method, the sufficient and necessary condition for all arcs in a graph lying on the shortest path was deduced. By generation of graphs at vertices from the first column to the n th column, the optimal approximate solution was found. As a conclusion, there are at most n - 1 graphs at each vertex, and at most n × （ n - 1） graphs for each column, therefore, not the graph G（v（Pk）￠Pk＋1,Pk＋2,…,Pn）, but the graph G（v（Pk）￠Pn） is needed to be obtained.