TSP问题分析动态规划-分支界限法-蛮力法(共16页).doc

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