旅行商问题最小搜索空间研究

　　摘要： TSP问题之所以复杂，一个很重要的方面就是搜索空间中有大量的冗余环路，降低了搜索的效率。通过对普通搜索空间中冗余环路表达出现原因的分析和研究，构造出了新的搜索空间－最小搜索空间（LSS），在最小搜索空间中每个环路的表达形式是唯一的，从而消除了环路表达冗余现象，使搜索得以在只相当于原搜索空间2N分之一（N为结点数目）的空间内进行。然后进一步的对最小搜索空间的构造展开研究，实现了基于问题规模递推的最小搜索空间获得方式，扫清了最小搜索空间的应用障碍。在TSP问题求取最优解的确定性算法中与常用的Uniformcost Search算法进行了对比，效率相应提高了2N倍。
　　关键词： 最优化；搜索空间；冗余环路；空间结构；旅行商问题（TSP）
　　中图分类号：O157.6 文献标示码： A
　　
　　一、引 言
　　
　　旅行商问题（Traveling Salesman Prob