算法综合实验报告
学 号： 1004111115
一、实验内容：
分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并
至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述：
（包括程序的数据结构、函数组成、输入/输出设计、符号名说明等） 1、 动态规划法
(1)数据结构：
①利用二进制来表示集合，则集合S可由一个十进制数x相对应，此x所对应的二进制数为y，如果y的第k位为1，则表示k存在集合S中。 例如：
集合S={0，1}（其子集合为{}{0}{1}{01}），我们用二进制数11（所对应十进制数为3）表示S，11中右手边第1个数为1表示0在集合S中，右手边第二个数为1表示1在集合S中，其他位为0表示其它数字不在集合S中；
同理,集合S={0,2}（其子集合为{}{0}{2}{02}可用二进制数101（所对应十进制数为5）表示（右手边第1个数为1表示0在集合S中，右手边第二个数为0表示1不在集合S中，右手边第3个数为1表示2在集合S中，则说明0，2在集合中，1不在集合中。 ②利用邻接矩阵表示任意两点之间的距离 例如：
mp[i][j]表示点i，j两点之间的距离。 (2)函数组成
①输入函数in()
②利用动态规划法算法实现的求解函数solve() ③主函数main()
姓 名： 李宏强
(3)输入/输出设计
本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）
这里采用随机产生输入数据，将数据输出在屏幕上的方式。 (4)符号名说明 ① n 表示顶点个数。
② mp[i][j] 表示顶点i和顶点j之间的距离。
③ dp[i][j] 表示顶点i经过集合S(用二进制表示的数为j)后回到起始点的最短路径和。 (5)算法描述
①某一个点i不经过任意点回到起始点的最短路径和为mp[i][0](默认初始点为0)
dp[i][0] = mp[i][0]; (1<=i ②点i经过集合S（二进制表示的数为j）的最短路径和为从点i经过集合S中的某一点k后再从该点出发，经过集合S-{k}的最小值。 dp[i][j]=min{mp[i][k]+dp[k][j-(1<<(k-1))}; 2、 贪心法 (1)数据结构 ①利用邻接矩阵表示任意两点之间的距离 例如： mp[i][j]表示点i，j两点之间的距离。 (2)函数组成 ①输入函数in() ②利用贪心法每次取最近距离的函数dfs(u，k，l),u表示当前在顶点u， k表示已经走过了k个点，l表示所经过的路径和。 ③主函数main() (3)输入/输出设计 本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） 这里采用随机产生输入数据，将数据输出在屏幕上的方式。 (4)符号名说明 ① n 表示顶点个数。 ② mp[i][j] 表示顶点i和顶点j之间的距离。 ③ inq[i] 表示顶点i已经走过了。 (5)算法描述 如果当前在顶点u，则取与顶点u距离最近的点p。 dfs(u,k,l)=dfs(p,k+1,l+mp[u][p]) 3、 分支限界法 (1)数据结构 ①利用邻接矩阵表示任意两点之间的距离 例如： mp[i][j]表示点i，j两点之间的距离。 ②结构体 struct node { int visp[22];//标记哪些点走了 int st;//起点 int ed;//终点 int k;//走过的点数 int sumv;//经过路径的距离 int lb;//目标函数的值 bool operator <(const node &p )const { return lb>p.lb; } }; ③优先级队列 priority_queue (2)函数组成 ①in() 输入函数。 ②dfs(int u，int k，int l) 利用贪心法每次取最近距离的函数,u表示当前在顶点u，k表示已经走过了k个点，l表示所经过的路径和。将贪心法的解作为上界的初始值。 ③get_lb( node p) 求对应节点p的目标函数。 ④main() 主函数。 ⑤get_up() 求分支限界法的上界。 ⑥get_low() 求分支界限法的下界。 ⑦solve() 利用分支限界法求解函数 (3)输入/输出设计 本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） 这里采用随机产生输入数据，将数据输出在屏幕上的方式。 (4)符号名说明 ① n 表示顶点个数。 ② mp[i][j] 表示顶点i和顶点j之间的距离。 ③ inq[i] 表示顶点i已经走过了。 (5)算法描述 首先通过贪心法求解的值作为上界，把每个点最近的两条边之和的1/2作为下界。 分支限界法通过设定目标函数，每次从优先级队列中取目标函数的值最小的节点。先判断是否已经经过了n-1个点，如果已经经过了n-1个点，那么 可直接求出最短路径和，并与在队列里的其他节点的目标函数值比较，如果该路径和比其他所有在队列里的节点的目标函数值都小，那么改路径和就是问题的解。否则，继续计算优先级队列里面的其他节点。 三、源程序及注释： 这里默认顶点的个数小于22。 1、动态规划法 #include scanf(\ for(int i=0;i for(int j=0;j if(i==j) { mp[i][j]=INF; continue; } scanf(\ } } } int dp[22][1<<22]; int solve() { int s=(1<<(n-1)); dp[0][0]=0; for(int i=1;i dp[i][0]=mp[i][0]; } dp[0][(s-1)]=INF; for(int j=1;j<(s-1);j++)//总共有n-1个点，但不能全部取 {