精华内容
下载资源
问答
  • 本压缩文档包含三个文件:用动态规划法解决TSP问题可执行源代码,word文档报告,实验测试数据
  • TSP问题动态规划法

    万次阅读 多人点赞 2018-05-15 20:19:10
    (一)动态规划法 假设从顶点i出发,令d(i, V')表示从顶点i出发经过V'中各个顶点一次且仅一次,最后回到出发点i的最短路径长度,开始时,V'=V-{i},于是,TSP问题动态规划函数为:d(i,V')=min{cik+d(k,V-{k}...

        TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。

        假设从顶点i出发,令d(i, V')表示从顶点i出发经过V'中各个顶点一次且仅一次,最后回到出发点i的最短路径长度,开始时,V'=V-{i},于是,TSP问题的动态规划函数为:

    d(i,V')=min{cik+d(k,V-{k})}(k∈V')

    d(k,{})=cki(k≠i)

        伪代码:

    for (i=1; i<n; i++)     //初始化第0列
    	d[i][0]=c[i][0]; 
     for (j=1; j<2n-1-1; j++)  
     	for (i=1; i<n; i++)   //依次进行第i次迭代
    		if (子集V[j]中不包含i) 
     			对V[j]中的每个元素k,计算[i][j]=min(c[i][k]+d[k][j-1]);
    对V[2n-1-1]中的每一个元素k,计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);
    输出最短路径长度d[0][2n-1-1];
    

        笔者在写此程序时卡在了如何判断:子集V[j]中不包含i。解决方法是对n个顶点分别用0~n-1的数字编号,按个数为1,2,……,n-1的顺序生成1~n-1个元素的子集存放在数组V[2^n-1]中。这样,在判断时就可以将当前点与数组编号按位与运算(如下图所示),为0则为需要进行计算(这时才能品味按位与运算的美)。


        完整代码:

    #include<iostream.h>
    #include<math.h>
    int main()
    {
    	int i,j,k,min,brief,n;
    	int D[20][20];
    	cout<<"顶点个数:";
    	cin>>n;
    	int b=(int)pow(2,n-1);
      	for(i=0;i<n;i++)
        	for(j=0;j<n;j++)
          		cin>>D[i][j];
      	int ** Route = (int **)calloc(n, sizeof(int *));
      	int ** Mat = (int **)calloc(n, sizeof(int *));
      	for(i=0;i<n;i++)
      	{
        	Route[i] = (int *)calloc(b*b, sizeof(int))+i*b;
        	Mat[i] = (int *)calloc(b*b, sizeof(int))+i*b;
      	}
      	for(i=0;i<b;i++)
       		for(j=0;j<n;j++)
    	    {
    			Route[j][i] = -1;
       			Mat[j][i] = -1;
    	    }
      	for(i=0;i<n;i++)//初始化第0列 
        	Route[i][0] = D[i][0];    
      	for(i=1;i<b-1;i++)
    	    for(j=1;j<n;j++)//依次进行第i次迭代 
    			if( ((int)pow(2,j-1) & i) == 0)//子集V[j不包含i 
    			{
    				min=999;
    				for(k=1;k<n;k++)
    				if( (int)pow(2,k-1) & i )
    				{
    					brief = D[j][k] + Route[k][i-(int)pow(2,k-1)]; 
    					if(brief < min)
    					{
    						min = brief;
    						Route[j][i] = min;
    						Mat[j][i] = k;//局部最优决策
    					}
    				}    
    			}
    	min=999;
      	for(k=1;k<n;k++)
    	{
    		brief = D[0][k] + Route[k][b-1 - (int)pow(2,k-1)];
    		if(brief < min)
    		{
    			min = brief;
    			Route[0][b-1] = min;//最优解
    			Mat[0][b-1] = k;
    		}
    	}
    	cout<<"最短路径长度:"<<Route[0][b-1]<<endl;//最短路径长度
    	cout<<"最短路径:"<<"1";
    	for(i=b-1,j=0; i>0; )
    	{
    		j = Mat[j][i];
    		i = i - (int)pow(2,j-1);
    		cout<<"->"<<j+1;
    	}
    	cout<<"->1"<<endl;
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<b;j++)
      			cout<<Route[i][j]<<" ";
    		cout<<endl;
    	}
    	free(Route);
    	free(Mat);
    	return 0;
    }
    
    展开全文
  • 动态规划法求解TSP问题 C++

    万次阅读 多人点赞 2018-07-01 14:06:16
    “鸡汤惠”帮“鸭汤莹”看代码,于是翻出了自己写的动态规划法求解TSP问题,于是整理了一下。(算法思想在知识点整理的部分,这里是具体实现的代码) 问题描述:  TSP问题是指旅行家要旅行n个城市,要求各个城市...

        “鸡汤惠”帮“鸭汤莹”看代码,于是翻出了自己写的动态规划法求解TSP问题,于是整理了一下。(算法思想在知识点整理的部分,这里是具体实现的代码)

    问题描述:

          TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。假设从顶点i出发,令d(i, V')表示从顶点i出发经过V'中各个顶点一次且仅一次,最后回到出发点i的最短路径长度,开始时,V'=V-{i},于是,TSP问题的动态规划函数为:

        d(i,V')=min{cik+d(k,V-{k})}(k∈V')      (式1)

        d(k,{})=cki(k≠i)                                     (式2)

    程序清单:

    #include<iostream>
    #include<iomanip>
    #include<cmath>
    using namespace std;
    #define MAX_IN 10
    
    class Tsp
    {
    	private:
    		int city_number;		//城市个数
    		int **distance;			//城市距离矩阵
    		int **process;			//求最短路径的过程矩阵
    	public:
    		Tsp(int city_number);		//构造函数
    		void correct();			//矫正输入的城市代价矩阵
    		void printCity();		//打印城市的距离矩阵
    		void getShoretstDistance();	//动态规划法求最短路径
    		void printProcess();		//打印过程矩阵
    
    };
    
    //构造函数
    Tsp::Tsp(int city_num)
    {
    	int i=0,j=0;
    	city_number=city_num;
    
    	//初始化城市距离矩阵
    	distance=new int*[city_number];
    	cout<<"请输入"<<city_number<<"个城市之间的距离"<<endl;
    	for(i=0;i<city_number;i++)
    	{
    		distance[i]=new int[city_number];
    		for(j=0;j<city_number;j++)
    			cin>>distance[i][j];
    	}
    
    	//生成过程矩阵
    	process=new int*[city_number];
    	for(i=0;i<city_number;i++)
    	{
    		process[i]=new int[1<<(city_number-1)];
    	}
    	
    
    }
    
    //纠正用户输入的城市代价矩阵
    void Tsp::correct()
    {
    	int i;
    	for(i=0;i<city_number;i++)
    	{
    		distance[i][i]=0;
    	}
    }
    
    //打印城市距离
    void Tsp::printCity()
    {
    	int i,j;
    	//打印代价矩阵
    	cout<<"您输入的城市距离如下"<<endl;
    	for(i=0;i<city_number;i++)
    	{
    		for(j=0;j<city_number;j++)
    			cout<<setw(3)<<distance[i][j];
    		cout<<endl;
    	}
    }
    
    //动态规划法求最短路径
    void Tsp::getShoretstDistance()
    {
    	int i,j,k;
    	//初始化第一列
    	for(i=0;i<city_number;i++)
    	{
    		process[i][0]=distance[i][0];
    	}
    	//初始化剩余列
    	for(j=1;j<(1<<(city_number-1));j++)
    	{
    		for(i=0;i<city_number;i++)
    		{
    			process[i][j]=0x7ffff;//设0x7ffff为无穷大
    
    			//对于数字x,要看它的第i位是不是1,通过判断布尔表达式 (((x >> (i - 1) ) & 1) == 1的真值来实现
    
    			if(((j>>(i-1))&1)==1)
    			{
    				continue;
    			}
    			for(k=1;k<city_number;k++)
    			{
    				//不能达到k城市
    				if(((j>>(k-1))&1)==0)
    				{
    					continue;
    				}
    				if(process[i][j]>distance[i][k]+process[k][j ^ (1 << (k - 1))])
    				{
    					process[i][j]=distance[i][k]+process[k][j ^ (1 << (k - 1))];				
    					//cout<<i<<"行"<<j<<"列为:"<<process[i][j]<<endl;
    				}
    			}
    		}
    	}
    	cout<<"最短路径为"<<process[0][(1<<(city_number-1))-1]<<endl;
    
    }
    
    //打印过程矩阵
    void Tsp::printProcess()
    {
    	int i,j;
    	for(j=0;j<1<<(city_number-1);j++)
    	{
    		cout<<setw(3)<<j;
    	}
    	cout<<endl;
    	for(i=0;i<city_number;i++)
    	{
    		for(j=0;j<1<<(city_number-1);j++)
    		{
    			if(process[i][j]==0x7ffff)
    				process[i][j]=-1;
    			cout<<setw(3)<<process[i][j];
    		}
    		cout<<endl;
    		
    	}
    }
    
    //主函数
    int main(void)
    {
    	cout<<"欢迎来到动态规划求旅行商问题,请输入城市个数";
    	int city_number;
    	while(cin>>city_number)
    	{
           Tsp tsp(city_number);		//初始化城市代价矩阵
    	   tsp.correct();					//纠正用户输入的代价矩阵
    	   tsp.printCity();				//打印城市
    	   tsp.getShoretstDistance();		//求出最短路径
    	   tsp.printProcess();			//打印计算矩阵
    	   cout<<"---------------------------------------"<<endl;
    	   cout<<"欢迎来到动态规划求旅行商问题,请输入城市个数";
    	}
    
    	return 0;
    }
    /*0 3 3 2 6
    3 0 7 3 2
    3 7 0 2 5
    2 3 2 0 3
    6 2 5 3 0
    */
    /*
            0, 10, 20, 30, 40, 50,
            12, 0 ,18, 30, 25, 21,
            23, 19, 0, 5,  10, 15,
            34, 32, 4, 0,  8,  16,
            45, 27, 11,10, 0,  18,
            56, 22, 16,20, 12,  0,
    */

    部分说明:

     

       个人认为动态规划法求解TSP问题的难点在于(1)求城市(除了起点)之外的其他城市子集;(2)判断城市是否位于一个子集中。

           我遇到的问题是起初认为子集需要按照子集元素的个数从小到大需要排序,在这里花费了比较多的时间,后来发现其实没有必要去排序。

    (1)关于求子集

       例如4个城市{0,1,2,3},{1,2,3}依次为{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},如果用111表示城市321,则上述子集转换成二进制为0,01,10,001,100,101,110,111,十进制恰好是0,1,2,3,4,5,6,7。虽然子集{1,2}在{3}之前,但遍历子集{1,2}的过程并不会使用过程矩阵中关于3的行列,因此不需要排序。

    (2)判断一个城市是否位于子集中

          判断一个城市是否在子集中,通过位运算(((x>>(i-1))&1)==1来实现,比如集合{1,3,5,6,7}表示成二进制串用1110101,其中集合里面有的数对应的位数写成1,没有的写成0。要判断第3位是不是1,就把1110101右移(3-1)位,得到11101,然后结果和00001进行&运算,如果结果是1说明第3位是1,则说明城市在子集中。

    (3)填过程矩阵,以process[2][5]为例。

        process[2][5] 表示从2出发,通过{1,3},最后回到起点。那么process[2][5] = min{C21 + process [1][{3}],C23 + process [3][{1}]} = min{C21 + process [1][4],C23 + process [3][1]} ;

      从2出发,要去{1,3}。先考虑去1的路,去了1集合{1,3}中只剩下{3} ,{3}对应二进制100,十进制4,所以要求的process表就是process [1][4],这个4可以通过(101)^(1)得到,(1) = 1<<(1-1);再看去3的路,去了3集合{1,3}中只剩下{1},{1}对应这1,所以要求的process表就是process [3][1],1通过(101) ^ (100)得到。(100) = 1<<(3-1)。

     

    参考结果:

     

     

     

     

    展开全文
  • 该文档使用Java语言编写了一个通用的TSP问题的求解方法,不仅进行了代码求解,还根据实际例子进行了手动求解和介绍,适合旅行商入门,以及Java语言的学习,附带源码和伪代码,以及详细的解释。
  • 动态规划法求解TSP问题

    千次阅读 2020-04-19 18:04:30
    一、求解TSP问题 1、问题描述 TSP问题(担货郎问题,旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短 各个城市间的距离可以用代价矩阵来表示。 2、...

    一、求解TSP问题
    1、问题描述

    • TSP问题(担货郎问题,旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短
    • 各个城市间的距离可以用代价矩阵来表示。
      在这里插入图片描述
      2、【应用】
      例如:校车怎样以最短的路线行走而接送到所有学生?报纸和牛奶的配送路线怎样最优?循环旅游怎样选取才能实现开支最少?公司视察子公司怎样出差更高效?
      3、【蛮力法求解】
      用蛮力法解决TSP问题,可以找出所有可能的旅行路线,即依次考察图中所有顶点的全排列,从中选取路径长度最短的简单回路。
      在这里插入图片描述
      在这里插入图片描述
      4、证明TSP问题满足最优性原理
      设s,s1,s2, …,sp,s是从s出发的一条路径长度最短的简单回路,假设从s到下一个城市s1已经求出,则问题转化为求从s1到s的最短路径,显然s1,s2,…,sp,s一定构成一条从s1到s的最短路径。
      如若不然,设s1,r1,r2,…,rq,s是一条从s1到s的最短路径且经过n-1个不同城市,则s,s1,r1,r2,…,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,…,sp,s要短,从而导致矛盾。所以,TSP问题满足最优性原理。
      5、动态规划法求解过程——示例
      在这里插入图片描述
      在这里插入图片描述6、动态规划求解问题的步骤
      (1)划分子问题—找到“状态”
      在这里插入图片描述
      (2)状态方程在这里插入图片描述
      (3)填表在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      7、算法设计
      (1)【数据结构设计】
      二维数组c[n][n]存放顶点之间的代价,n个顶点用0~n-1的数字编号
      一维数组V[2n-1]存放1~n-1个元素的所有子集
      二维数组dp[n][2n-1]存放递推结果,其中dp[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次,最后回到出发点0的最短路径长度。
      (2)【动态规划法算法】
      算法——TSP问题
      1.for(i=1; i<n; i++) d[i][0]=c[i][0]; //初始化第0列
      2.for(j=1; j<2n-1-1; j++)
      for(i=1; i<n; i++) //依次进行第i次迭代
      if(子集V[j]中不包含i)
      对V[j]中的每个元素k,计算d[i][j]=min(c[i][k]+d[k][j-1]);
      3.对V[2n-1-1]中的每一个元素k,计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);
      4.输出最短路径长度d[0][2n-1-1];

    8、算法分析
    在这里插入图片描述

    展开全文
  • 对基于动态规划TSP问题的求解 ,这个源码很好的说明其中的求解过程,以及数据结构的设计问题
  • 动态规划法解旅行商问题TSP问题的java实现
  • 动态规划解决TSP问题

    千次阅读 2018-12-15 16:42:41
    tmp = D[node][next_node] + TSP(step +1, next_node, S - i); if (min > tmp) { min = tmp; min_node = next_node; } } next_node++; } if (min [step][node]) { Path[step][node] = ...

    题目描述

    某推销员要从城市 v1 出发,访问其它城市v2,v3,…,v6 各一次且仅一次,最后返回v1。D为各城市间的距离矩阵。
    问:该推销员应如何选择路线,才能使总的行程最短?

             

                                       

     

    /*
    编辑者 : Lin_QC
    */
    
    #include<stdio.h>
    #include<stdlib.h>
    #define NODE_NUMBER 6
    
    int D[NODE_NUMBER][NODE_NUMBER] =   //每个点之间距离的矩阵
    { 0,10,20,30,40,50,
      12,0,18,30,25,21,
      23,19,0,5,10,15,
      34,32,4,0,8,16,
      45,27,11,10,0,18,
      56,22,16,20,12,0
    };
    int Path[6][6];   // 行表示走到第几步,列表是当前在哪一个点,它的值表示下一个走哪
    int cost[6][6] = {
    	1000,1000,1000,1000,1000,1000,
    	1000,1000,1000,1000,1000,1000,
    	1000,1000,1000,1000,1000,1000,
    	1000,1000,1000,1000,1000,1000,
    	1000,1000,1000,1000,1000,1000,
    	1000,1000,1000,1000,1000,1000
    };   // 记录Path每一个数据的当前最优值,先初始化一个很大的值
    
    int TSP(int step,int node ,int S)
    {
    	int min = 10000;
    	int tmp = 10000;
    	int next_node=1;
    	int min_node;
    	if (step == 6) {
    		return D[node][0];
    	}
    	for (int i = 1; i <=16 ; i *= 2) {
    		int t = S & i;
    		if (t == i) {	
    			tmp = D[node][next_node] + TSP(step +1, next_node, S - i);
    			if (min > tmp)
    			{
    				min = tmp;
    				min_node = next_node;
    			}
    		}	
    		next_node++;
    	}
    	if (min < cost[step][node]) {
    		Path[step][node] = min_node;
    		cost[step][node] = min;
    	}
    	return min;
    
    }
    int main()
    {
    	int next_node;
    	int ShortestDistance;
    	ShortestDistance=TSP(1,0,31);
    	printf("The Shortest distance is:%d\n",ShortestDistance);
    	printf("The best Path is: 1 ");
    	next_node = 0;
    	for (int i = 1; i <= 5; i++) {
    		printf("%d ", Path[i][next_node]+1);
    		next_node = Path[i][next_node];
    	}
    	printf("1 \n");
    	system("pause");
    }
    展开全文
  • 动态规划TSP问题(状态压缩dp)

    万次阅读 2017-09-04 15:38:03
    动态规划TSP问题(状态压缩dp)TSP问题简述  给定图上若干个点,以及他们之间的距离,求一条距离和最小的回路,使得该回路正好经过每个点一次。TSP也叫旅行商问题、货郎担问题。。。状态转移方程  用 V’ 表示...
  • 动态规划法】求解TSP问题

    千次阅读 多人点赞 2019-07-14 23:50:18
    假设从顶点i出发,令d(i, V’ )表示从顶点i出发经过V’ 中各个顶点一次且仅一次,最后回到出发点(i)的最短路径长度,开始时, V’ =V-{i},于是,TSP问题动态规划函数为: d(i, V’ )=min{cik+d(k, V’ -{k})...
  • 动态规划法解决TSP问题(C++)

    万次阅读 2011-12-19 10:32:01
    /*旅行商问题(Traveling Saleman Problem,TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点...解决TSP问题的思想有回溯法、贪心法、动态规划法等。 如
  • 动态规划 TSP 问题

    千次阅读 2018-04-17 19:09:25
    使用动态规划解决问题,首先需要证明问题具有最优子结构性质。可以使用反证证明TSP 问题具有最优子结构性质。 1. 问题假设 假设有4个城市,编号分别为0、1、2、3。设distance(k,V') 且V' = V-k 表示从顶点i出发...
  •   最近选了王波兴教授的计算几何与算法设计的课程,觉得王老师的课程讲的很好,就认真的听了一下,这门课最后要做一个PPT,讲解用这个学期讲的几种算法解决旅行商问题,下面就是我做的PPT。 程序实现的源码...
  • 动态规划TSP(旅行商)问题C++源码 内含可执行程序,C++源码,测试用例
  • 想分享的是递归实现的一种思路,理解了动态规划求解TSP的基本原理之后,会发现,计算相邻两个状态的距离d可以同归递归求解。
  • 2、使用动态规划法编程,求解0/1背包问题TSP问题TSP问题 一、实验内容: TSP问题是指旅行家要旅行n个城市,要求每个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。 对于图G=(V,E),假设从顶点i...
  • 使用动态规划方法求解TSP问题 这两天看到了一个用动态规划方法求解TSP问题的案例,原文代码是用C++写的,本人照着写成了java的代码,可以运行出相同的最后结果,但是不知道该如何得到最终的访问城市序列。 但是...
  • 首先,什么是TSP问题?直接摘百度—— 旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的...
  • TSP问题 TSP问题是什么? TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路线图最短。 题目 带权图的代价矩阵 无穷 3 6 7 5 无穷 2 3 6 4 无穷 2 6 7 5 ...
  • 某推销员要从城市v1出发,访问其它城市v2,v3,…,v6各一次且仅一次,最后返回v1。D为各城市间的距离矩阵。 问:该推销员应如何选择路线,才能使总的行程最短?
  • 20)又要求比较准确,所以采用了动态规划法动态规划算法的定义就不多做介绍了, 下面直接来到解决思路。 假设有N个城市,dp[N][N]这个二维数组保存了 各个城市之间的距离 那么问题就可以简化为 从0(p)点出发到...
  • 本报告仅供参考,不足之处请指正,版权由博主所有,未经同意禁止应用于非法用途,请下载者自觉。
  • 动态规划求解TSP

    2019-05-31 10:51:03
    动态规划的方法的最大难点就在于初始变量的确定,选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),设s出发点,其中i是一个点,而S是点的集合,这个变量的意思就是从i出发,...
  • 动态规划算法解决TSP问题

    万次阅读 2018-06-20 00:05:02
    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,994
精华内容 797
关键字:

动态规划法tsp问题