双调欧几里得旅行商问题【转载】

秒速五厘米 2021-11-17 12:52 226阅读 0赞

欧几里德旅行商问题是对平面上给定的n个点的确定一条连接各点的最短闭合旅程的问题。图a给出了一个7个点问题的解。这个问题的一般形式是NP完全的，故其解需要多余多项式的时间。

J.L.Bentley建议通过只考虑双调旅程来简化问题，这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。图b显示了同样的7个点问题的最短双调路线。在这种情况下，多项式时间的算法是可能的。

描述一个确定最优双调路线的O(n^2)时间的算法。可以假设任何两点的x坐标都不相同。

[![双调欧几里得旅行商问题【转载】 - kevinlee\_2010 - 云淡风轻][- kevinlee_2010 -]][- kevinlee_2010 -]

一个人从最左点开始，严格地从左到右直至最右点，然后从右到左直至出发点，可以等价为两个人同时从最左点，严格地从左到右经历不同路径到达最右点。  
假设这两个人为A和B，且A总是走在B后面。设Pij表示A走到pi、B走到pj时两人所经过的最短双调路径，根据假设，可得i<=j。又设b\[i, j\]表示最短双调路径Pij的长度，d\[i, j\]表示点pi到点pj的直线距离，则：  
b\[1, 2\]=d\[1, 2\]  
当i=j时，即A和B处于同一点，b\[i, j\]=b\[i, i\]=b\[i-1, i\]+d\[i-1, i\]  
当i=j-1时，即A在B紧邻的靠后一点，b\[i, j\]=b\[j-1, j\]=min(1<=k<j-1)\{b\[k, j-1\]+d\[k, j\]\}  
当i<j-1时，即A在B后且相隔多个点，b\[i, j\]=b\[i, j-1\]+d\[j-1, j\]

由几何学知识可得，如果中间路径A和B经历了同一点，则这条路径肯定不是最短路径，故i=j的情况只可能用来计算b\[n, n\]=b\[n-1, n\]+d\[n-1, n\]。  
定义r\[i, j\]表示双调路径Pij上，点p\[j\]的前驱点的下标。下面的伪代码就展示了b\[i, j\]和r\[i, j\]的计算方法：

EUCLIDEAN-TSP(p)  
n<-Length\[p\]  
SORT(p, 1, n)  
for i<-1 to n  
    do for j<-1 to n  
           do d\[i, j\]<-|p\[i\]p\[j\]|  
b\[1, 2\]=d\[1, 2\]  
for j<-3 to n  
    do for i<-1 to j-2  
           do b\[i, j\]<-b\[i, j-1\]+d\[j-1, j\]  
              r\[i, j\]<-j-1  
       b\[j-1, j\]<-∞  
       for k<-1 to j-2  
           do q<-b\[k, j-1\]+d\[k, j\]  
              if q<b\[j-1, j\]  
                  then b\[j-1, j\]<-q  
                       r\[j-1, j\]<-k  
b\[n, n\]<-b\[n-1, n\]+d\[n-1, n\]  
r\[n, n\]<-n-1  
return b and r

PRINT-TOUR(p, r, n)  
print p\[n\]  
print p\[r\[n\]\[n\]\]  
PRINT-PATH(p, r, k, n-1)  
print p\[r\[n-1\]\[n\]\]

PRINT-PATH(p, r, i, j)  
if i<j  
    then k<-r\[i, j\]  
         print p\[k\]  
         if k>1  
             then PRINT-PATH(p, r, i, k)  
    else k<-r\[j, i\]  
         if k>1  
             then PRINT-PATH(p, r, k, j)  
                  print p\[k\]

转载于:https://www.cnblogs.com/kevinLee-xjtu/archive/2011/12/06/2299100.html

[- kevinlee_2010 -]: /images/20211116/add3b9aaa72345fabb1ebae542cfffa9.png