http://acm.hdu.edu.cn/showproblem.php?pid=2224
貨郎問題(Traveling Salesman Problem，簡稱“TSP”)也叫貨郎擔問題，中國郵路問題，旅行商問題等,是計算機算法理論歷史上的經(jīng)典問題。在過去幾十年中，它成為許多重要算法思想的測試平臺，同時也促使一些新的理論領域的產(chǎn)生，比如多面體理論和復雜性理論。 貨郎問題：給定n個結點和任意一對結點{i，j}之間的距離為dist(i，j)，要求找出一條閉合的回路，該回路經(jīng)過每個結點一次且僅一次，并且該回路的費用最小，這里的費用是指每段路徑的距離和。 貨郎問題求解其精確解是NP難的，并且求解任意常數(shù)因子近以度的解也是NP難的。若將問題限定在歐氏平面上，就成為歐氏平面上的貨郎問題,也叫歐幾里德旅行商問題(Eculid Traveling Salesman Problem)。但是，即使是歐氏平面上的貨郎問題也是NP難的。因此通常用來解決TSP問題的解法都是近似算法。其中第一個歐幾里德旅行商問題的多項式近似算法是Arora在1996年使用隨機平面分割和動態(tài)規(guī)劃方法給出的。
J.L. Bentley 建議通過只考慮雙調(diào)旅程(bitonic tour)來簡化問題,這種旅程即為從最左點開始，嚴格地從左到右直至最右點，然后嚴格地從右到左直至出發(fā)點。事實上，存在確定的最優(yōu)雙調(diào)路線的O(n*n)時間的算法。
/**********************************************************************
* Bitonic path (詳見《算法導論》 P217)
* 一個人從p1嚴格地增的走到pn，然后再嚴格遞減的回到p1;求總路徑的最小值；
* 網(wǎng)上看到很多解題報告。。。看的我直冒汗
* 只好自己看書，翻譯。。。
* 對于1 <= i <= j <= n, 我們定義P(i, j)是一條包含了P1, P2, P3 …… Pj的途徑;
* 這條路徑可以分成2部分：遞減序列與遞增序列
* 起點是Pi(1 <= i <= j)，拐點是P1，終點是Pj, P[i, j]為其最小值；
* 狀態(tài)轉移方程為：
* b[1,2] = |P1P2|,
* i < j-1時， b[i,j] = b[i,j-1] + |Pj-1Pj| 點Pj-1在遞增序列中，
* i = j-1時， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 } 點Pj-1在遞減序列中
* b[n,n] = b[n-1,n] + |Pn-1Pn|
**********************************************************************/
#include <stdio.h>
#include <math.h>
#define INF 0x7fffffff
#define N 201
struct point{
double x, y;
}point[N];
int n;
double dis[N][N];
double distant(int i, int j)
{
return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
}
double dp()
{
int i, j, k;
double temp, b[N][N];
b[1][2] = dis[1][2];
for (j=3; j<=n; j++)
{
for (i=1; i<=j-2; i++)
b[i][j] = b[i][j-1] + dis[j-1][j];
b[j-1][j] = INF;
for (k=1; k<=j-2; k++)
{
temp = b[k][j-1] + dis[k][j];
if (temp < b[j-1][j])
b[j-1][j] = temp;
}
}
b[n][n] = b[n-1][n] + dis[n-1][n];
return b[n][n];
}
int main()
{
int i, j;
double ans;
while (scanf("%d", &n) > 0)
{
for (i=1; i<=n; i++)
scanf("%lf %lf", &point[i].x, &point[i].y);
for (j=2; j<=n; j++)
for (i=1; i<j; i++)
dis[i][j] = distant(i,j);
ans = dp();
printf("%.2lf\n", dp());
}
}
posted on 2009-11-30 18:38
西風蕭瑟 閱讀(6990)
評論(3) 編輯 收藏 引用 所屬分類:
動態(tài)規(guī)劃