论文部分内容阅读
TSP问题是非常著名的NP-complete问题,也几乎是每个算法课程都会谈论到的议题。如果给定一个完整的无向图形（undirected graph）-G,并以V表示顶点集合,以E表示两顶点间的边界,则此无向图形可用G=（V,E）表示。现在假设每个边界均有一个非负数的整数成本，在大多数的TSP形式里，其相当于要在G中找到一个使旅程之起点与终点均在同一顶点，并且对图形中所有顶点均要拜访过一次的一种汉弥顿环（Hamiltonian cycle）旅行路径。在许多情况里我们要找的不只是汉弥顿环，而且该环要是最短路