算法设计与分析实验报告实验三旅行商问题
院系：
班级：计算机科学与技术
学号：
姓名：
任课教师：
成绩：
湘潭大学
2016年5月
实验三旅行商问题
一. 实验内容
分别编程实现回溯法和分支限界法求TSP问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。
二．实验目的
1、掌握回溯法和分支限界法解决问题的一般步骤，学会使用回溯法和分支限界法解决实际问题；
2、理解回溯法和分支限界法的异同及各自的适用范围。
三. 算法描述
旅行商问题的回溯法算法可描述如下：
Template
Class Traveling{
friend Type TSP(int ** , int[],int ,Type);
Private;
Void Backtrack(int i);
Int n, //图G的顶点数
*x; //当前解
*bestx; //当前最优解
Type **a, //图G的邻接矩阵
cc, //当前费用
bestc，//当前最优解
NoEdge; //无边标记
}；
Template
Void Traveling
{if(i ==n){
if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1] +a[x[n]][1] for(int j = 1;j<=n;j++) bestx[j] = x[j]; bestc == cc + a[x[n-1]][x[n]]+a[x[n]][1]}; }else{ For (int j = i;j<= n;j++) //是否可进入x[j]子树？ If(a[x[i-1]][x[j]] != NoEdge &&(cc+a[x[i-1]][x[j]] < bestc || bestc == NoEdge)){ //搜素子树 Swap(x[i],x[j]); cc += a[x[i-1]][x[i]]; Backtrack(i + 1); cc -= a[x[i-1]][x[i]]; Swap(x[i],x[j]); } } } Template Type TSP(Type**a, int v[], int n, Type NoEdge) {Traveling //初始化Y Y.x = new int [n+1]; //置x为单位排列 For(int i = 1;i <= n;i++) Y.x[i] = i; Y.a = a; Y.n = n; Y.bestc = NoEdge; Y.bestx = v; https://www.doczj.com/doc/f916314753.html, = 0; Y.NoEdge = NoEdge; //搜索x[2:n]的全排列 Y.Backtrack(2); Delete[]Y.x; Return Y.bestc; } 算法效率： 如果不考虑更新bestx所需的计算时间，则Backtrack需 要O（（n-1）！）计算时间。由于算法Backtrack在最坏情款下 可能需要更新当前最优解O（（n-1）！）次，每次更新需O（n） 计算时间，从而整个算法的计算时间复杂性为O（n！）。 旅行商问题的分支界限法算法可描述如下： 使用优先队列来存储活节点，优先队列中的每个活节点都存储从根到该活节点的相应路径。具体算法可描述如下： Template Class MinHeapNode{ firend Traveling Public: Operator Type() const {return lcost;} Private: Type lcost, //子树费用的下界 cc, //当前费用 rcost；//x[s:n-1]中定点最小出边费用和 Int s, //根节点到当前节点的路径为x[0:s] *x; //需要进一步搜索的顶点是x[s+1:n-1] }; 四. 算法实现 源程序代码 /*回溯法*/ #include #include #define N 5 double cc,//当前路径费用 bestc;//当前最优解费用 double a[N+1][N+1];//邻接矩阵，存放图的信息 int bestx[N+1];//当前最优解 int x[N+1];//当前解 void inputAjac() { int i,j; for(i=1;i<=N;i++) { for(j=i+1;j<=N;j++) { printf("请输入第%d个城市到第%d个城市所需路费为：",i,j); scanf("%lf",&a[i][j]); a[j][i]=a[i][j]; } } } void backtrack(int i) { if(i==N) { if(a[x[N-1]][x[N]]>0.0&&a[x[N]][x[1]]>0.0) { if(bestc<0.0||bestc>cc+a[x[N-1]][x[N]]+a[x[N]][x[1]]) { int j; for(j=1;j<=N;j++) { bestx[j]=x[j]; bestc=cc+a[x[N-1]][x[N]]+a[x[N]][x[1]]; } } } } else { int j; for(j=i;j<=N;j++) { if(a[x[i-1]][x[j]]>0.0) { if(bestc<0.0||bestc>cc+a[x[i-1]][x[j]]+a[x[j]][x[1]]) { int temp; cc+=a[x[i-1]][x[j]]; temp=x[i]; x[i]=x[j]; x[j]=temp; backtrack(i+1); temp=x[i]; x[i]=x[j]; x[j]=temp; cc-=a[x[i-1]][x[j]]; } } } } double tsp() { int i; for(i=1;i<=N;i++) {x[i]=i;} cc=0.0,bestc=-1.0; inputAjac(); backtrack(2); return bestc; } void output() { int i; for(i=1;i<=N;i++) { printf("%4d",bestx[i]); } // printf("\n"); } void main() { double start,finish; start=clock();//取开始时间 printf("城市个数：5\n"); printf("走%d个城市最少路费为：%lf\n",N,tsp()); printf("路径:"); output(); printf(" 1\n"); finish=clock(); printf("所需时间%f ms\n",(finish-start)); /*分支界限法*/ #include #include #include using namespace std; #define MAX_CITY_NUMBER 10 #define MAX_COST 10000000 int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]; int City_Size; int Best_Cost; int Best_Cost_Path[MAX_CITY_NUMBER]; typedef struct Node { int lcost; int cc; int rcost; int s; int x[MAX_CITY_NUMBER]; struct Node* pNext; } Node; typedef struct MiniHeap { Node* pHead; } MiniHeap; void InitMiniHeap(MiniHeap* pMiniHeap) { pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL; } void put(MiniHeap* pMiniHeap,Node node) { Node* next; Node* pre; Node* pinnode = new Node; pinnode->cc = https://www.doczj.com/doc/f916314753.html,; pinnode->lcost = node.lcost; pinnode->pNext = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL; for(int k=0; k pinnode->x[k] = node.x[k]; } pre = pMiniHeap->pHead; next = pMiniHeap->pHead->pNext; if(next == NULL) { pMiniHeap->pHead->pNext = pinnode; } else { while(next != NULL) { if((next->lcost) > (pinnode->lcost)) { pinnode->pNext = pre->pNext; pre->pNext = pinnode; break; } pre = next; next = next->pNext; } pre->pNext = pinnode; } } Node* RemoveMiniHeap(MiniHeap* pMiniHeap) { Node* pnode = NULL; if(pMiniHeap->pHead->pNext != NULL) { pnode = pMiniHeap->pHead->pNext; pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext; } return pnode; } void Traveler() { 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。 黄石理工学院 数学建模大型作业2011—2012 学年第1学期 目录 一．摘要 二．旅行问题 1.问题描述 2.符号说明 3.模型设计 4.建模求解 5.模型分析 6. 三．建模过程及心得体会 四．参考文件 一．摘要 本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。 关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型 二．旅行问题 问题描述 某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F 旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？ 在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。 模型设计 首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。 问题1. 分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立： 对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。假设ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则 ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66 1 ij ij i j d x =∑∑ (i ≠j) s.t. 6 1ij i x =∑=1 （i ≠j ；j=1,2, (6) 6 1 ij j x =∑=1 (i ≠j ；i=1,2, (6) 1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6) 其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，i u =访问城市的顺序数。 模型求解 运用LINGO ，输入程序： MODEL : !Traveling Sales Problem for the cities of six city; SETS : 旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称ＴＳＰ）是一个著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。如果用图论来描述，那就是已知带权图Ｇ＝ （Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。其中Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝表示ｎ个城市的集合，Ｌ＝｛ｌｉｊ｜ｃｉ，ｃｊ∈Ｃ｝是集合Ｃ中元素（城市）两两连接的集合，每一条边ｌｉｊ，都存在与之对应的权值ｄｉｊ，实际应用中ｄｉｊ可以表示距离、费用、时间、油量等。 ＴＳＰ的描述虽然简单， 解决起来却很困难。最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理很小规模的问题。旅行商问题属于 ＮＰ－ｃｏｍｐｌｅｔｅ问题， 是ＮＰ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙ－ｎｏｍｉｎａｌ）问题中最难的一类，不能在多项式时间内求解。如果有ｎ座城市，那么巡游路径共有（ｎ－１）！／２条，计算的时间和（ｎ－１）！成正比。当 城市数ｎ＝２０，巡回路径有１．２×１０１８种，ｎ＝１００， 巡回路径就有多达４．６×１０１５５种，而据估计宇宙中基本粒子数“仅仅只有”１０８７个。 尽管如此，随着算法研究的逐步深入和计算机技术飞速提高，对ＴＳＰ问题的研究不断取得进展。７０年来，被征服的ＴＳＰ规模从几十个城市增加到上万个城市。目前的最高记录是在２００４年５月，找到的巡游瑞典２４９７８个城镇的最优路径 （ｓｗ２４９７８）， 花费了８４．８个ＣＰＵ年。图１展示了ＴＳＰ的研究进展，最近的二三十年时间里，被攻克的ＴＳＰ规模高速增长，差不多是每十年增加一个数量级。照这样发展下去的话，再过２０年就能解决上百万个城市的ＴＳＰ，有专家甚至已经为此准备好了数据：全球１９０，４７１１个城市的坐标。当然，能不能达到这 个目标，有赖于未来计算技术的发展。 图１ＴＳＰ的发展 字母后面的数字表示城市数，“ｓｗ２４９７８”就是瑞典的 ２４９７８个城镇。 一、应用 旅行商问题具有重要的实际意义和工程背景。它一开始 是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域，下面举几个实例。 印制电路板转孔是ＴＳＰ应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为ＴＳＰ，孔相当于城市，孔到孔之间的移动时间就是距离。 为了避免大气干扰，使光学系统达到其衍射极限分辨率，欧美发达国家提出发展空间光干涉仪和综合孔径望远镜的计划。美国航空航天局有一个卫星群组成空间天文台（Ｓｐａｃｅ－ｂａｓｅｄＯｂｓｅｒｖａｔｏｒｉｅｓ）的计划， 用来探测宇宙起源和外星智慧生命。欧洲空间局也有类似的Ｄａｒｗｉｎ计划。对天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用ＴＳＰ来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。 美国国家卫生协会在人类基因排序工作中用ＴＳＰ方法绘制放射性杂交图。把ＤＮＡ片断作为城市，它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。 此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是，它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题，和ＴＳＰ同属ＮＰ－ｃｏｍｐｌｅｔｅ类，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的ＮＰ－ｃｏｍｐｌｅｔｅ类问题也能用多项式确定性算法解决。很多方法本来是从ＴＳＰ发展起来的，后来推广到其他ＮＰ－ｃｏｍｐｌｅｔｅ类问题上去。 二、ＴＳＰ求解方法 求解旅行商问题的方法可以分为两大类，一类是精确算法，目的是要找到理论最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。 （一）精确算法 如前面所述，穷举法和全局搜索算法属于精确算法，但 旅行商问题概述 郭靖扬 （电子科技大学光电信息学院， 四川成都６１００５４） 【摘要】旅行商问题是组合优化的经典问题，应用广泛，而且长期以来被作为ＮＰ－ｃｏｍｐｌｅｔｅ问题的理想研究平台。文章介绍 了旅行商问题的基础知识、应用，以及常用的求解方法。 【关键词】旅行商问题；组合优化；ＮＰ－ｃｏｍｐｌｅｔｅ；ｋ－ｏｐｔ；智能算法【中图分类号】ＴＰ１８２【文献标识码】Ａ【文章编号】１００８－１１５１（２００６）０８－０２２９－０２大众科技 ＤＡＺＨＯＮＧＫＥＪＩ２００６年第８期（总第９４期） Ｎｏ．８，２００６ （ＣｕｍｕｌａｔｉｖｅｌｙＮｏ．９４） 【收稿日期】２００６－０３－１８【作者简介】郭靖扬（１９８０－），四川宜宾人，电子科技大学光电信息学院硕士研究生。 ２２９－－ 有一个推销员，从城市1出发，要遍访城市2，3，…，n 各一次，最后返回城市1。已知从城市i 到j 的旅费为ij c ，问他应按怎样的次序访问这些城市，使得总旅费最少？ 可以用多种方法把TSP 表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。 在下述意义下，引入一些0-1整数变量： ij x ?? ?≠=其它情况，且到巡回路线是从，0,1j i j i 其目标只是使∑=n j i ij ij x c 1 ,为最小。 这里有两个明显的必须满足的条件： 访问城市i 后必须要有一个即将访问的确切城市；访问城市j 前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。 n i x n j ij ,,2,1, 11 ==∑= n j x n i ij ,,2,1, 11 ==∑= 到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP 来说并不充分，仅仅是必要条件。例如： 以上两个条件都满足，但它显然不是TSP 的解，它存在两个子巡回。 这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量 ),,3,2(n i u i =附加到问题中。可把这些变量看作是连续的（最然这些变量在最 优解中取普通的整数值）。现在附加下面形式的约束条件 n j i n x n u u ij j i ≤≠≤-≤+-2, 1。 为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约 束条件；（2）全部巡回都满足该约束条件。 首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为121i i i i k ，则必有(对于所有的i k 都满足大 于2的限制条件) 1 11132121-≤+--≤+--≤+-n n u u n n u u n n u u i i i i i i k 把这k 个式子相加，有 1-≤n n ，矛盾！ 故假设不正确，结论（1）得证。 下面证明（2），采用构造法。对于任意的总巡回1111-n i i ，可取 =i u 访问城市i 的顺序数。 下面来证明总巡回满足该约束条件。 1 2 3 4 5 6 《算法设计与分析》实验报告一 学号：姓名： 日期：20161230 得分： 一、实验内容： TSP问题 二、所用算法的基本思想及复杂度分析： 1、蛮力法 1）基本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点到自身节点的距离为无穷大。在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找。。。然后构造各行允许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会返回k=0，即实现访问源节点，得出一条简单回路。 2）复杂度分析 基本语句是访问下一个行列中最小的点，主要操作是求平方，假设有n个点，则计算的次 页脚内容1 数为n^2-n。T(n)=n*(n-1)=O(n^2)。 2、动态规划法 1）基本思想 假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。 推导：(分情况来讨论) ①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的城市3->城市0(0 为起点城市)。此时d(i, V’)=Cis(就是城市i 到城市s 的距离)、 ②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个， 并求出最优解。 d(i, V’)=min{Cik +d(k, V’-{k})} 注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。 综上所述，TSP问题的动态规划方程就出来了： 2）复杂度分析 和蛮力法相比，动态规划求解tsp问题，把原来时间复杂性O（n！）的排列转化为组合问题，从而降低了时间复杂度，但仍需要指数时间。 3、回溯法 1）基本思想 页脚内容2 人工智能原理 实验报告 模拟退火算法解决TSP问题 目录 1 旅行商问题和模拟退火算法........................................... 错误!未定义书签。 旅行商问题................................................................... 错误!未定义书签。 旅行商问题的描述................................................. 错误!未定义书签。 模拟退火算法............................................................... 错误!未定义书签。 基本思想................................................................. 错误!未定义书签。 2 TSP模拟退火算法的实现................................................ 错误!未定义书签。 TSP算法实现............................................................... 错误!未定义书签。 TSP算法描述......................................................... 错误!未定义书签。 TSP算法流程......................................................... 错误!未定义书签。 TSP的C实现 .............................................................. 错误!未定义书签。 加载数据文件......................................................... 错误!未定义书签。 计算总距离的函数................................................. 错误!未定义书签。 交换城市的函数..................................................... 错误!未定义书签。 执行模拟退火的函数............................................. 错误!未定义书签。 实验结果......................................................................... 错误!未定义书签。 小结................................................................................. 错误!未定义书签。3源代码................................................................................ 错误!未定义书签。 以点0表示旅行商的出发城市，称为源点，点1,2, ,l 表示m 个旅行商需访 问的城市。MTSP 问题的数学模型可以表示为： 令10ij x ?=??弧(i,j)在线路上 弧(i,j)不在线路上 模型表示如下： 0000min 10,1,,10,1,,()01,0,1,,R R ij ij i j R ij i R ij j ij ij z d x x j R x i R X x S x i j R ====?=?? ?==????==??=∈??==?∑∑∑∑或 式中：1;ij R m l d =+-为增广费用。若用(,1,,)ij c i j l =表示旅行商经过对应弧度(,)i j 所花的费用，如时间、距离、花费等，那么给ij c 增加(1)m -行和(1)m -列，每一新的行或列是ij c 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用ij d 。 一般MTSP 中，旅行商访问l 个城市必须满足以下2个条件。 条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m 条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP ，可通过附加虚拟城市的方法把MTSP 转化为TSP 。将另外(1)m -个旅行商理解为(1)m -个虚拟城市，这(1)m -个虚拟城市标号分别为1,2,,1,l l l m +++-，它们与城市0具有相同的坐标(即相同位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP 中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(1)m -个虚拟城市到原点的距离为 00(,0,1,,1),ij c M i j l l m M ==++-为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制(1)m -个，m 个源点编号为0,1,1,l l m ++-每一个同源点0一样与其他 #include { /*if(mincost <= cost[cur][i]+cost[i][start]) { continue; //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break } */ visit[i] = 1; //递归调用时，防止重复调用 int value = cost[cur][i] + imin(num-1, i); if(mincost > value) { mincost = value; } visit[i] = 0;//本次递归调用完毕，让下次递归调用 } } return mincost; } int main() { int i,j; // int k,e,w; n=4; int cc[4][4]={{0,10,15,20}, {5,0,9,10}, {6,13,0,12}, {8,8,9,0}}; for(i=0; i 运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的 i j=L位置上的数表示（其中∞表示两个客户之间无直接的路线到i j(,1,,10) (,) 达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给 客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能 装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送 实验报告：用遗传算法解决旅行商问题的简单实现 实验目的：编写程序实现用遗传算法解决旅行商问题，研究遗传算法的工作原理和收敛性质。 实验者： 问题描述：TSP是一个具有广泛应用背景和重要理论价值的组合优化难题，TSP问题可以简单的描述为：已知N个城市之间的相互距离．现有一个旅行商必须遍历这N个城市，并且每个城市只能访一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使旅行路线的总长度最短？ 本次实验的目标问题中国大陆31个大城市的公路旅行商问题，数据来源是《中国大城市公路里程表》（后附）。 需求分析：TSP已经被证明是一个NP—Hard问题，即找不到一种算法能在多项式时间内求得问题的最优解。利用遗传算法，在一定时间内求得近似最优解的可能性比较大。实验目标是： 1）设计用遗传算法解决TSP问题的程序； 2）求出该TSP问题的（近似）最短路程； 3）求得相应的城市遍历序列； 4）检查算法收敛性，求解决该问题的（近似）最优遗传参数。 算法分析： 1．算法基本流程 2．编码策略与初始群体设定 TSP的一般编码策略主要有二进制表示、次序表示、路径表示、矩阵表示和边表示等。而路径编码是最直观的方式，以城市序号作为遗传基因。在本实验中，我们用一个N维向量来表示一个个体，N是城市总数，元素表示城市遍历顺序，以最后一个到达的城市为结束。则群体用一个N * POP的矩阵表示，POP为群体中的人口（个体数）。初始群体在空间中自动生成。 3．适应度函数及结束条件 适应度函数采用题目的目标函数——路径的总路程（包括回到出发点）。适应度越低，个体越优秀。由于暂时无法先验估计收敛性和目标结果，所以以一个参数，最大遗传代数MAXGEN作为程序结束控制。 4．遗传算子设计 遗传算子的设计方法主要有两大类：自然算法和贪心算法。自然算法是以大自然的进化规律为依据，大体采用“优胜劣汰”的机制来进行遗传；贪心算法则是以迅速收敛为目标，对个体进行更严格的选择和遗传处理。 算法设计与分析实验报告实验三旅行商问题 院系： 班级：计算机科学与技术 学号： 姓名： 任课教师： 成绩： 湘潭大学 2016年5月 实验三旅行商问题 一. 实验内容 分别编程实现回溯法和分支限界法求TSP问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。 二．实验目的 1、掌握回溯法和分支限界法解决问题的一般步骤，学会使用回溯法和分支限界法解决实际问题； 2、理解回溯法和分支限界法的异同及各自的适用范围。 三. 算法描述 旅行商问题的回溯法算法可描述如下： Template if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&& (cc+a[x[n-1]][x[n]]+a[x[n]][1] +a[x[n]][1] 2012 年第一学期研究生课程考核 （实验报告、研究报告） 考核科目：算法分析与复杂性理论 学生所在学院：计算机科学与技术学院 学生所在学科：计算机应用技术 姓名： 学号： 学生类别：研究生 一、实验目的 1.通过TSP算法的具体实现，加深对算法复杂分析的理解。 2.通过TSP算法的具体实现，提高对NP完全问题的认识。 3.通过TSP算法的具体实现，理解不确定性算法。 4.通过TSP算法的具体实现，理解不确定性算法。 二、实验环境 实验平台：Visual C++ 6.0 编程语言：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便完成了一次循环，此时蚂蚁走所走过的路径便是问题的一个解。是一个启发式因子，表示蚂蚁从城市i转移到城市j的期望程度，在蚂蚁算法中，通 常取 城市ij之间距离的倒数。α和β分别表示路径上信息量和启发示因子的重要程度。 当所有蚂蚁完成一次循环后，各路径上的信息量要根据下面的公式进行调整： 令x ij 弧(i,j)在线路上 弧(i,j) 不在线路上 以点0表示旅行商的出发城市，称为源点，点1,2丄，1表示m个旅行商需访 问的城市。MTSP问题的数学模型可以表示为: 模型表示如下: RR min z d ij x ij i0j0 R x ij 1 j 0,1,L ,R i0 R x ij 1 i 0,1,L ,R j0 X (x ij ) S x ij 0或1 i, j 0,1,L ,R 式中：R m l 1;d ij为增广费用。若用C ij (i,j 1,L ,1)表示旅行商经过对应弧度(i, j)所花的费用，如时间、距离、花费等，那么给q增加(m 1)行和(m 1)列，每一新的行或列是c ij 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用d ij 。 一般MTSP中，旅行商访问I个城市必须满足以下2个条件。 条件 1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP，可通过附加虚拟城市的方法把 MTSP转化为TSP。 将另外(m 1)个旅行商理解为(m 1)个虚拟城市，这(m 1)个虚拟城市标号分 别为l 1,l 2,L ,l m 1,，它们与城市0具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(m 1)个虚拟城市到原点的距离为 c ij M0(i, j 0,l 1,L ,l m 1 ) , M 0为一无穷大的正数(即永远不能达到) ，到其他各点距离与原点一致，这样遗传算法就不会出现 0-0-0 的途径。将源点 0 复制(m 1)个，m个源点编号为0,1 1,L l m 1,每一个同源点0 —样与其他 T S P问题算法分析集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289- 算法第二次大作业 TSP问题算法分析 021251班 王昱（02125029） 一．问题描述 “TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。 TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。 二．算法描述 2.1分支界限法 2.1.1算法思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 2.1.2算法设计说明 设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn) 若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。 再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值 bound(x1,…,xn)。 2.2A*算法 算法思想 对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有 f*(n)=g*(n)+h*(n)。 （实验报告、研究报告） 考核科目：算法分析与复杂性理论 学生所在学院：计算机科学与技术学院 学生所在学科：计算机应用技术 姓名： 学号： 学生类别：研究生 一、实验目的 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便完成了一次循环，此时蚂蚁走所走过的路径便是问题的一个解。是一个启发式因子，表示蚂蚁从城市i转移到城市j的期望程度，在蚂蚁算法中， 通常取 城市ij之间距离的倒数。α和β分别表示路径上信息量和启发示因子的重要程度。 当所有蚂蚁完成一次循环后，各路径上的信息量要根据下面的公式进行调整： 其中表示路径上信息的蒸发系数；表示信息的保留系数；表示本次循环路径ij上信息的增量。表示第k只蚂蚁在本次循环中留在路 摘要 本文分析比较了tsp问题的动态规划算法，分支界限法，近似等算法。分析了旅行商问题的时间度特点，针对启发式算法求解旅行商问题中存在的一些问题提出了改进算法。此算法将群体分为若干小子集，并用启发式交叉算子，以较好利用父代个体的有效信息，达到快速收敛的效果，实验表明此算法能提高寻优速度，解得质量也有所提高。 关键词：旅行商问题TSP Abstract this paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision. Keywords traveling salesman problem; genetic algorithm; subset; henristic crossover operator 目录 1、摘要--------------------------------------------------------------1 2、Abstract---------------------------------------------------------1 3、Tsp问题的提法------------------------------------------------2 4、回溯法求Tsp问题--------------------------------------------3 5、分支限界法求Tsp问题--------------------------------------7 6、近似算法求解Tsp问题-------------------------------------10 7、动态规划算法解Tsp问题----------------------------------12 姓名学号 实验成 绩 华中师范大学计算机科学系 实验报告书 实验题目：基于Boltzmann Machine的模拟退火算法解决TSP问题课程名称：智能计算 主讲教师：沈显君 辅导教师： 课程编号： 班级：2011级硕士 实验时间：2011.12.27 实验题目 基于Boltzmann Machine的模拟退火算法解决TSP问题 实验环境 操作系统：Microsoft Windows XP Professional 编程平台：Microsoft Visual C++ 6.0 TSP问题 旅行商问题（TSP，Traveling Salesman Problem）是著名的组合优化问题之一。可以描述如下：设n为城市数目，D=[d ij]为n*n的矩阵，d ij表示从城市i到城市j的距离，其中i，j=0,1,…,n-1，则TSP的解就是从某一城市出发经过所有城市恰好一次最后回到出发点的最短路径。 Boltzmann Machine 波尔兹曼机（Boltzmann Machine）是一种多层网络，由输入层，输出层和隐层构成，隐单元之间相互连接。网络状态按照概率分布变化，网络中单元状态可取0,1两种值，每个单元的状态的转换是一随机函数。如把状态的0或1看成拒绝或接受某一假设，则两者的连接强度可理解为两个假设之间的一致程度。 模拟退火(Simulated Annealing) 模拟退火算法借鉴了金属制品加工的退火过程，即为了提高金属制品的韧性和硬度将金属制品缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。 金属制品中的原子结构代表一种状态，每个状态对应一个能量，这是由原子TSP问题求解实验报告
旅行商问题数学建模
旅行商问题概述_郭靖扬
单旅行商问题的算法
TSP问题的解决方案
模拟退火算法的旅行商问题
多旅行商问题模型
货郎担问题或旅行商问题动态规划算法
数学建模运输问题
实验报告：遗传算法在解决旅行商问题的应用
[精品文档]旅行商问题
TSP实验报告
多旅行商问题模型
TSP问题算法分析
TSP实验报告
Tsp问题的几种算法的分析
基于Boltzmann机的求解TSP问题的实验报告
相关主题
文本预览