http://acm.hdu.edu.cn/showproblem.php?pid=2224
      货郎问题(Traveling Salesman Problem,简称“TSP”)也叫货郎担问题,中国邮路问题,旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中,它成为许多重要算法思想的测试平台,同时也促使一些新的理论领域的产生,比如多面体理论和复杂性理论。 货郎问题:给定n个结点和任意一对结点{i,j}之间的距离为dist(i,j),要求找出一条闭合的回路,该回路经过每个结点一次且仅一次,并且该回路的费用最小,这里的费用是指每段路径的距离和。 货郎问题求解其精确解是NP难的,并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上,就成为欧氏平面上的货郎问题,也叫欧几里德旅行商问题(Eculid Traveling Salesman Problem)。但是,即使是欧氏平面上的货郎问题也是NP难的。因此通常用来解决TSP问题的解法都是近似算法。其中第一个欧几里德旅行商问题的多项式近似算法是Arora在1996年使用随机平面分割和动态规划方法给出的。

    J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始,严格地从左到右直至最右点,然后严格地从右到左直至出发点。事实上,存在确定的最优双调路线的O(n*n)时间的算法。

/**********************************************************************
*        Bitonic path (详见《算法导论》 P217)                                                                                  
*        一个人从p1严格地增的走到pn,然后再严格递减的回到p1;求总路径的最小值;   
*        网上看到很多解题报告。。。看的我直冒汗     
*        只好自己看书,翻译。。。                                                                  
*        对于1 <= i <= j <= n, 我们定义P(i, j)是一条包含了P1, P2, P3 …… Pj的途径;                   
*        这条路径可以分成2部分:递减序列与递增序列                                                                
*        起点是Pi(1 <= i <= j),拐点是P1,终点是Pj, P[i, j]为其最小值;                                     
*        状态转移方程为:                                                                                                                      
*        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 西风萧瑟 阅读(6811) 评论(3)  编辑 收藏 引用 所属分类: 动态规划

评论:
# re: PKU2677,HDU2224 经典DP之双调旅行商(TSP) 2009-12-01 15:21 | 创意产品批发
佩服佩服。。。  回复  更多评论
  
# re: PKU2677,HDU2224 经典DP之双调旅行商(TSP) 2012-05-24 10:12 | aaa
* 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|   回复  更多评论
  
# re: PKU2677,HDU2224 经典DP之双调旅行商(TSP) 2012-10-09 22:43 | keli
状态转移方程为:
* 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|

==================
当i = j-1时,状态转移方程应该是:
b[i,j] = min{ b[j-1, k] + |PkPj|, 1 <= k < j-1 }吧,
虽然b[j-1, k] == b[k, j-1],但是我上面写的才是合理的吧?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理