城市周游路线的次序表示方法

次序表示是取n 个城市的某个排列（p1，p2，…，pn），通常取（1，2，…，n）作为参照排列，然后将周游路线中的城市按照其在参照排列中的次序记录下来，形成一个具有n 个元素的有序表。具体做法如下：对给定的一条周游路线C=（c1，c2，…，cn），首先记录城市c1 在参照排列（p1，p2，…，pn）中的次序i1，将c1 从（p1，p2，…，pn）中删除得n-1个城市的参照排列（q1，q2，…，qn-1），再记录城市c2 在参照排列（q1，q2，…，qn-1）的次序i2，然后将城市c2从（q1，q2，…，qn-1）中删除，得n-2个城市的参照排列（r1，r2，…，rn-2），这样继续下去，直到城市cn 的次序in 记录下来为止。有序表（i1，i2，…，in）称为周游路线C=（c1，c2，…，cn）的次序表示。注意ij 的取值范围为1≤ij≤n-j+1。

例4-2 若取（1，2，…，9）作为参照排列，那么周游路线

1-2-4-3-8-5-9-6-7-1

的次序表示为：

(1 1 2 1 4 1 3 1 1)

反之，给定一个有序表（i1，i2，…，in），1≤ij ≤n-j+1，我们可如下确定n 个城市的一个排列（c1，c2，…，cn），即一条周游路线。显然c1 为参照排列（p1，p2，…，pn）中的第i1个城市，将c1 从（p1，p2，…，pn）中删除得参照排列（q1，q2，…，qn-1），则c2 为（q1，q2，…，qn-1）中的第i2 个城市，这样继续下去便可得（c1，c2，…，cn）。

例如，若取P=（1，2，…，9）作为参照排列，给定有序表L=（1 1 2 1 4 1 3 1 1）后，由L的第一个元素为1可知，P 的第一个城市1为所求周游路线的第一个城市，即与L 相应的部分周游路线为：

(1# # # # # # # #)

其中#表示尚未确定的城市。

从P 中删除城市1得P1=（2，3，4，5，6，7，8，9），由L 的第2个元素为1知，所求周游路线的第二个城市为P1 中的第一个城市2，可得部分周游路线为：

(1 2 # # # # # # #)(www.xing528.com)

从P1 中删除城市2后得P2=（3，4，5，6，7，8，9），再由L 的第3个元素为2知，所求周游路线的第三个城市为P2 中的第二个城市4，可得部分周游路线为：

(1 2 4 # # # # # #)

这样继续下去，最终可得周游路线为（1 2 4 3 8 5 9 6 7）。

次序表示的主要优点是可以使用传统的杂交算子，即可以使用二进制表示的点式杂交。这是因为对于任意两个父体：

若选定杂交点k，将两父体在杂交点k 右边的对应元素相互交换得：

p1′=(i1,i2,…,ik,jk+1,…,jn)=(s1,s2,…,sn),1≤sk≤n-k+1,k=1,2,…,n

p2′=(j1,j2,…,jk,ik+1,…,in)=(t1,t2,…,tn),1≤tk≤n-k+1,k=1,2,…,n

由上面的讨论知，p1′、p2′是合法的次序表示。对多点杂交也有类似的结论。

虽然次序表示具有可以使用传统杂交算子的优点，但实验表明在次序表示的基础上使用单点杂交算子所得到的结果不能令人满意[5]。