TS问题分析动态规划分支界限法蛮力法

1、算法综合实验报告学号：_15 姓名： 李宏强一、实验内容：分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：（包括程序的数据结构、函数组成、输入/输出设计、符号名说明等）1、动态规划法（1）数据结构： 利用二进制来表示集合，则集合S可由一个十进制数x相对应，此x所对应的二进制数为y，如果y的第k位为1，则表示k存在集合S中。例如：集合S=0，1（其子集合为0101），我们用二进制数 11 （所对应十进制数为3）表示S, 11中右手边第1个数为1表示0在集合S中，右手边第二个数

2、为1表示1在集合S中，其他位为0表示其它数字不在集合 S中;同理，集合S=0,2（其子集合为0202可用二进制数101 （所对应十 进制数为 5)表示(右手边第 1 个数为 1 表示 0 在集合 S 中，右手边第二个 数为 0 表示 1 不在集合 S 中，右手边第 3 个数为 1 表示 2 在集合 S 中，则说 明 0， 2在集合中， 1 不在集合中。 利用邻接矩阵表示任意两点之间的距离例如：mpij 表示点 i ， j 两点之间的距离。(2) 函数组成 输入函数 in() 利用动态规划法算法实现的求解函数 solve() 主函数 main()(3) 输入 / 输出设计本程序可以通过键盘进行输

3、入、屏幕进行输出。(根据实际程序情况，还可 以选择随机产生输入数据、将输出数据输出到文件等其它方式)这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符号名说明 n 表示顶点个数。 mpij 表示顶点 i 和顶点 j 之间的距离 dpij 表示顶点 i 经过集合 S( 用二进制表示的数为 j) 后回到起始点的 最短路径和。(5) 算法描述 某一个点 i 不经过任意点回到起始点的最短路径和为 mpi0( 默认初始点为0)dpi0 = mpi0; (1<=i<n) 点i经过集合S (二进制表示的数为j )的最短路径和为从点i经过集合S中的某一点k后再从该点出发，经过集合S-k

4、的最小值。dpij=minmpik+dpkj-(1<<(k-1);2、贪心法(1) 数据结构 利用邻接矩阵表示任意两点之间的距离例如：mpij 表示点 i ， j 两点之间的距离。(2) 函数组成 输入函数 in() 利用贪心法每次取最近距离的函数 dfs(u ， k， l),u 表示当前在顶点 u， k表示已经走过了 k 个点， l 表示所经过的路径和 主函数 main()(3) 输入 / 输出设计本程序可以通过键盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式)这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符

5、号名说明 n 表示顶点个数。 mpij 表示顶点 i 和顶点 j 之间的距离。 inqi 表示顶点 i 已经走过了。(5) 算法描述如果当前在顶点u,则取与顶点u距离最近的点P。dfs(u,k,l)=dfs(p,k+1,l+mpup)3、分支限界法(1) 数据结构 利用邻接矩阵表示任意两点之间的距离例如：mpij 表示点 i ， j 两点之间的距离 结构体struct nodeint visp22;/标记哪些点走了int st;/起点int ed;/终点int k;/走过的点数int sumv;/经过路径的距离int lb;/目标函数的值bool operator <(const nod

6、e &p )constreturn lb> 优先级队列priority_queue<node> q;(2) 函数组成 in()输入函数。 dfs(int u , int k , int l)k 表示已经走过了利用贪心法每次取最近距离的函数 ,u 表示当前在顶点 u， k 个点， l 表示所经过的路径和。将贪心法的解作为上界的初始值 get_lb( node p)求对应节点 p 的目标函数。 mai n()主函数。 get_up()求分支限界法的上界。 get_low()求分支界限法的下界。 solve()利用分支限界法求解函数(3) 输入/ 输出设计 本程序可以通过键

7、盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式) 这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符号名说明 n 表示顶点个数。 mpij 表示顶点 i 和顶点 j 之间的距离。 inqi 表示顶点 i 已经走过了。(5) 算法描述首先通过贪心法求解的值作为上界，把每个点最近的两条边之和的 1/2 作为 下界。分支限界法通过设定目标函数，每次从优先级队列中取目标函数的值最小的节点。先判断是否已经经过了 n-1个点，如果已经经过了 n-1个点，那么可直接求出最短路径和， 并与在队列里的其他节点的目标函数值比较， 如果该路径和比

