首页 > 代码库 > TSP问题——动态规划

TSP问题——动态规划

            Traveling Salesman Problem

  Description:                    Time Limit: 4sec    Memory Limit:256MB

  有编号1到N的N个城市,问从1号城市出发,遍历完所有的城市并最后停留在N号城市的最短路径长度。

  Input:

  第一行整数 T :T组数据 (T<=20) 

  每个case 读入一个N( 2 <= N <= 20),接着输入N行,第i行有两个整数 xi , yi 表示第 i 个城市坐标轴上的坐标 。

  Output:

  每个case输出一个浮点数表示最短路径。四舍五入保留两位小数。

  Sample Input:

  1 4 0 0 1 0 1 1 0 1

  Sample Output:

  3.41

 

  经典难题!数据开到这么小就知道没有那么简单的复杂度了,一般的算法,即爆搜,复杂度为 o( n! ) ,我们这里采用的动态规划算法,

  算法复杂度已经从阶乘级降到了o( ( n^2 )*( 2^n ) ) (看起来也是相当恐怖的,不过像这种经典难题这种复杂度对我来说已经不错了)。

 

  开始说说思路,一开始马上想到的必然是搜索,搜索必然超时,于是某大神直接告诉我——记忆化搜索,记忆化搜索能做的动规就能做,写递归太麻烦了于是动规!

  题目中起点终点确定,于是我们可以用一个二维dp数组来保存一个状态——dp[i]{V}表示从结点0到结点 i 途经V中所有节点的最短路径长(这里的V是一个集合)

  于是状态转移方程可以为:dp[i]{V}=min( dp[i]{V} , dist[i][j]+dp[j]{V-{j}} )  (j 属于 V)

  好的大思路定好了,我们来考虑细节部分,主要有以下部分:

  1)建图等等:结构体point,距离函数dist;

  2)集合V的表示:二进制数,即010表示三个数的集合第二个有,其余无;

  3)dp过程的范围:1 ~ n-1 (最大可能为 1 ~ 18 );

  

  于是我们可以敲代码啦!

#include <bits/stdc++.h>const double INF=10e7;using namespace std;int T,n,cnt;double a[25][25],dp[25][1100000];struct point{		//结点结构体 	int x,y;}pt[25];double d(point a,point b){		//结点间距离 	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int main(){	scanf("%d",&T);	while(T--)	{		cnt=1;		scanf("%d",&n);		for(int i=2;i<n;i++) cnt<<=1;		//组合数(除起点终点外) 				for(int i=0;i<n;i++)				//输入 			scanf("%d %d",&pt[i].x,&pt[i].y);				for(int i=0;i<n;i++)				//建边 			for(int j=0;j<n;j++)				a[i][j]=d(pt[i],pt[j]);						for(int i=0;i<n;i++)				//初始化 			for(int j=0;j<cnt;j++)				dp[i][j]=INF;				for(int i=0;i<n;i++)				//起点确定,定下初始条件 			dp[i][0]=a[i][0];						for(int i=1;i<cnt;i++)				//从有元素考虑起 			for(int j=1;j<n-1;j++)			{				for(int k=1;k<n-1;k++)				{					if((1<<k-1)&i)		//k is in the set						dp[j][i]=min(dp[j][i],a[j][k]+dp[k][i-(1<<k-1)]);	//状态转移方程 				}			}		double ans=INF;		for(int i=1;i<n;i++)			ans=min(ans,dp[i][cnt-1]+a[i][n-1]);				printf("%.2lf\n",ans);	}		return 0;}

  之前动态规划也是做了不少的基础例题,这道题算是动态规划的第一次成功应用,还是蛮开心的,软创得加油啊!

 

  

TSP问题——动态规划