最优Hamilton圈的一种新算法

An Analysis of a New Algorithm on Optimum Hamilton Cycle

提出了一种行之有效的执行算法——换顶算法，对无向图权值矩阵的数据进行有效处理，通过交换顶点来寻找一条较优Hamilton圈。在整个过程中，权值矩阵的上三角数据为有效数据，只需要按一定的顶点交换规则对这部分数据进行调整就可以达到优化Hamilton圈的目的。提出了交换规则的思想，且通过选择适当的规则，先判定可行性再执行交换算法，节省了大量的运算时间，降低了算法的时间复杂性。该算法也适用于Hamilton链的情况。

This paper establishes a useful algorithm vertex-exchange algorithm. Through exchanging vertexes, the authors redeploy the data in weight matrix of the undirected graph to find out a better Hamilton circle. In this process, data of up triangular part in weight matrix are valid data, which are manipulated according to an exchanging-rule to optimize the Hamilton cycle. The idea of exchanging-rule is put forward for the first time. The algorithm saves a lot of execution time and decreases the complexity of algorithm by choosing proper rules and order of operation. This algorithm also can be applied to Hamilton chain problems.