动态规划解决旅行商问题_附代码

《动态规划解决旅行商问题_附代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.问题基本描述:求一个旅行商经过N个城市最后回到出发点的最短路径.即,在一个无向带权图的邻接矩阵中,求一个最短环包括所有顶点.2.解法:1)动态规划:假设从顶点i出发，令d(i,V’)表示从顶点i出发经过V’中各个顶点一次且仅一次，最后回到出发点i的最短路径的长度，开始时，V’=V-{i}，于是，旅行商问题的动态规划函数为：d(i,V’)=min{cik+d(k,V’-{k})}(k∈V’)1)d(k,{})=cki(k≠i)2)简单来说,就是用递归表达:从出发点0到1号点,假设1是第一个,则剩下的路程就是从1经过剩下的点最后回到0点的最短路径.

2、所以当V’为空的时候,d(k,{})=cki(k≠i),找的是最后一个点到0点的距离.递归求解1之后,再继续求V’之中剩下的点,最后找出min.如果按照这个思想直接做,对于每一个i都要递归剩下的V中所有的点,所以这样的时间复杂度就近似于N!,其中有很多重复的工作.可以从小的集合到大的集合算,并存入一个二维数组,这样当加入一个节点时,就可以用到之前的结果,如四个点的情况:邻接矩阵:node01230 53215 79237 1232912 动态填表:表中元素代表第i个节点经过V集合中的点最后到0点的最短值.如果有多个值,取其中最小的一个.iVj01

3、231,2(取min)1,3(取min)2,3(取min)1,2,3(取min)0       c[0][i]+d[i][v’]=2115 1011  {c[1][2]+d[2][{3}]=21,c[1][3]+d[3][{2}]=24} 2312 14 {c[2][1]+d[1][{3}]=18,c[2][3]+d[3][{1}]=26}  321415 {c[3][1]+d[1][{2}]=19,c[3][2]+d[2][{1}]=24}   这样一共循环(2^(N-1)-1)*(N-1)次,就把时间复杂度缩小到O(N*2N)的级别.核心伪代码

4、如下:{for(i=1;i

5、每一个k∈Vj};}}对V[2^(n-1)-1]中的每个元素k,计算:d[0][2^(n-1)-1]=min{c[0][k]+d[k][2^(n-1)-2]};输出最短路径:d[0][2^(n-1)-1];}具体代码如下://TravRoadD.cpp:Defi

6、nestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"windows.h"#include"math.h"#include#include#includeusingnamespacestd;intN;//节点数intmatr[20][20];//存邻接矩阵intd[20][40000]={0};//存动态填表数据intgetmin(int*sum)//返回该数组中最小非零值{inti=0;intmin=-1,k

7、;for(;i0)

8、

9、(sum[i]>0&&sum[i]

10、jlist[i]=0;jlist[i+1]=1;}elseif(n-1-j==c)//若最高位为1,且j为当前1的个数所能组成的最大的j{for(i=0;i

11、j+i]=0;for(i=0;i<=k;i++)jlist[j+i+1]=1;}}intgetnextj(intj){in