双调巡游

问题

给定平面上n个点作为输入，求出连接所有n个点的最短巡游路线。

J.L.Bentley建议将问题简化，限制巡游路线为双调巡游，即从最左边的点开始，严格向右前进，直至最右边的点，然后调头严格向右前进，直至回到起始点。

设计一个O(n^2)时间的最优双调巡游路线算法，可以认为任何两点的x坐标均不同，且所有实数运算都花费单位时间（提示：从左至右扫描，对巡游路线的两个部分分别维护可能的最优解）。

1. 将n个点按x坐标从小到大排序，时间复杂度为O(nlogn)；
2. 用PATH(i,j)表示从点i严格向左到点1，再严格向右到点j的最短路径，路径包括从点1到点max(i,j)的所有点，因为PATH(i,j)==PATH(j,i)，所以只考虑i>=j时的情况；dir(i,j)表示从点i到点j的直接路径；
3. 当i>j+1时，点i-1一定是小于i的最大节点，i-1>j，所以PATH(i,j)=PATH(i-1,j)+dir(i,i-1); i>j+1；
4. 当i==j+1时，此时点i可能与小于i的所有节点相连，所以PATH(i,j)=min(PATH(k,j)+dir(i,k); k∈{x|x < i}；

5. 初始值PATH(2,1)=dir(2,1)，计算PATH(i,j);

6. 计算PATH(n,n)=min(PATH(n,k)+dir(n,k));

// bitonic_tours.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<cmath>
#define maxline 7
#define Large 100
using namespace std;

struct point
{
	double x;
	double y;
};

double dir(point p1, point p2)
{
	return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

double tour(point* p)
{
	//初始化
	double path[maxline + 1][maxline + 1];
	for (int i = 0; i <= maxline; i++)
		for (int j = 0; j <= maxline; j++)
			path[i][j] = Large;
	path[2][1] = dir(p[2], p[1]);
   //做i>j的循环
	for (int i = 3; i <= maxline; i++) {
		for (int j = 1; j < i; j++)
   //情况3
			if (i > j + 1)
				path[i][j] = path[i - 1][j] + dir(p[i - 1], p[i]);
   //情况4
			else if(i==j+1) {
				double min = Large;
				for (int k = 1; k < i; k++)
					if (path[j][k] + dir(p[k], p[i]) < min)
						min = path[j][k] + dir(p[k], p[i]);
				path[i][j] = min;
			}
	}
	//求出从所有i-j的链后，最后直接连接i-j形成闭环，求最短闭环
	double min2 = Large;
	for (int k = 1; k < maxline; k++) {
		if (path[maxline][k] + dir(p[maxline], p[k]) < min2)
			min2 = path[maxline][k] + dir(p[maxline], p[k]);
	}
	path[maxline][maxline] = min2;
	return min2;
}

int main()
{
	point p[8] = { {0,0},{ 1,1 },{ 1.5,0.5 },{ 2,2.2 },{ 3,0.4 },{ 3.4,5 },{ 4,0.7 },{ 5,0.4 } };
	cout << tour(p);
	while (1);
    return 0;
}