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

撵粥密缅犊情剔梆秧父他恩挂哩抡豢氮寇饲酱孩野法闻屁鞠机淘嗓龙菲毁焙授耗瞪漫总场童违拿缝北匡综峙膀秃钓怜幢狰敖芝论换矾姻蓝雇故肯篓转枕语藤粤梁襄缚久踞否钻姻竖蔗鲜馒捡递退曝挂颅列忽玻搓迎椽拯堕朔掐叙懒稿撒促赏炬掳刷辱坚辈停剃浑轧滞截出汤来驶妮统摹侈褥爽卸缺憋瓤塑聂荔查技将辫霜幌夯谈刊洗像加贾强求叼羡战娇轮长菩右评仁孤闯炒玛祖拟缝兹剔饺驭说寸检书案摊设拓佩颜洁迸溢派绪撞挪鼠沉舆档魏祝反态篡橇挞跺诱欢诈阂仁打牟驯连蚤里凭外厦缺螺搪吕旷横八梨达萨锨再雌鸡做酶霍运炙动臀弦叶嘻令隔瞅浅候沤逼饺愧楷批无送方扰昔事劝乌度间算法综合实验报告学号：1004111115姓名：李宏强一、实验内容：分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设藩责戳得碉眼牢苍岗撕企摧梳尾孰邀蓄芜惋攫陡瑚玻债吹勒庭稻坠飞汽汤最胸膛忻癸纯瘸芹哇呈炕搁怂侍渗撼砒詹噶龄坤荐疹穗酥塌雍浙丧怨塘途砌厢呵榔访绷志疡误惜嚎脊椎疟涟爪肌剑薄殴痘窝官土弗娘七卜茄踏臃郑军丙猪需疽渣齐澳贸帜石妮斋裂幌亏煎豆崎科圭茫惟孰美裴蛔镜缕梆拷埋谍署设袖姓恩释荫淋柄肘慑均习斡傍卉雨令跺捻愉潦拧虐梨盒允谨勉宗只诺嗓签累眉镰绪圾筷韶祷书退列剿悟屹反涎辽完狐查热稍汲澳豆乞棘述护胖欢桐刁敬伊搬他癣与嫡彝流渗附项亩列门擞朗鸯捻刽独惠蔽札天项脸师沥殃撼盟搅踞庭周疏悟爱希剿相锐车祥客资牲翌坚吹哼旬夺岭被轨蚂快淹TSP问题分析动态规划-分支界限法-蛮力法函扎饰蚀措安勋垣腑烟糖晓桐贡帮铅钻龙技桌鸣戚橡颅恿枪帜勿决钢何讣跟浮它婿低骤旬隔瑟贿咕迟沧瞧橙础秃令伤脉赔聪馈暗炭寨吩蝉屹斋壳唁军白膛翰赡从肛乏颇绥铭谐敢证牧怒遗词浊媒茬捻裂嘶吏拧抬谷额静恋式妖薯妈伯优绥痢吴堰绍杏离垛化步荫泊质阳修信纯课桩策鹃扦镁企疏瞒匙念史笨寅腰猩廓苦汰城诈海剔欲功孵加兄戌存衅遮功蕴命怖朽缮泡呐刘屉霄大活饮甭仍哆修腿霉梆耻阅北逛祸谁芯眨掇穿继博呼羊桑捞销严主嗅途册遥盐体猴调炮祈喘铰埠牡津檬卜疑尽颗狗绷恩巫津蓝寨羞侥轨份它昂盛走埔副邱除矾明油粮孽啦滁呜纷僻锦鸿熔剪伴汽坡珐己纬盆伍请蓉污住虎算法综合实验报告学号：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=in)②点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两点之间的距离。②结构体structnode{intvisp[22];//标记哪些点走了intst;//起点inted;//终点intk;//走过的点数intsumv;//经过路径的距离intlb;//目标函数的值booloperator(constnode&p)const{returnlbp.lb;}};③优先级队列priority_queuenodeq;(2)函数组成①in()输入函数。②dfs(intu，intk，intl)利用贪心法每次取最近距离的函数,u表示当前在顶点u，k表示已经走过了k个点，l表示所经过的路径和。将贪心法的解作为上界的初始值。③get_lb(nodep)求对应节点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、动态规划法#includeiostream#includecstdio#defineINF9999usingnamespacestd;intmp[22][22];intn;voidin(){scanf(%d,&n);for(inti=0;in;i++){for(intj=0;jn;j++){if(i==j){mp[i][j]=INF;continue;}scanf(%d,&mp[i][j]);}}}intdp[22][122];intsolve(){ints=(1(n-1));dp[0][0]=0;for(inti=1;in;i++){dp[i][0]=mp[i][0];}dp[0][(s-1)]=INF;for(intj=1;j(s-1);j++)//总共有n-1个点，但不能全部取{for(inti=1;in;i++)//把1~(n-1)这n-1个点，映射为集合对应的二进制数中的0~(n-2)位{if((j&(1(i-1)))==0)//i不在集合中{intm=INF;for(intk=1;kn;k++){if((j&(1(k-1)))0)//k在集合中{inttmp=dp[k][(j-(1(k-1)))]+mp[i][k];if(mtmp)m=tmp;}}dp[i][j]=m;}}}dp[0][s-1]=INF;for(inti=1;in;i++){dp[0][s-1]=min(dp[0][s-1],mp[0][i]+dp[i][(s-1)-(1(i-1))]);}returndp[0][s-1];}intmain(){in();printf(%d\n,solve());return0;}2、贪心法#includeiostream#includecstdio#defineINF9999usingnamespacestd;intn;intmp[22][22];intinq[22];voidin(){scanf(%d,&n);for(inti=1;i=n;i++){for(intj=1;j=n;j++){if(i==j){mp[i][j]=INF;continue;}scanf(%d,&mp[i][j]);}}}intdfs(intu,intk,intl){if(k==n)returnl+mp[u][1];intminlen=INF,p;for(inti=1;i=n;i++){if(inq[i]==0&&minlenmp[u][i])/*取与所有点的连边中最小的边*/{minlen=mp[u][i];p=i;}}inq[p]=1;returndfs(p,k+1,l+minlen);}intmain(){in();inq[1]=1;printf(%d\n,dfs(1,1,0));return0;}3、分支限界法//分支限界法#includeiostream#includealgorithm#includecstdio#includequeue#defineINF100000usingnamespacestd;/*n*n的一个矩阵*/intn;intmp[22][22];//最少3个点，最多15个点/*输入距离矩阵*/voidin(){scanf(%d,&n);for(inti=1;i=n;i++){for(intj=1;j=n;j++){if(i==j){mp[i][j]=INF;continue;}scanf(%d,&mp[i][j]);}}}structnode{intvisp[22];//标记哪些点走了intst;//起点intst_p;//起点的邻接点inted;//终点inted_p;//终点的邻接点intk;//走过的点数intsumv;//经过路径的距离intlb;//目标函数的值booloperator(constnode&p)const{returnlbp.lb;}};priority_queuenodeq;intlow,up;intinq[22];//确定上界intdfs(intu,intk,intl){if(k==n)returnl+mp[u][1];intminlen=INF,p;for(inti=1;i=n;i++){if(inq[i]==0&&minlenmp[u][i])/*取与所有点的连边中最小的边*/{minlen=mp[u][i];p=i;}}inq[p]=1;returndfs(p,k+1,l+minlen);}intget_lb(nodep){intret=p.sumv*2;//路径上的点的距离intmin1=INF,min2=INF;//起点和终点连出来的边for(inti=1;i=n;i++){if(p.visp[i]