动态规划法,回溯法,分支限界法求解TSP问题实验报告

TSP问题算法实验报告

指导教师：***

*名：***

学号：**********

提交日期：2015年11月

目录

总述 (2)

动态规划法 (3)

算法问题分析 (3)

算法设计 (3)

实现代码 (3)

输入输出截图 (6)

OJ提交截图 (6)

算法优化分析 (6)

回溯法 (6)

算法问题分析 (6)

算法设计 (7)

实现代码 (7)

输入输出截图 (9)

OJ提交截图 (9)

算法优化分析 (10)

分支限界法 (10)

算法问题分析 (10)

算法设计 (10)

实现代码 (10)

输入输出截图 (15)

OJ提交截图 (15)

算法优化分析 (15)

总结 (16)

总述

TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城

市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。

动态规划法

算法问题分析

假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。

算法设计

输入：图的代价矩阵mp[n][n]

输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度

1.初始化第0列（动态规划的边界问题）

for(i=1;i

dp[i][0]=mp[i][0]

2.依次处理每个子集数组x[2^n-1]

for(i=1;i

if（子集x[j]中不包含i）

对x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};

3.输出最短路径长度。

实现代码

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define debug "output for debug\n" #define pi (acos(-1.0))

#define eps (1e-8)

#define inf 0x3f3f3f3f

#define ll long long int

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1 using namespace std;

const int mod = 1000000007;

const int Max = 100005;

int n,mp[20][20],dp[20][40000];

int main()

{

while(~scanf("%d",&n))

{

int ans=inf;

memset(mp,0,sizeof mp);

for(int i=0; i

{

for(int j=0; j

{

if(i==j)

{

mp[i][j]=inf;

continue;

}

int tmp;

scanf("%d",&tmp);

mp[i][j]=tmp;

}

}

int mx=(1<<(n-1));

dp[0][0]=0;

for(int i=1; i

{

dp[i][0]=mp[i][0];

}

dp[0][mx-1]=inf;

for(int j=1; j<(mx-1); j++)

{

for(int i=1; i

{

if((j&(1<<(i-1)))==0)

{

int x,y=inf;

for(int k=1; k

{

if((j&(1<<(k-1)))>0){

x=dp[k][(j-(1<<(k-1)))]+mp[i][k];

y=min(y,x);

}

}

dp[i][j]=y;

}

}

}

dp[0][mx-1]=inf;

for(int i=1;i

dp[0][mx-1]=min(dp[0][mx-1],mp[0][i]+dp[i][(mx-1)-(1<<(i-1))]);

printf("%d\n",dp[0][mx-1]);

}

return 0;

}