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

1. 问题基本描述:求一个旅行商经过N个城市最后回到出发点的最短路径.即,在一个无向带权图的邻接矩阵中,求一个最短环包括所有顶点.2. 解法:1) 动态规划:假设从顶点i出发，令d(i,V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径的长度，开始时，V=V-i，于是，旅行商问题的动态规划函数为： d(i,V) = mincik + d(k,V-k) (kV) 1)d(k,) = cki (k i) 2)简单来说,就是用递归表达:从出发点0到1号点,假设1是第一个,则剩下的路程就是从1经过剩下的点最后回到0点的最短路径. 所以当V为空的时候, d(k,) = cki (k i), 找的是最后一个点到0点的距离.递归求解1之后,再继续求V之中剩下的点,最后找出min.如果按照这个思想直接做,对于每一个i都要递归剩下的V中所有的点,所以这样的时间复杂度就近似于N!,其中有很多重复的工作.可以从小的集合到大的集合算,并存入一个二维数组,这样当加入一个节点时,就可以用到之前的结果,如四个点的情况:邻接矩阵:node0123053215792371232912动态填表:表中元素代表第i个节点经过V集合中的点最后到0点的最短值.如果有多个值,取其中最小的一个.iVj01231,2(取min)1,3(取min)2,3(取min)1,2,3(取min)0c0i+div=21151011c12+d23=21,c13+d32=24231214c21+d13=18,c23+d31=26321415c31+d12=19,c32+d21=24这样一共循环(2(N-1)-1)*(N-1)次,就把时间复杂度缩小到O(N*2N )的级别.核心伪代码如下:for (i =1;in;i+) /初始化第0列di0=ci0;for( j=1;j2(N-1)-1;j+) for(i=1 ; in ;i+)if(子集Vj中不包含i)对Vj中的每个元素k，计算diVj = mincik + dkVj-k | 每一个kVj;对V2(n-1)-1中的每个元素k,计算:d02(n-1)-1 = minc0k + dk2(n-1)-2;输出最短路径:d02(n-1)-1;具体代码如下:/ TravRoadD.cpp : Defines the entry point for the console application./#include stdafx.h#include windows.h#include math.h#include #include #include using namespace std;int N;/节点数int matr2020;/存邻接矩阵int d2040000=0;/存动态填表数据int getmin(int *sum)/返回该数组中最小非零值int i = 0;int min = -1,k;for(;iN;i+)if(min 0) | (sumi0 & sumimin)min = sumi;k = i;return min;void getJ(int jlist, int c, int n)/根据2进制j和j中1的个数找下一个jint i = n-1,j;int tmp = 1 , result = 0;while(!jlisti)i-;/最高位的1的位置j = i-1;while(jlistj)j-;/找最高位1之下的最高0if(!jlistn-1)/若最高位不为1/将为1的最高一位向上移一位jlisti=0;jlisti+1=1;else if(n-1-j=c)/若最高位为1,且j为当前1的个数所能组成的最大的jfor(i=0;in;i+)jlisti=0;for(i=0;ic+1;i+)jlisti=1;else/最高位为1,且在当前数目1下还能变更大/将和最高位之间有隔0的最高的1上移一位,并把这个1之后的 所有1 拉到紧邻它后面int k;k=n-1-j;/最高位一共有多少相邻的1while(!jlistj)j-;/找和最高位隔着0的最高1for(i=0;j+in;i+)jlistj+i=0;for(i=0;i=k;i+)jlistj+i+1=1;int getnextj( int j )int nextj = 0;/下一个jint c=0;/计数j的二进制有几个1int jlist20=0;/存放j的二进制数组int i=0;int tmp = 1;while(j)if(j%2)c+;jlisti+=1;elsejlisti+=0;j/=2;getJ(jlist,c,N-1);/处理jlistfor(i=0;iN-1;i+)/将jlist中的2进制转换成int返回if(jlisti)nextj += tmp;tmp *= 2;return nextj;int main(int argc, char* argv)freopen(d:test_20.txt,r,stdin);int i,j;int min;scanf(%d,&N);/读入点数for(i = 0; i N; i+)/读入邻接矩阵for(j = 0;j N; j+)scanf(%d,&matrij);int V20=0;for(i = 0; i N; i+)Vi=1;/将所有点设置为未经过点V0=0;/以第0个点为出发点/2n次方解法for (i =1;iN;i+) /初始化第0列di0=matri0;for(j=1;jpow(2,N-1)-1;j=getnextj(j) for(i=1; iN ;i+)if(!(j & ( 1(i-1) )/如果集合j中不包含i/对Vj中的每个元素k，计算dij = minmatrik + dkj-k;int jlist20=0; /存放j的二进制数组int tmpres20=0;int c=0,k=j,l;while(k)if(k%2)jlistc+=1;elsejlistc+=0;k/=2;c=0;for(l=0;lN;l+)if(jlistl)tmpresc+=matril+1 + dl+1j-(1l);dij = getmin(tmpres);int tmpres20=0;j = pow(2,N-1)-1;for(i=1;iN;i+)tmpresi=matr0i + di j - (1(i-1