文档编制序号：[KKIDT-LLE0828-LLETD298-POI08]
动态规划法回溯法分支限界法求解TSP问题实验报告

TSP问题算法实验报告
指导教师：        季晓慧                       
姓    名：        辛瑞乾                 
学    号：
提交日期：      2015年11月           
总述
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<n;i++)
    dp[i][0]=mp[i][0]
2.依次处理每个子集数组x[2^n-1]
for(i=1;i<n;i++)
    if（子集x[j]中不包含i）
    对x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};
3.输出最短路径长度。
实现代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
cstring转为int#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#define debug "output for debug\n"
#define pi (acos)
#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 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<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j)
                {
                    mp[i][j]=inf;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。