首页 > 代码库 > 双调巡游
双调巡游
问题
给定平面上n个点作为输入，求出连接所有n个点的最短巡游路线。
J.L.Bentley建议将问题简化，限制巡游路线为双调巡游，即从最左边的点开始，严格向右前进，直至最右边的点，然后调头严格向右前进，直至回到起始点。
设计一个O(n^2)时间的最优双调巡游路线算法，可以认为任何两点的x坐标均不同，且所有实数运算都花费单位时间（提示：从左至右扫描，对巡游路线的两个部分分别维护可能的最优解）。
- 将n个点按x坐标从小到大排序，时间复杂度为O(nlogn)；
- 用PATH(i,j)表示从点i严格向左到点1，再严格向右到点j的最短路径，路径包括从点1到点max(i,j)的所有点，因为PATH(i,j)==PATH(j,i)，所以只考虑i>=j时的情况；dir(i,j)表示从点i到点j的直接路径；
- 当i>j+1时，点i-1一定是小于i的最大节点，i-1>j，所以PATH(i,j)=PATH(i-1,j)+dir(i,i-1); i>j+1；
- 当i==j+1时，此时点i可能与小于i的所有节点相连，所以PATH(i,j)=min(PATH(k,j)+dir(i,k); k∈{x|x < i}；
-
初始值PATH(2,1)=dir(2,1)，计算PATH(i,j);
- 计算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;
}
双调巡游
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。