求解货郎担问题的认识和实践

TSP问题求解（一）实验目的熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。

（二）实验原理巡回旅行商问题给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。

TSP问题也称为货郎担问题，是一个古老的问题。

最早可以追溯到1759年Euler提出的骑士旅行的问题。

1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。

TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。

近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法，模拟退火方法以及遗传算法方法等。

TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。

在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。

借助遗传算法的搜索能力解决TSP问题，是很自然的想法。

基本遗传算法可定义为一个8元组：（SGA）=（C，E，P0，M，Φ，Г，Ψ，Τ）C ——个体的编码方法，SGA使用固定长度二进制符号串编码方法；E ——个体的适应度评价函数；P0——初始群体；M ——群体大小，一般取20—100；Ф——选择算子，SGA使用比例算子；Г——交叉算子，SGA使用单点交叉算子；Ψ——变异算子，SGA使用基本位变异算子；Т——算法终止条件，一般终止进化代数为100—500；问题的表示对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。

用遗传算法解决TSP，一个旅程很自然的表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用。

路径表示是表示旅程对应的基因编码的最自然，最简单的表示方法。

它在编码，解码，存储过程中相对容易理解和实现。

例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示为（5 1 7 8 9 4 6 2 3）（三）实验内容N>=8。

TSP实验报告（实验报告、研究报告）考核科⽬：算法分析与复杂性理论学⽣所在学院：计算机科学与技术学院学⽣所在学科：计算机应⽤技术姓名：学号：学⽣类别：研究⽣⼀、实验⽬的1.通过TSP算法的具体实现，加深对算法复杂分析的理解。

2.通过TSP算法的具体实现，提⾼对NP完全问题的认识。

3.通过TSP算法的具体实现，理解不确定性算法。

4.通过TSP算法的具体实现，理解不确定性算法。

⼆、实验环境实验平台：Visual C++编程语⾔：C++编程电脑配置：三、实验内容描述TSP（Travelling Salesman Problem）⼜称货郎担或巡回售货员问题，在运筹学、管理科学及⼯程实际中具有⼴泛的⽤途。

及⼯程实际中具有⼴泛的⽤途。

TSP问题是组合优化中的著名难题，⼀直受到⼈们的极⼤关注。

由于其NP难题性质，⾄今尚未完全解决。

此问题可以抽象描述为：给出⼀个n个顶点⽹络（有向或⽆向），要求找出⼀个包含所有n个顶点的具有最⼩耗费的环路。

其中，任何⼀个包含所有n个顶点的环路被称作⼀个旅⾏。

对于旅⾏商问题，顶点表⽰旅⾏商所要旅⾏的城市（包括起点）。

边上权值给出了在两个城市旅⾏所需的路程。

旅⾏表⽰当旅⾏商游览了所有城市后再回到出发点时所⾛的路线。

四、实验原理许多研究表明，应⽤蚁群优化算法求解TSP问题优于模拟退⽕法、遗传算法、神经⽹络算法、禁忌算法等多种优化⽅法。

为说明该算法，引⼈如下的标记: m表⽰蚁群中蚂蚁的数量；表⽰城市i和城市j之间的距离；表⽰t时刻位于城市i的蚂蚁数，显然应满⾜，表⽰t时刻在ij连线上的信息数量。

在算法的初始时刻，将m只蚂蚁随机地放到n座城市上，此时各路径上的信息量相等，设。

每只蚂蚁根据路径上保留的信息量独⽴地选择下⼀个城市。

在时刻t，蚂蚁k从城市i转移到城市j 的概率为其中，表⽰蚂蚁⾛下⼀步允许选择的所有城市，列表纪录了当前蚂蚁k所⾛过的城市，当所有n个城市都加⼊到中时，蚂蚁k便完成了⼀次循环，此时蚂蚁⾛所⾛过的路径便是问题的⼀个解。

龙源期刊网 挑担游戏中的纠结作者：来源：《幼儿教育·教育教学版》2019年第10期一天，中班幼儿饶有兴致地聊起了在古镇游玩时看到的挑着担的货郎，他们还拿管子積木搭了一根“扁担”扛在肩上模仿了一番。

我想，如果设计一种挑担的游戏材料，幼儿一定会很喜欢玩的。

为此，我收集了大大小小多个饮料瓶、油壶，装满水，在瓶口或壶口系上绳子作为拎环，又找来竹竿，组合成了挑担的游戏材料，投放到户外运动区。

我设想，幼儿可以根据自己的能力将不同大小的饮料瓶或油壶挂到竹竿两头，尝试保持平衡并负重行走。

这不但可以发展幼儿的平衡能力，而且可以锻炼幼儿的体能。

同时，为了让幼儿自主探索，我没有演示玩法，而是告诉幼儿想怎么玩就怎么玩。

材料投放之后，幼儿果然很有兴趣，都来尝试挑担，还自发地加入了一些角色游戏情节。

他们往往从小一点的饮料瓶开始尝试，逐渐增加重量，挑战自己，有时还把大号油壶挂在竹竿中间，与同伴合作抬水。

当然，也有不少幼儿自创了新的玩法，比如，拿来练举重，或把竹竿架在两个瓶子上模拟跨栏、跳高等。

在此过程中，我也不断完善材料的设计，使之更适合幼儿使用。

比如，我把竹竿两头用布包起来拿绳子扎紧，以增加摩擦力，使瓶子或油壶的拎环没那么容易滑脱;我提供毛巾让幼儿挑担时垫在肩膀上，以免竹竿太硬、担子太沉弄疼幼儿。

过了一段时间，幼儿对这一材料的兴趣渐渐淡了下来，玩的人也越来越少了。

