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

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

关键词： 最优化；搜索空间；冗余环路；空间结构；旅行商问题（TSP）

中图分类号：O157.6 文献标示码： A

一、引 言

旅行商问题（Traveling Salesman Problem,以下简称TSP），是一个经典的NP难度的组合优化问题。其大意是：有若干个城市，任何城市之间的距离都是确定的，旅行商从某城市出发，必须经过每一个城市且只经过一次，最后回到出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。TSP问题目前是许多国家（如德国、日本、俄罗斯、英国、美国、法国）的运筹学工作者研究的热门课题[1]。

定义1： 具有相同Hamilton圈的两个环路彼此称为相关环路，否则称为相互独立环路。

定理1：对于完全TSP问题，R(G)中的任一环路L对应的Hamilton圈都有2N条相关环路。其中R(G)为节点全排列构成的环路空间。

证明：对于任一环路以下操作都可以获得一个与之相关的环路：

1）任取L中的节点k做为环路的起点，以k为基准，将左侧的线路片断依原序缀于其右侧线路片断的末尾。如此构成的新环路表示与L互为相关环路。L中每一个节点都对应一个这样的环路，故这样的相关环路有N条。

2）以上1）中获得的任一环路取倒序，也是L的一个相关环路。故又有N条与L相关的环路。

由于以上1）、2）获得的环路都与L相关，由定理1可知，这2N个环路彼此相关。

定义2：如果两个搜索空间R1(G)， R2(G)满足 R1(G)R2(G)，则称R1(G)为R2(G)的子空间。若R1(G)中的环路又彼此相互独立，则称R1(G)为最小环路搜索子空间，简称最小搜索空间（LSS，The Least Searching Space）。

定理2：完全TSP问题的最小搜索空间的元素总数为(N-1)!/2。

证明：由定理1可知，R(G)中的任一环路L对应的Hamilton圈都有2N条相关环路。

而R(G)空间中的元素总数为N！，故N！中的所有不相关的环路有N！/2N=(N-1)!/2条。

虽然我们知道最小环路空间的环路数量为(N-1)!/2，但是只有搞清最小搜索空间的结构，使得其可描述、可构造，也即可以将空间中的元素秩序化，才能得到应用。

二、完全TSP问题最小环路空间的结构研究

定理3：任何环路均可表达为××……××M1××……××M2××……××M3 的形式，其中Mi V (i=1，2，3)，“×”代表除Mi之外的其他节点而且这种表达对于有序数组（M1，M2，M3）是唯一的。

证明：（略）。

定义3：满足定理3的三元有序数组（M1，M2，M3）叫做N点完全TSP问题的基元，Mi V (i=1，2，3) 叫基元元素。

基元（M1，M2，M3）满足定理5的所有环路构成的集合用R M1M2M3(G)表示，则：

定理4：R M1M2M3 (G)是R(G)的环路子空间，且为最小环路子空间。

证明：首先由定理5可知R M1M2M3(G) 是R(G)的环路子空间，又因为R M1M2M3(G)的元素（环路）是相互独立的，因此是最小环路子空间。

定理5：完全图G = (V,E,w)的基元总数为 ，其中N=|V|。

证明：任何三个元素的一个排列都可以做为基元，规模为N的完全TSP问题如此排列共有 个，故完全图G = (V,E,w)的基元总数为 。

推论1：完全图G = (V,E,w)不同基元的最小环路子空间共有 个，其中N=|V|。

证明：每一个基元都对应一个最小搜索空间，因此由定理5可知命题成立。

定理6：不同基元构成的最小环路子空间彼此拓扑同构。

证明：只要证明可以在两个空间中建立双射（即满且单）即可。

定理7：完全TSP问题的最小环路子空间在拓扑同构的意义上是唯一的。

定理3解决了最小搜索空间中的环路表达特征的描述问题。但是如何构造最小搜索空间呢？经过研究我们获得了若干构造最小搜索空间的办法，以下仅列举一种。

若G k代表在图G中结点基础上再增加一个新结点k的完全TSP问题所对应的图则有：

定理8：R123 [kG]= R123 [G] ，此处“ ”运算代表将结点K遍历的插入G对应的最小搜索空间集合R123 (G)的所有的环路的任二结点之间获得的含|G|+1个结点的新环路的操作，所有这些操作结果都是更高一级TSP问题最小搜索空间的元素之一。

证明（略）。

即K＋1点TSP问题的最小搜索空间，可以由K点TSP问题的最小搜索空间构造得来。

三、与普通搜索空间的对比

普通搜索空间如图1所示，最小搜索空间如图2所示。通常的最佳环路的确定性搜索方法只有两种，环路枚举搜索，和环路uniformcost Search搜索。最小搜索空间下的环路搜索由于搜索空间的缩小使搜索的效率大大提高。

例3 ：某四点问题，如图3所示

获得最小环路ABCDA和ADCBA长度皆为12。实际上这是两条相关环路。

需要15次加操作和14次比较才能获得最优环路，而且最优环路还有相关环路（即实际上为同一Hamilton圈的重复环路表达）。

2）采用枚举搜索，则需要逐一计算R(G)中的环路长度需要24次加操作和23次比较操作才能获得最优解。同样最优环路有许多相关环路。

3）采用最小搜索空间R123 (G) = {4123, 1423,1243}进行搜索，

设环路长度函数为L（R），三环路分别为R1，R2，R3则：

L（R1）＝L（4123）＝12，

L（R2）＝L（1423）＝16，

L（R3）＝L（1243）＝16，

故最短环路为R1＝4123，即DABC，路径总长为12。

由于最小环路空间的构造过程仅仅是一种排列过程无需加总比较操作，因此仅需要3次加操作和2次比较即可获得最优环路，而且最优环路是唯一的。

四、结论

对完全TSP问题最小搜索空间的研究是一个新的研究方向，为该类问题的研究提供了一个新视角。

经过研究，线路空间的结构得以彻底搞清。不但将环路表达唯一化，而且实现了基于问题规模递推的最小搜索空间获得方式，使最小搜索空间能够直接用于最优环路的搜索。

最小搜索空间的获得大大缩小了完全TSP问题的搜索空间。进一步的研究应该集中在如何将最小搜索空间应用于各种算法，以提高各算法的效率方面。

作者单位：北京科技大学机械工程学院物流工程系

参考文献：

[1] 219.226.9.43/Resource/CZ/CZSX/SXBL/SXJGS3/0005_MATH0008.htm.

[2] Ma Liang. Review on the Research of Algorithms of TSP[J]. Mathematics in Practice and Theory, 1991,30(2):156 -165.

[3]耿素云 屈婉玲. 离散数学[M].北京：北京大学出版社，2004.