1 引 言
1.1 问题背景
旅行商问题（Traveling Salesman Problem,以下简称TSP），是一个经典的NP难度的组合优化问题。其大意是：有若干个城市，任何城市之间的距离都是确定的，旅行商从某城市出发，必须经过每一个城市且只经过一次，最后回到出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。TSP问题目前是许多国家（如德国、日本、俄罗斯、英国、美国、法国）的运筹学工作者研究的热门课题[1]。
1.2 问题数学描述及研究综述
TSP问题是经典的NP Hard组合优化问题之一,求解该问题的启发式算法一直是数学，计算机科学研究的热点之一, TSP问题的形式化定义为:给定加权图G = (V,E,w),V为顶点集,|V| = n,E为边集,w:E→R+为边权函数,G中一个TSP环路就是一条不重复地访问Ｖ中所有顶点的Hamilton环路,记为T =〈V1,V2,…,Vｎ〉,其中对于任意满足 1≤i≤ｎ, 1≤ｊ≤ｎ, i≠ｊ,vi≠vj,有〈vi,v(i mod ｎ)+1〉∈E,记S(G)为G中所有TSP环路的集合.定义w(T)=w(〈v1,vｎ〉)+Σｗ(〈ｖ−=11niｉ,ｖｉ+1〉),要求权最小的TSP环路S* ,使得ｗ(S* )=minｓ∈ｓ(Ｇ)ｗ(ｓ)。该问题相关的最新综述参见文献[2]。
1.3 环路搜索空间
定义1：将完全TSP问题的环路用顶点序列列示出来，该顶点序列叫做一个TSP问题的环路表示。列示环路的方法叫做环路表示方法。以一个环路表示方法所对应的全部环路表示为元素的集合叫做该问题的一个环路搜索空间，简称搜索空间，用R(G)表示，其中G为TSP问题所对应的图。
定义2：一个完全TSP问题所对应的图中节点的总数称为此问题的问题规模。
定理1：规模为N的完全TSP问题用N个不同节点的任意排列表示一个环路时，对应的搜索空间的势为N!，该搜索空间称为最大搜索空间，以)(Gℜ表示。
证明：任何一个包含所有N个节点的排列都是一个环路表示，而所有这样的排列有N！个。
在各种TSP问题启发式算法中，例如遗传算法中，广为采用的就是最大搜索空间。
例1：如对于以下的四点完全TSP问题
-1-
可以用任一个由四节点组成的序列表示一个环路，例如环路表示1234就代表自顶点1出发顺次经过顶点2，顶点3和顶点4最终回到起始点1的一个回路，因此容易知道该TSP问题的搜索空间为：
R(G) = {1234,2341,3412,4123,
1243,2431,4312,3124,
1324,3241,2413,4132,
1342,3421,4213,2134,
1423,4231,2314,3142,
1432,4321,3214,2143}
该搜索空间的势为24。
图1 4点完全TSP问题
Fig.1 Complete TSP of 4
定义3： 具有相同Hamilton圈的环路彼此称为相关环路。
比如环路1234和环路2341，其Hamilton圈相同, 只是起点表示分别为1和2，故两个环路为相关环路。
定理2：相关概念具有传递性。即若L1与L2相关，而L2与L3相关，则L1与L3相关。
证明：因为他们具有相同的Hamilton圈。
定理3：对于完全TSP问题，中的任一环路L对应的Hamilton圈都有2N条相关环路。 )(Gℜ
证明：对于任一环路以下操作都可以获得一个与之相关的环路：
1）任取L中的节点k做为环路的起点，以k为基准，将左侧的线路片断依原序缀于其右侧线路片断的末尾。如此构成的新环路表示与L互为相关环路。L中每一个节点都对应一个这样的环路，故这样的相关环路有N条。
2）以上1）中获得的任一环路取倒序，也是L的一个相关环路。故又有N条与L相关的环路。
由于以上1）、2）获得的环路都与L相关，由定理1可知，这2N个环路彼此相关。
实际上正是因为有这2N条相关环路，使得现有的有关TSP问题算法的效率大打折扣。如果采用穷举的办法搜索TSP问题的解，就需要重复2N-1次相同的搜索。
定义4：两条完全TSP问题的环路L1和L2如果不是相关环路，则称两环路相互独立。相互独立的环路对应着不同的Hamilton圈。
比如环路L1：1234与环路L2：1324为相互独立的环路。
定义5：如果两个搜索空间R1(G)， R2(G)满足 R1(G)⊆ R2(G)，则称R1(G)为R2(G)的子空间。
定义6：在定义5中，若R1(G)中的环路彼此相互独立，则称R1(G)为最小环路搜索子空间，简称最小搜索空间（The Least Searching Space）。
定理4：完全TSP问题的最小搜索空间的势为(N-1)!/2。
证明：由定理3可知，中的任一环路L对应的Hamilton圈都有2N条相关环路。 )(Gℜ
而由定理1可知的势为N！故N！中的所有不相关的环路有N！/2N = (N-1)!/2条。 )(Gℜ
虽然我们知道最小环路空间的环路数量为(N-1)!/2，但是只有在能够不重复的罗列出这些环路时，这个结论才是有用的。
2 完全TSP问题最小环路空间的结构研究
在不增加其他约束（比如约束环路起点等）的条件下，如何找到TSP环路空间的最小搜索空间中环路的共同构造特点，使得其可描述、可构造，成为我们研究的主要问题。
定理5：任何环路均可表达为××……××M1××……××M2××……××M3 的形式，其中Mi∈V (i=1，2，3)，“×”代表除Mi之外的其他节点而且这种表达对于有序数组（M1，M2，M3）是唯一的。
证明：（略）。 -2-
三思论文代写网
定义7：满足定理5的三元有序数组（M1，M2，M3）叫做N点完全TSP问题的基元，Mi∈V (i=1，2，3)叫基元元素。
基元（M1，M2，M3）满足定理5的所有环路构成的集合用R M1M2M3(G)表示，则：
定理6：R M1M2M3 (G)是的环路子空间，且为最小环路子空间。 )(Gℜ
证明：首先由定理5可知R M1M2M3(G) 是)(Gℜ的环路子空间，又因为R M1M2M3(G)的元素（环路）是相互独立的，因此是最小环路子空间。
定理7：完全图G = (V,E,w)的基元总数为，其中N=|V|。 3NP
证明：任何三个元素的一个排列都可以做为基元，规模为N的完全TSP问题如此排列共有个，故完全图G = (V,E,w)的基元总数为。 3NP3NP
图2 不同最小搜索空间拓扑同构
Fig.2 Topological isomorphism space
推论2：完全图G = (V,E,w)不同基元的最小环路子空间共有个，其中N=|V|。 3NP
证明：每一个基元都对应一个最小搜索空间，因此由定理7可知命题成立。
定理8：不同基元构成的最小环路子空间彼此拓扑同构。
证明：其表达的都是同样的一个Hamilton圈集合，只是表示的方式不同而已。如图2所示。
定理9：完全TSP问题的最小环路子空间在拓扑同构的意义上是唯一的。
因此，在下面的讨论中不失一般性以R123 (G) 代表一般最小环路子空间。
如此我们找到了所有N阶完全TSP的搜索空间的环路构成特征。
定理5解决了最小搜索空间中的环路表达特征的描述问题。但是如何构造最小搜索空间呢？
若G⊕k代表在G中结点基础上再增加一个新结点k的完全TSP问题所对应的图则有：
定理10：R123 [Gk]= R⊕k⊗123 [G] ，此处“⊗”运算代表将结点K遍历的插入G对应的最小搜索空间集合R123 (G)的所有的环路的任二结点之间获得的含|G|+1个结点的新环路的操作，所有这些操作结果都是更高一级TSP问题最小搜索空间的元素之一。
证明（略）。
定理10表明，可以递推得得到任何TSP问题的最小搜索空间。
例如对于三点TSP问题，G={1，2，3}，则R123 [G] = {123} 对应的四点问题G⊕4={1，2，3，4}；其最小搜索空间R123 [G⊕K]= {4123，1423，1243}。即由三点最小搜索空间可以通过递推的方法构造四点TSP问题的最小搜索空间。
即K＋1点TSP问题的最小搜索空间，可以由K点TSP问题的最小搜索空间构造得来。
3 与普通搜索空间的对比
普通搜索空间的势为 N!, 完全表达出这些环路，需要如图3所示的搜索树，最小搜索空间（如图4）的势为(N-1)!/2 ,前者为后者的2N倍。差异十分明显。而且搜索空间的结构清晰，可以不重不漏的排出所有环路。
-3-
三思论文代写网
图3 四点TSP问题的普通搜索空间
Fig.3 The ordinary searching space of 4 nodes TSP
图4四点TSP问题最小搜索空间
Fig.4 The Least Routes Space of 4 nodes TSP
通常的最佳环路的确定性搜索方法只有两种，环路枚举搜索，和环路uniformcost Search搜索。最小搜索空间背景下的环路搜索由于搜索空间的缩小使搜索的效率大大提高。
例3 ：某四点问题，如图5所示
图5 4点TSP问题
Fig.5 A TSP of 4
如例1所示，采用传统的环路表达方法，其搜索空间为：
R(G) = {1234,2341,3412,4123,
1243,2431,4312,3124,
1324,3241,2413,4132,
1342,3421,4213,2134,
1423,4231,2314,3142,
1432,4321,3214,2143}
其中节点A用1表示节点B用2表示节点C用3表示节点D用4表示。
1） 采用uniformcost Search搜索方法进行搜索，过程如图6所示 [1]： -4-
三思论文代写网
图6 一个4点TSP问题uniformcost Search搜索方法
Fig.6 The uniformcost Search for a TSP of 4
获得最小环路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次比较即可获得最优环路，而且最优环路是唯一的。
由于搜索空间中仅有三条环路，获得最佳环路的效率为uniformcost Search搜索算法的1/5，为枚举搜索的1/8。其效果十分明显。对于规模为100的完全TSP问题，算法所需时间仅为原来的1/200；规模为1000点的TSP问题，其搜索空间仅为普通搜索空间的1/2000。因此规模越大的问题，其搜索空间的缩小越明显。
4 结论
对完全TSP问题最小搜索空间的研究是一个新的研究方向，为该类问题的研究提供了一个新视角。
经过研究，线路空间的结构得以彻底搞清。不但将环路表达唯一化，而且实现了基于问题规模递推的最小搜索空间获得方式，使最小搜索空间能够直接用于最优环路的搜索。
最小搜索空间的获得大大缩小了完全TSP问题的搜索空间。进一步的研究应该集中在如何将最小搜索空间应用于各种算法，以提高各算法的效率方面。
-5-
三思论文代写网
参考文献：
[1] http://219.226.9.43/Resource/CZ/CZSX/SXBL/SXJGS3/0005_MATH0008.htm
[2] Ma Liang. Review on the Research of Algorithms of TSP. Mathematics in Practice and Theory [J]. 1991. 30(2),156 ～ 165.
[3] 离散数学,耿素云 屈婉玲,北京大学出版社，2004年7月版。
Research on the least Searching Space of TSP
Li Qingyuan， Li Sujian
Department of Logistics Engineering,School of Mechanical Engineering,USTB,Beijing,PRC (100083)
Abstract
The unique expression of the routes of TSP is successfully been accomplished by means of the research on the construction of the TSP route searching space. The least searching space (LSS) of TSP is acquired. The searching space thus is narrowed to a little percent of the space commonly used and so the algorithm for TSP can be improved.
Keywords: optimization; searching space; redundancy routes; space construction; traveling salesman problem (TSP)
-6-
三思论文代写网 |
减小字体
增大字体