8、其他所有在队列里的节点的目标函数值都小，那么改路径和就是问题的解。否则，继续计算优先级队列里面的其他节点三、源程序及注释：这里默认顶点的个数小于 22。1、动态规划法#include<iostream>#include<cstdio>#define INF 9999using namespace std;int mp2222;int n;void in()scanf("%d",&n);for(int i=0;i<n;i+)for(int j=0;j<n;j+)if(i=j)mpij=INF;continue;scanf("

9、;%d",&mpij);int dp221<<22;int solve()int s=(1<<(n-1);dp00=0;for(int i=1;i<n;i+)不在集合中在集合中dpi0=mpi0;dp0(s-1)=INF;for(int j=1;j<(s-1);j+)/总共有 n-1 个点，但不能全部取for(int i=1;i<n;i+) /把 1(n-1) 这 n-1 个点，映射为集合对应的二进制数中的0(n-2) 位if(j&(1<<(i-1)=0)/iint m=INF;for(int k=1;k<n

10、;k+)if(j&(1<<(k-1)>0)/kint tmp=dpk(j-(1<<(k-1)+mpik;if(m>tmp)m=tmp;dpij=m;dp0s-1=INF;for(int i=1;i<n;i+)dp0s-1=min(dp0s-1,mp0i+dpi(s-1)-(1<<(i-1);return dp0s-1;int main()in();printf("%dn",solve();return 0;2、贪心法 #include<iostream> #include<cstdio>

11、#define INF 9999 using namespace std; int n;int mp2222;int inq22;void in()scanf("%d",&n);for(int i=1; i<=n; i+)for(int j=1; j<=n; j+)if(i=j)mpij=INF;continue;scanf("%d",&mpij);int dfs(int u,int k,int l)if(k=n) return l+mpu1;int minlen=INF , p;for(int i=1; i<=n; i

12、+)取与所有点的连边中最小的边 */if(inqi=0&&minlen>mpui)/*minlen=mpui;p=i;inqp=1;return dfs(p,k+1,l+minlen);int main()in();inq1=1;printf("%dn",dfs(1,1,0);return 0;3、分支限界法/ 分支限界法#include<iostream>#include<algorithm>#include<cstdio>#include<queue>#define INF 100000using n

13、amespace std;/* n*n 的一个矩阵 */int n;int mp2222;/ 最少 3 个点，最多 15 个点/* 输入距离矩阵 */void in()scanf("%d",&n);for(int i=1; i<=n; i+)for(int j=1; j<=n; j+)if(i=j)mpij=INF;continue;scanf("%d",&mpij);struct nodeint visp22;/ 标记哪些点走了int st;/ 起点int st_p;/ 起点的邻接点int ed;/ 终点int ed_p;/

14、 终点的邻接点int k;/ 走过的点数int sumv;/ 经过路径的距离int lb;/ 目标函数的值bool operator <(const node &p )constreturn lb>priority_queue<node> q;int low,up;int inq22;/ 确定上界int dfs(int u,int k,int l)if(k=n) return l+mpu1;int minlen=INF , p;for(int i=1; i<=n; i+)取与所有点的连边中最小的边 */if(inqi=0&&minlen&g

15、t;mpui)/*minlen=mpui;p=i; inqp=1;return dfs(p,k+1,l+minlen);int get_lb(node p)int ret=*2;/ 路径上的点的距离int min1=INF,min2=INF;/ 起点和终点连出来的边for(int i=1; i<=n; i+)ifi=0&&min1>mpi)min1=mpi;ret+=min1;for(int i=1; i<=n; i+)ifi=0&&min2>mpi) min2=mpi;ret+=min2;for(int i=1; i<=n; i+

16、)ifi=0)min1=min2=INF;for(int j=1; j<=n; j+)if(min1>mpij) min1=mpij;for(int j=1; j<=n; j+) if(min2>mpji)min2=mpji;ret+=min1+min2;return ret%2=0(ret/2):(ret/2+1);void get_up()inq1=1;up=dfs(1,1,0);void get_low()low=0;for(int i=1; i<=n; i+)/* 通过排序求两个最小值 */int min1=INF,min2=INF;int tmpA22;

17、for(int j=1; j<=n; j+)tmpAj=mpij;sort(tmpA+1,tmpA+1+n);/ 对临时的数组进行排序low+=tmpA1;int solve()/* 贪心法确定上界 */get_up();/* 取每行最小的边之和作为下界 */get_low();/* 设置初始点 , 默认从 1 开始 */node star;=1;=1;=1;for(int i=1; i<=n; i+) i=0;1=1;=0;=low;/*ret 为问题的解 */ int ret=INF;(star);while(!()node tmp=();();if=n-1)/* 找最后一个没

18、有走的点 */int p;for(int i=1; i<=n; i+)ifi=0)p=i;break;int ans=+mpp+mpp;node judge = ();/* 如果当前的路径和比所有的目标函数值都小则跳出 */ if(ans <=ret=min(ans,ret);break;/* 否则继续求其他可能的路径和，并更新上界 */elseup = min(up,ans);ret=min(ret,ans);continue;/* 当前点可以向下扩展的点入优先级队列 */ node next;for(int i=1; i<=n; i+)ifi=0)J/*更新路径和 */=

19、+mpi;/*更新最后一个点 */=i;/*更新顶点数 */=+1;/*更新经过的顶点 */ for(int j=1; j<=n; j+) j=j;i=1;/*求目标函数 */=get_lb(next);/*如果大于上界就不加入队列 */if>up) continue;(next);return ret;int main()in();printf("%dn",solve();return 0;四、运行输出结果：（贴出程序运行完成时的屏幕截图或者输出文件的内容）这里采用相同的两组数据进行测试。1、动态规划法样例 1：样例 2：2、贪心法样例 1：样例 2：贪心法只

20、能求局部最优解，局部最优解不一定是全局最优解。3、分支限界法样例 1：样例 2：五、调试和运行程序过程中产生的问题及采取的措施：1、动态规划法中输出错误， 通过测试数据进行反复验证， 并分块输出局部结果，从而发现问题并解决。2、贪心法对第二组样例的解不正确，因为局部最优解不一定是全局最优解。3、分支限界法对于测试样例输出随机值， solve() 函数在每次返回的时候结果不 一致。通过反复观察代码，发现循环跳出的条件有问题，应该是当前的解小于或等 于队列中的目标函数值才跳出。六、对算法的程序的讨论、分析，改进设想，其它经验教训：1动态规划法算法时间复杂度为 0(n2*2n)，在oj上的测试时间如下：(oj 上的测试样例 n 最大值为 15)2、贪心法只能求局部最优解，不一定是全局最优解。所以第二组样例的解不正 确。3、分支限界法的复杂度是根据数据的不同而不同，搜索的节点越少，复杂度越 低，跟目标函数的选择有很大关系。目标函数值的计算也会需要一定时间，比如此 文章中的目标函数值求解的复杂度是 0(n2)。在 oj 上的测试时间如下：在设置节点的时候，用数组标记经过的顶点， vispi=1 ，则说明 i 点已经经过 了，由于是静态分配空间，所以每次创建新的节点，都会增加空间。所以可以考虑 动态分配空间，把不用的节点的空