算法题 双调欧几里得旅行商问题

欧几里得旅行者问题是平面上给定的问题n确定连接图形各点的最短闭合行程的问题a给予，给予7点问题的解决。这个问题的一般形式是NP完全，所以它的解需要额外的多项式的时间。

J.L.Bentley建议简化问题，只考虑双色调行程，即从最左边的点开始，严格地从左到右一直到最右边的点，然后严格地从右到左直到起点的旅程。插图b显示相同显示相同显示相同7单点问题的最短双向调谐路径。在这种情况下，多项式时间算法是可能的。

描述确定以下各项的最佳双向调整路径O(n^2)时间算法。可以假设任何两个点x坐标都不一样。坐标是不同的。坐标都是不同的。

一个人从最左边的点开始，严格地从左到右一直走到最右边的点，然后从右到左直到起点，可以等同于两个人从最左边的点经过不同的路径，严格地从左到右，同时到达最右边的点。
假设这两个人是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 q1  
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