首页 > 代码库 > 双调欧几里德旅行商问题

双调欧几里德旅行商问题

2024-07-06 14:44:31   224人阅读

双调欧几里得旅行商问题是一个经典动态规划问题。《算法导论（第二版）》思考题15-1和北京大学OJ2677都出现了这个题目。

旅行商问题描述：平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）

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

上图中，a是最短闭合路线，这个路线不是双调的。b是最短双调闭合路线。

求解过程，算法导论官网上已给出来了，而且是写的最好的。




下面已杭电2604为例，贴出已经AC的代码
//双调欧几里德旅行商算法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
    int x;
    int y;
};
#define MAXSIZE 202
int number;       //点的个数
point a[MAXSIZE];
double d[MAXSIZE][MAXSIZE];

double straight(point m,point n)
{
    double i=(double)(m.x-n.x)*(m.x-n.x);
    double j=(double)(m.y-n.y)*(m.y-n.y);
    return sqrt(i+j);

}
bool compare(point m,point n)
{
    return m.x<n.x;
}
int main()
{
    int i,j,k;
    //freopen("a.txt","r",stdin);
    while(cin>>number)
    {
        for(i=0;i<number;i++)
            cin>>a[i].x>>a[i].y;
        //先排序
        sort(a,a+number,compare);
        //计算状态关系集d[i][j]
        d[1][1]=0;
        for(i=2;i<=number;i++)
        {
            for(j=1;j<=i;j++)
            {
                if(j==i-1)
                {
                    d[i][j]=d[j][1]+straight(a[0],a[i-1]);
                    for(k=2;k<=j-1;k++)
                    {
                        if(d[j][k]+straight(a[k-1],a[i-1])<d[i][j])
                            d[i][j]=d[j][k]+straight(a[k-1],a[i-1]);
                    }

                }
                else if(j==i)
                {
                    d[i][i]=d[i][1]+straight(a[0],a[i-1]);
                    for(k=2;k<=j-1;k++)
                    {
                        if(d[i][k]+straight(a[k-1],a[i-1])<d[i][i])
                            d[i][j]=d[i][k]+straight(a[k-1],a[i-1]);
                    }
                }
                else
                    d[i][j]=d[i-1][j]+straight(a[i-2],a[i-1]);
            }

        }
        printf("%.2lf\n",d[number][number]);

    }

}




联系
我们