有一天，我看到冬冬挑着两瓶水到了小花园，然后拧开瓶盖把水倒在地上，说：“我把水运过来给大树浇浇水。

”我受到了启发：如果在挑担游戏中增加一些运水之类的任务情境，会不会让幼儿重新对游戏产生兴趣呢？考虑到户外场地上取水不太方便，我请保育员拿大水桶装上水，搬到场地边。

我又提供了水瓢和漏斗等，幼儿可以利用这些工具把水灌到瓶子、油壶里，然后挑到花园边上。

为了避免幼儿浇水过多把植物浇死，我在小花园边上也放置了一个大水桶，只让幼儿把水运过来倒进桶里，这样水就能循环利用，避免浪费。

旅⾏商问题——模拟退⽕算法实现1.问题描述旅⾏商问题（Travelling Salesman Problem, 简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[d ij]，其中d ij表⽰城市i到城市j的距离（i，j=1，2 … n），则问题是要找出遍访每个城市恰好⼀次的⼀条回路并使其路径长度为最短。

2.算法设计对原问题进⾏分析，TSP的⼀个解可表述为⼀个循环排列：Π= (Π1，Π2，Π3… Πn），即Π1→Π2→ … →Πn→Π1有（n-1）！/2 种不同⽅案，若使⽤穷举法，当n很⼤时计算量是不可接受的。

旅⾏商问题综合了⼀⼤类组合优化问题的典型特征，属于NP 难题，不能在多项式时间内进⾏检验。

若使⽤动态规划的⽅法时间复杂性和空间复杂性都保持为n的指数函数。

本次实验利⽤模拟退⽕算法（Simulated Annealing）求解TSP问题。

模拟退⽕算法最早由N.Metropolis等⼈于1953年提出，基于物理中固体物质的退⽕过程与⼀般组合优化问题之间的相似性。

该算法从某⼀较⾼初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间随机寻找全局最优解。

退⽕是将固体加热到⾜够⾼的温度，使分⼦呈随机排列态，然后逐步降温冷却，最后分⼦以低能状态排列，得到稳定状态的固体。

退⽕的过程有：（1）加温过程：增强粒⼦运动，消除系统原本可能存在的⾮均匀态；（2）等温过程：对于与环境换热⽽温度不变的封闭系统，系统状态的⾃发变化总是朝向⾃由能减少的⽅向进⾏，当⾃由能达到最⼩时，系统平衡；（3）冷却过程：使粒⼦热运动减弱并逐渐趋于有序，系统能量逐渐下降，从⽽得到低能的晶体结构。

其中，固体在恒温下达到热平衡的过程采⽤Metropolis⽅法进⾏模拟：温度恒定为T时，当前状态i转为新状态j，如果j状态的能量⼩于i，则接受状态j为当前状态；否则，如果概率p=exp{-(E j-E i)/(k*T)}⼤于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成⽴则保留状态i为当前状态。

【算法复习二】货郎担（旅行售货商）动态规划一，问题由来货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。

二，问题描述1）货郎担问题提法：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？2）旅行商问题的提法：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

三，问题求解1）动态规划解例题：设v1，v2，……..，vn是已知的n个城镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回v1的最短路程。

分析：设S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。

建模：状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。

最优指标函数fk（i，S）为从v1出发，经过S集合中所有点一次最后到达vi。

决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合到vi 城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为：fk（i，S）= min{ fk-1（j，S、{ j }+dji} j属于Sf0（i，空集）=d1i （k=1，2，…,n-1,i=2,3,…n)求解：K=0f0(2,空集)=d12=6f0(3,空集)=d13=7f0(4,空集)=d14=9当k=1时:从城市V1出发,经过1个城镇到达Vi的最短距离为:f1(2,{ 3 }) = f0 (3,空)+d 32 =7+8=15f1(2,{ 4 }) = f0 (4,空)+d 42 =9+8=14f1(3,{ 2 }) = f0 (2,空)+d 23 =6+9=15f1(3,{ 4 }) = f0 (4,空)+d 43 =9+5=14f1(4,{ 2 }) = f0 (2,空)+d 24 =6+7=13f1(4,{ 3 }) = f0 (3,空)+d 34 =7+8=15当k=2时,从城市V1出发,中间经过2个城镇到达Vi的最短距离.f2(2,{ 3,4 }) = min[ f1(3,{4})+d32, f1(4,{3})+ d42] =min[14+8,15+5]=20P2(2,{3,4})=4f2(3,{ 2,4 })= min[14+9,13+5]=18P2(3,{2,4})=4f2(4,{ 2,3})= min[15+7,15+8]=22P2(4,{2,3})=2当k=3时:从城市V1出发,中间经过3个城镇最终回到Vi的最短距离.f3(1,{ 2,3,4 })= min[f2(2,{ 3,4 }) + d 21,f2(3,{ 2,4})+ d31,f2(4,{ 2,3 }) + d41]=min[20+8,18+5,22+6]=23P3(1,{2,3,4})=3逆推回去,货郎的最短路线是1 2 4 3 1,最短距离为23.四，源码[html] view plaincopyprint?1.#include<iostream>2.#include<iomanip>ing namespace std;4.5.int n;6.int cost[20][20]={};7.bool done[20]={1};8.int start = 0; //从城市0开始9.10.int imin(int num, int cur)11.{12.if(num==1) //递归调用的出口13.return cost[cur][start]; //所有节点的最后一个节点，最后返回最后一个节点到起点的路径14.15.int mincost = 10000;16.for(int i=0; i<n; i++)17.{18.cout<<i<<" i:"<<done[i]<<endl;19.if(!done[i] && i!=start) //该结点没加入且非起始点20.{21.if(mincost <= cost[cur][i]+cost[i][start])22.{23.continue; //其作用为结束本次循环。