TSP问题分析动态规划,分支界限法,蛮力法.doc

算法综合实验报告 学 号： 1004111115 姓 名： 李宏强 一、实验内容： 分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述： （包括程序的数据结构、函数组成、输入/输出设计、符号名说明等） 动态规划法 (1)数据结构： = 1 \* GB3 ①利用二进制来表示集合，则集合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不在集合中。 = 2 \* GB3 ②利用邻接矩阵表示任意两点之间的距离 例如： mp[i][j]表示点i，j两点之间的距离。 函数组成 = 1 \* GB3 ①输入函数in() = 2 \* GB3 ②利用动态规划法算法实现的求解函数solve() = 3 \* GB3 ③主函数main() (3)输入/输出设计 本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） 这里采用随机产生输入数据，将数据输出在屏幕上的方式。 符号名说明 = 1 \* GB3 ① n 表示顶点个数。 = 2 \* GB3 ② mp[i][j] 表示顶点i和顶点j之间的距离。 = 3 \* GB3 ③ dp[i][j] 表示顶点i经过集合S(用二进制表示的数为j)后回到起始点的最短路径和。 算法描述 = 1 \* GB3 ①某一个点i不经过任意点回到起始点的最短路径和为mp[i][0](默认初始点为0) dp[i][0] = mp[i][0]; (1=in) = 2 \* GB3 ②点i经过集合S（二进制表示的数为j）的最短路径和为从点i经过集合S中的某一点k后再从该点出发，经过集合S-{k}的最小值。 dp[i][j]=min{mp[i][k]+dp[k][j-(1(k-1))}; 贪心法 数据结构 = 1 \* GB3 ①利用邻接矩阵表示任意两点之间的距离 例如： mp[i][j]表示点i，j两点之间的距离。 函数组成 = 1 \* GB3 ①输入函数in() = 2 \* GB3 ②利用贪心法每次取最近距离的函数dfs(u，k，l),u表示当前在顶点u，k表示已经走过了k个点，l表示所经过的路径和。 = 3 \* GB3 ③主函数main() (3)输入/输出设计 本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） 这里采用随机产生输入数据，将数据输出在屏幕上的方式。 符号名说明 = 1 \* GB3 ① n 表示顶点个数。 = 2 \* GB3 ② mp[i][j] 表示顶点i和顶点j之间的距离。 = 3 \* GB3 ③ inq[i] 表示顶点i已经走过了。 算法描述 如果当前在顶点u，则取与顶点u距离最近的点p。 dfs(u,k,l)=dfs(p,k+1,l+mp[u][p]) 分支限界法 数据结构 = 1 \* GB3 ①利用邻接矩阵表示任意两点之间的距离 例如： mp[i][j]表示点i，j两点之间的距离。 = 2 \* GB3 ②结构体 struct node { int visp[22];//标记哪些点走了 int st;//起点 int ed;//终点 int k;//走过的点数 int sumv;//经过路径的距离 int lb;//目标函数的值 bool operator (const node p )const { return lbp.lb; } }; = 3 \* GB3 ③优先级队列 priority_queuenode q; 函数组成 = 1 \* GB3 ①in() 输入函数。 = 2 \* GB3 ②dfs(int u，int k，int l) 利用贪心法每次取最近距