对双调欧几里得旅行商问题的一些思考

问题简述

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

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

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

题意解读

  假设在一个平面上有n个点。我们先假设它们是按$x$坐标单调递增排序的。也就是说,设这些点的集合为$P$,大小为$n$,其中特定的点可用$P_i(x_i,y_i)$来表示。那么当$1 \le i \lt j \le n$时,$x_i \lt x_j$。欧几里得旅行商问题就是从$P_1$出发,访问了所有的节点后,又返回到了$P_1$,但要注意的是每个节点仅访问一次。对于双调欧几里得旅行商问题来说,多出了一些约束。首先,$P_n$必须为访问路径上的最右端的节点。然后到达$P_n$前,访问的节点的$x$坐标必须是越来越大的。比如说,如果现在访问的节点是$P_i$,那么下一个要访问的节点必须是$P_j$,其中$j \gt i$。当访问到最右节点$P_n$后,这个约束又反了过来。这时访问的节点的$x$坐标必须越来越小。比如说,如果现在访问的节点是$P_i$,那么下一个要访问的节点必须是$P_j$,其中$j \lt i$。

求解方法

原始方法

最优子结构

  首先肯定是把点按$x$坐标进行从小到大排序。假设排序后的序列为$P_1, P_2, P_3, … , P_n$。$d_{ij}$为从$P_i$到$P_j$的距离。

  可以把所要求的闭合回路转换成两条从最左端节点到最右端节点的两条路径。它们除了起点和终点以外没有共同的节点,并且两条路径上所经过节点的并集为整个平面上的节点。那么我们可以假设有两条除了起点和终点以外无任何的公共节点,起始点为最左端的节点$P_1$的路径$Path$和$Path^*$。然后可以用$B_{i,j}$表示,终止节点为$P_i$的$Path$的旅程和终止节点为$P_j$的$Path^$的旅程之和的最小值。而$Path$和$Path^\$的并集就是从$P_1$到$P_{ max \lbrace i, j \rbrace }$的所有节点。那么这时候$Path$和$Path^*$上的节点的$x$坐标都分别是严格地从小到大。显而易见,$B_{n,n}$即为我们所需要的闭合双调旅程的长度。于是现在的目标函数如下

  现在就可以看成这两条路径都是从$P_1$生长出来,可以假定$Path$的生长速度不大于$Path^$的生长速度。也就是说在$B_{i,j}$中$i$永远都不大于$j$。于是这时候就是$Path^\$先生长到$P_n$节点。那么现在目标函数就如下

  因为$d_{i,n}$易得,就是$P_i$和$P_n$两点间的距离而已。所以现在的目标是求出$B_{i,n}$。也就是要求$B_{i,j}$,当$j = n$时就为$B_{i,n}$。那么因为$1 \le i \le j \le n$。于是可以分为三种情况

  情况一 当$i \lt j - 1$时,$i \lt j - 1 \lt j$。因为$Path$的最后一个节点是$i$,而$Path^*$的最后一个节点是$j$,又因为$Path$和$Paht^*$的并集就是从$P_1$到$P_{max{\{i,j\}}}$的所有节点。也就是说,$P_{j - 1}$这个节点要么在$Path$要么在$Path^*$上。又因为$Path$和$Path^*$上的节点的$x$坐标都分别是严格地从小到大,那么$P_{j - 1}$只能在$Path^*$上,因为$Path$的最后一个节点是$P_i$,而$P_{j - 1}$的x坐标比$P_i$大,不符合约束。于是可以得到以下递推公式。

  情况二 当$i = j - 1$的时候。这种情况就比较复杂一些。因为$B_{i,j}$是$Path$和$Path^*$旅程和的最小值,设$1 \le k \lt j - 1$,那么肯定存在一个$P_k$在$Path^*$上。注意这时候$i = j - 1$,所以$P_{j - 1}$肯定不在$Path^*$上。所以

  在上式中,因为$k \lt j - 1 = i$,也就是说需要的一部分最优子结构违反了我们的约束,需要$Path$的增长速度比$Path^*$快。但好在$B$有个美妙的性质,它是对称的。因为$B_{i,j}$就是两条符合约束的分别以$P_i$和$P_j$为终点的路径的最小距离和。$B_{i,j} = B_{j,i}$。如果$B$是个$i$行$j$列矩阵的话,我们只需要上三角。所以递推式可以改为

  情况三 当$i = j $的时候。这种情况当且仅当$i = j = n$时才会出现,也就是说这时候已经组成闭合曲线了,也就是我们的目标函数$B_{n,n}$,

复杂度分析

  情况一有$O(n^2)$次进入,但每次处理时间是常数时间,所以,情况一的复杂度是$O(n^2)$。情况二有$O(n)$次进入,每次处理时间是$O(n)$。所以情况二的复杂度是$O(n^2)$。情况三就一次进入,也就是当$i = j = n$的时候,处理时间为$O(n)$。所以整体的复杂度为$O(n^2)$。
  具体来讲$Path^*$,当$j = 1$时,就是只有一个点,这时就是个常数项的时间,因为只是个赋值而已。当$j$从$2$生长到$n$。每次生长,都会发生情况一和情况二。最后一次增长会触发情况三。情况一每次都会发生$Path$从$i = 1$到$i = j-2$的增长。情况二每次都会计算最优解,而这个过程需要$j - 2$次。情况三发生后,会进行$n - 1$次的计算。于是复杂度为

优化

  根据约束$P_n$肯定是会和$P_{n-1}$相连,于是我们不妨设$P_{n-1}$在$Path$上,那么现在的目标函数,或者说情况三就是

最终验证和代码

  我们采用杭州电子科技大学的oj平台上的2224题进行验证。它的题目有些问题,它说输入的点的坐标是整数,但最终它的用例却用的double….这浪费了我的好长时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <math.h>
#include <float.h>
class Point{
public:
double x;
double y;
Point(double _x,double _y) : x(_x),y(_y){}
Point(){}
};
double getDistance(Point *pointA,Point *pointB){
return sqrt((pointA->x - pointB->x) * (pointA->x - pointB->x)
+ (pointA->y - pointB->y) * (pointA->y - pointB->y));
}
double min(double a,double b){
if(a < b){
return a;
}
return b;
}
double dp[200][200];
double solve(Point *point, int size){
dp[0][0] = 0;
for(int j = 1,i;j < size;j ++){
for(i = 0;i < j - 1;i ++){ //情况一
dp[i][j] = dp[i][j - 1] + getDistance(point + j - 1, point + j);
}
//情况二
i = j - 1;
dp[i][j] = FLT_MAX;
int k = 0;
do{
dp[i][j] = min(dp[i][j], dp[k][i]
+ getDistance(point + k, point + j));
k++;
}while (k < j - 1);
}
return dp[size - 2][size - 1]
+ getDistance(point + size - 2, point + size - 1);//情况三
}
int main(int argc, const char * argv[]) {
int pointNum;
Point points[200];
while(scanf("%d",&pointNum) == 1){
for(int i = 0;i < pointNum;i ++){
scanf("%lf %lf",&points[i].x,&points[i].y);
}
double result = solve(points,pointNum);
printf("%.2lf\n",result);
}
return 0;
}