最优Hamilton圈的一种新算法

摘要

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