[精品文档]旅行商问题

一、 问题描述旅行商问题:给定一个完全无向带权图G=(V,E)，其每条边(u,v)∈E 有一非负整数权值w(u,v)。

要求找出G 的一条经过每个顶点一次且仅经过一次的回路，使得该回路上所有边的权值之和尽可能地小。

二、 算法分析旅行商问题的各个城市间的距离可以用代价矩阵来表示，就是邻接矩阵表示法。

如果E j i ∉),(，则∞=ij c 。

先说明旅行商问题具有最优解结构。

设s s s s p ,,.....,,21是从s 出发的一条路径长度最短的简单回路，假设从s 到下一个城市1s 已经求出，则问题转化为求1s 到S 的最短路径，显然s s s s p ,,.....,,21一定构成一条从1s 到S 的最短路径，如果不然，设s r r r s q ,,.....,,,211是一条从1s 到S 的最短路径且经过n-1个城市，则s r r r s s q ,,.....,,,,211将是从S 出发的路径长度最短的简单回路且比s s s s s p ,,.....,,,21要短，从而导致矛盾。

所以，旅行商问题一定满足最优性原理。

穷举法：穷举法解决旅行商问题的思路很简单，就是遍历所有可能的情况，然后把符合条件（最短）的路径找到并输出可以了。

动态规划法：假设从顶点i 出发，令)',(V i d 表示从顶点i 出发经过V ’中各个顶点一次且仅一次，最后回到出发点i 的最短路径的长度，开始时，V ’=V-{i}，于是，旅行商问题的动态规划函数为：)({}),()'})}({',(min{)',(i k c k d V k k V k d c V i d ki ik ≠=∈-+=)2()1( 下面举个实例说明算法的执行过程。

下图是无向带权图的邻接矩阵表示法：⎢⎢⎢⎢⎣⎡∞=763C323∞ 226∞ ⎥⎥⎥⎥⎦⎤∞237在上图所示的带权图中，从城市0出发，经城市1，2，3然后回到城市0的最短路径长度为：})}2,1{,3(}),3,1{,2(}),3,2{,1(min{})3,2,1{,0(030201d c d c d c d +++=这是最后一个阶段的决策，它必须知道})3,1{,3(}),3,1{,2(}),3,2{,1(d d d 的计算结果，而：})}2{,3(}),3{,2(min{})3,2{,1(1312d c d c d ++=})}1{,3(}),3{,1(min{})3,1{,2(2321d c d c d ++= })}1{,2(}),2{,1(min{})2,1{,3(3231d c d c d ++=这一阶段的决策又依赖于下面的计算结果：{}),2(})2{,3({}),,3(})3{,2({}),,2(})2{,1(322312d c d d c d d c d +=+=+= {}),1(})1{,3({}),,1(})1{,2({}),,3(})3{,1(312113d c d d c d d c d +=+=+= 而下面的就可以直接获得（括号中是该策略引起的路径）：)03(7{}),3(),02(6{}),2(),01(3})0{,1(302010>-==>-==>-==c d c d c d向前推导，可以得到：)23(862{}),2(})2{,3()13(633{}),1(})1{,3()12(532{}),1(})1{,2()32(972{}),3(})3{,2()31(1073{}),3(})3{,1()21(862{}),2(})2{,1(323121231312>-=+=+=>-=+=+=>-=+=+=>-=+=+=>-=+=+=>-=+=+=d c d d c d d c d d c d d c d d c d再向前推导有：)23(7}7,11min{})}1{,2(}),2{,1(min{})2,1{,3()32(8}8,12min{})}1{,3(}),3{,1(min{})3,1{,2()21(11}11,11min{})}2{,3(}),3{,2(min{})3,2{,1(323123211312>-==++=>-==++=>-==++=d c d c d d c d c d d c d c d 最后有：})}2,1{,3(}),3,1{,2(}),3,2{,1(min(})3,2,1{,0(030201d c d c d c d +++=)302010(14}14,14,14min{}77,86,113min{>->->-==+++=or or所以，从顶点0出发的旅行商问题的最短路径长度为14，其中一条路径为01320>->->->-。

int size = str_arr.length; int[] int_arr = new int[size];
for(int i = 0; i < size; i ++){ int_arr[i] = Integer.valueOf(str_arr[i]);
}
return int_arr; }
//获取所有路径中最短的路径 private int get_min_distance(){
FileInputStream fi = new FileInputStream(file);
InputStreamReader ir = new InputStreamReader(fi);
BufferedReader br = new BufferedReader(ir);
//------------------------------------
城市之间的距离：通过 n*n 矩阵 city_distance 表示，其中 n 表示城市的个数。编号为 k 的城市到各个城市之间的距离可以从第（k-1）行获取。
open 表：用队列表示，城市结点进入队列之前需要根据估计值 fvalue 按升序排列。
close 表：用向量表示。 搜索图：搜索图通过 open 表构建，将路径的编号保存在一个数组 id_list 中。 四、实验结果和分析 1、输入数据 第一行的数Байду номын сангаас 8 表示城市结点的个数，后面是一个 8*8 的数组，数组的值表示城市之 间的距离。任何一个结点到自身的距离是 0，数组中的第 0 行表示第 1 个城市到各个城市 之间的距离，其他的可类推。
Astar 算法求解旅行商问题
一、问题描述 一共有 n 个城市，某推销员从其中的一个城市 A 出发经过每个城市一次且仅一次后回

图算法--旅⾏商问题旅⾏商问题的描述试想⼀下，⼀个业务员因⼯作需要必须访问多个城市。

他的⽬标是每个城市只访问⼀次，并且尽可能地缩短旅⾏的距离，最终返回到他开始旅⾏的地点，这就是旅⾏商问题的主要思想。

在⼀幅图中，访问每个顶点⼀次，并最终返回起始顶点，这个访问的轨迹称为哈密顿圈。

要解决旅⾏商问题，需要⽤图G=（V，E）作为模型，寻找图中最短的哈密顿圈。

G是⼀个完整的、⽆⽅向的带权图，其中V代表将要访问的顶点的集合，E为连接这些顶点的边的集合。

E中每条边的权值由顶点之间的距离决定。

由于G中⼀个完整的、⽆⽅向的图，因此E包含V（V-1）/2条边。

事实上，旅⾏商问题是⼀种特殊的⾮多项式时间问题，称为NP完全问题。

NP完全问题是指那些多项式时间算法未知，倘没有证据证明没有解决的可能性的问题。

考虑到这种思想，通常⽤⼀种近似算法来解决旅⾏商问题。

最近邻点法的应⽤⼀种近似的计算旅⾏商路线的⽅法就是使⽤最近邻点法。

其运算过程如下：从⼀条仅包含起始顶点的路线开始，将此顶点涂⿊。

其他顶点为⽩⾊，在将其他顶点加⼊此路线中后，再将相应顶点涂⿊。

接着，对于每个不在路线中的顶点v，要为最后加⼊路线的顶点u与v之间的边计算权值。

在旅⾏商问题中，u与v之间边的权值就是u到v 之间的距离。

这个距离可以⽤每个顶点的坐标计算得到。

两个点（x1，y1）与（x2，y2）之间距离的计算公式如下：r = √（x2 - x1）2 + （y2 - y1）2 （注意是求和的平⽅根）利⽤这个公式，选择最接近u的顶点，将其涂⿊，同时将其加⼊路线中。

接着重复这个过程，直到所有的顶点都涂成⿊⾊。

此时再将起始顶点加⼊路线中，从⽽形成⼀个完整的回路。

下图展⽰了使⽤最近邻点法来解决旅⾏商问题的⽅法。

通常，在为旅⾏商问题构造⼀个图时，每个顶点之间相连的边不会显⽰表⽰出来，因为这种表⽰会让图不清晰了，也没有必要。

在图中，每个顶点旁边都显⽰其坐标值，虚线表⽰在此阶段需要⽐较距离的边。

旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。

该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。

本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。

关键字：旅行商问题；动态规划法；贪心法；分支限界法1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。

研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。

关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。

归纳起来，目前主要算法可分成传统优化算法和现代优化算法。

在传统优化算法中又可分为：最优解算法和近似方法。

最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。

但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。

2正文2.1蛮力法2.1.1蛮力法的设计思想蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。

一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。

在基本的数据结构中，一次处理每个元素的方法是遍历。

2.1.2算法讨论用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。

如对于图1，我们求解过程如下：（1）路径：1->2->3->4->1；路径长度：18；（2）路径：1->2->4->3->1；路径长度：11；（3）路径：1->3->2->4->1；路径长度：23；（4）路径：1->3->4->2->1；路径长度：11；（5） 路径：1->4->2->3->1；路径长度：18；（6） 路径：1->4->3->2->1；路径长度：18；从中，我们可以知道，路径（2）和（4）路径长度最短。

第7章 旅行商问题
目录第7章 旅行商问题1.问题概述2.求解算法2.1.下界和上界算法2.2.分支定界法2.3.动态规划法2.5.近似算法2.5.竞赛题
2
§7-1 问题概述一 、数学模型1.标准TSP旅行商问题(简称TSP ), 也称货郎担问题或 旅行推销员问题，是运筹学中一个著名的问题，其 一般提法为：有一个旅行商从城市1出发，需要到 城市2、3、 …、n 去推销货物，最后返回城市1,若 任意两个城市间的距离已知，则该旅行商应如何选 择其最佳行走路线?
18
TS 多面体研究中的一个重要问题就是寻找能导出Q” 最大面的不等式， Grotschel 等人发现了一类很重要的能导 出最大面的梳子不等式，并予以了证明。此外，还有其它 能导出最大面的不等式，如团树不等式等。可见， Q" 的最 大面极多，曾经计算过由梳子不等式所导出的最大面个数 如表7-1所示：表 7 - 1
27
对结点i的e(i)1, 边e(i)1 的一个结点为i, 另 一 个结点为j=dmi n_j(i,1), 若e(i)1 也是结点j 关联边 中最小的两条边之一，即i =dmin_j(j,1) 或 i=dmin_j(j,2 ), 则对边e(i)1 来说就不需要调整，否则 按以下方式调整：
8
从严格的数学意义而言，瓶颈TSP (简称BTSP )并没有降低问题的难度，也未能提供任何特殊的解决 办法。瓶颈TSP的数学模型与标准TSP类似，仅目标函 数不同：min Z=max{d,·xi|i,jeV}
由于目标函数为瓶颈值，故求得的最佳巡回路 线与标准TSP的往往截然不同。
16
称X为路线T的关联向量，其m=n(n-2)/2 个分量中，恰好 有个为1,其余的都为0。图有许多H amilt on回路，设为T₁.T₂.…T,, 对应的关联向 量记为X₁,X₂…X 。, 在m维空间Rm中，考虑这些向量生成的 凸包( convex hull) Q":

旅⾏商问题+背包问题--经典问题问题描述：旅⾏商问题（Traveling Salesman Problem,TSP）是旅⾏商要到若⼲个城市旅⾏，各城市之间的费⽤是已知的，为了节省费⽤，旅⾏商决定从所在城市出发，到每个城市旅⾏⼀次后返回初始城市，问他应选择什么样的路线才能使所⾛的总费⽤最短？此问题可描述如下：设G=(V,E)是⼀个具有边成本cij的有向图，cij的定义如下，对于所有的i和j，cij>0,若<i,j>不属于E，则cij=∞。

令|V|=n，并假设n>1。

G的⼀条周游路线是包含V中每个结点的⼀个有向环，周游路线的成本是此路线上所有边的成本和。

旅⾏商问题（Traveling Saleman Problem，TSP）⼜译为旅⾏推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单⼀旅⾏者由起点出发，通过所有给定的需求点之后，最后再回到原点的最⼩路径成本。

最早的旅⾏商问题的数学规划是由Dantzig（1959）等⼈提出。

　TSP问题在物流中的描述是对应⼀个物流配送公司，欲将n个客户的订货沿最短路线全部送到。

如何确定最短路线。

TSP问题最简单的求解⽅法是枚举法。

它的解是多维的、多局部极值的、趋于⽆穷⼤的复杂解的空间，搜索空间是n个点的所有排列的集合，⼤⼩为（n-1）。

可以形象地把解空间看成是⼀个⽆穷⼤的丘陵地带，各⼭峰或⼭⾕的⾼度即是问题的极值。

求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到⼭顶或⾕底的过程。

问题分析旅⾏商问题要从图G的所有周游路线中求取最⼩成本的周游路线，⽽从初始点出发的周游路线⼀共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅⾏商问题是⼀个排列问题。

排列问题⽐⼦集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列。

通过枚举(n-1)!条周游路线，从中找出⼀条具有最⼩成本的周游路线的算法，其计算时间显然为O(n!)。

• 2004 年，一个具有 24978 个城市的旅行商问题的最优路 径由 Applegate, Bixby,Chavátal, Cook 和 Helsgaun 找到。 这是到目前为止精确找到最优解的最大规模的旅行商问题.
• 旅行商问题吸引了越来越多的人对它进行研究。 其中，有数学家，计算机科学家，运筹学家，还 有一些其它领域的研究者。
• 增加变异概率实际上是把遗传算法退化成了一种 纯粹的随机搜索，所谓的自适应也无从谈起！
灾变思想
• 那么如何解决遗传算法容易陷入局部极值的问题呢？ • 让我们来看看大自然提供的方案。六千五百万年以前，恐
龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如 果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正 是恐龙的灭绝才使灵长类动物有了充分进化的余地。 • 事实上地球至少经历了5次物种大灭绝，每次物种灭绝都 给更加高级的生物提供了充分进化的余地。 • 所以要跳出局部极值就必须杀死当前所有的优秀个体，从 而让远离当前极值的点有充分的进化余地。这就是灾变思 想。
Traveling Salesman Problem （TSP）
旅行商问题的发展历史
• 旅行商问题，也称货郎担问题，是一个较 古老的问题。其起源已经有些模糊了。最 早大概可以追溯到 1759 年 Euler 提出的骑 士旅行问题。
• 十九世纪初，爱尔兰数学家William R. Hamilton和英国数学家Thomas P. Kirkman 研究过一些与旅行商问题相关的数学问题。
• 对旅行商问题的研究经过几十年的发展，已经产生了许多 其它扩展形式,例如多旅行商问题(Multi-Salesman Problem),多目标旅行商问题(Multi-Objective TSP)等等。

旅行商问题
旅行商问题（Traveling Salesman Problem，TSP）是一个有着悠久历史的经典优化问题，也是一个非常重要的研究领域。

贪婪法是常用的解决TSP问题的算法之一。

它的思想是每次都选择与当前位置最近的城市，最后回到出发城市，进而完成一个TSP问题的解决。

贪婪法的TSP问题可以通过求解最佳匹配（Minimazing Tour Cost）而简单地实现。

它要求先求出各城市带来的价值，然后将价值作为各城市之间的距离权重，计算出最佳匹配。

另外，贪婪算法解决TSP问题还可以使用基于穷举搜索的解法。

它对所有有可能存在的路线进行排查，从而最终求出最短路径长度。

但是，由于TSP问题的解空间很大，穷举搜索的解法无法保证能够求出最优解，运行时间也增加了很多，贪婪算法求解TSP问题速度较快。

总之，贪婪算法解决TSP问题能够在短时间内快速求出最短路径，但是求得的解不一定是最优解，而且TSP问题求解的解空间非常大，仍然有很多未知问题需要进一步研究。

3.5 建议
2.1.2 TSP 问题的动态规划函数 假设从顶点 i 出发，令 d(i,V ') 表示从顶点 i 出发经过 V ' 中各个顶点一次且仅
一次，最后回到出发点 i 的最短路径长度，开始时， V ' V i ，于是， TSP 问
题的动态规划函数为： d (i ,V ') min cik d (k,V
k ) (k V ')
贪心法求解 TSP 问题的贪心策略是显然的，至少有两种贪心策略是合理的： 最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。 最近邻点策略： 从任意城市出发， 每次在没有到过的城市中选择距离已选择的城 市中最近的一个，直到经过了所有的城市，最后回到出发城市。 2.2.3 算法分析 1．P={ }; 2．V=V-{u0}; u=u0; //从顶点 u0 出发 3．循环直到集合 P 中包含 n-1 条边
3.3 两者比较
动态规划法相对贪心法来说虽然要精确些，但代码相对繁杂很多，对时间和 空间要求很多， 仅适用于城市数量较小的情况。 贪心法虽然比较简单， 实现起来 比较容易， 但不是很精确， 当图中顶点个数较多并且各边的代价值分布比较均匀 时，贪心法可以给出较好的近似解， 不过，这个近似解以何种程度近似于最优解， 却难以保证。
swap(&pArr[i],&pArr[j]);
//更新当前累加值 ,是 i-1 与 i 的
g_iCurResult += g_iArr[ pArr[i-1] ][ pArr[i] ];
//递归
backTrace(i+1,pArr);
//回溯，清空累加值；能够走到这里，说明上述结果不是最
优解，需要向求解树上一层回退

旅行商问题的解决方法嘿，咱今天就来聊聊旅行商问题！这就好比你是个超级大忙人，要去好多好多地方办事，还得想办法怎么走才能最省事儿、最省钱、最省时间呢！你想想看，要是让你自己随便规划路线，那得多头疼啊！可能会走好多冤枉路，浪费好多精力和金钱。

那怎么办呢？咱可以先把要去的地方都标记出来，就像给每个地方贴上一个小标签。

然后呢，试着把这些地方连接起来，看看有多少种可能的路线。

哇，这可不少呢！就好像你面前有一堆乱七八糟的线，得一根一根地理清楚。

这时候，咱就得动点小脑筋啦！可以从距离比较近的地方开始考虑呀。

比如说，两个地方挨得很近，那就先去那儿呗，这样不就少跑点路嘛。

这就跟你去菜市场买菜一样，肯定先挑离家近的那个菜市场呀，对吧？还有哦，咱可以看看哪些地方比较重要，先去重要的地方。

比如说，有个地方有特别重要的业务要谈，那肯定得优先去那儿呀。

这就好像你要去见一个特别重要的人，肯定得先把他的事儿搞定咯。

有时候啊，光靠自己想可能还不够，咱可以借助一些工具呀。

就像你爬山的时候，需要一根拐杖来帮忙一样。

有些专门的软件或者算法就能帮咱找到最优的路线呢。

咱也别死脑筋，有时候换个角度想想，可能就有新的发现。

比如说，从反方向走会不会更好呢？这就像你走路，走不通的时候，换个方向说不定就柳暗花明啦。

哎呀，解决旅行商问题可不简单呢，但只要咱有耐心，多试试，总能找到最合适的办法。

就像解一道难题一样，刚开始觉得难，慢慢研究，总会找到答案的。

你想想，要是能完美地解决这个问题，那出去办事、旅游得多轻松呀！不用再担心走冤枉路，浪费时间和精力。

而且，这也是一种锻炼咱思维能力的好办法呢。

所以呀，别害怕旅行商问题，大胆地去尝试，去探索，相信你一定能找到属于自己的最佳路线！这就好比在茫茫人海中找到属于自己的那条路，虽然不容易，但一旦找到了，那可就太棒啦！。

表示连接两城市的路，边上的权W（e）表示距
离（或时间或费用）。于是旅行推销员问题就
成为在加权图中寻找一条经过每个顶点正好一
次的最短圈的问题，即求最佳Hamilton 圈的
问题。
基本概念
•： 1) 哈米尔顿路径(H路径): 经过图G每个顶点正好一次的路径; 2) 哈米尔顿圈(H圈)；经过G的每个顶点正好一次的圈; 3) 哈米尔顿图(H图): 4) 最佳H圈: 含H圈的图。
引 例
公路边的数字为该路段的公里数.
引 例
2. 问题分析 本题给出了某县的公路网络图，要求在不同的条件下， 灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之 间的公路看作此图对应顶点间的边，各条公路的长度（或 行驶时间）看作对应边上的权，所给公路网就转化为加权 图，问题就转化为图论中一类称之为旅行推销员问题， 即在给定的加权网络图中寻找从给定点O出发，行遍所有
参考书： 1.龚劬 《图论与网络最优化算法》 重庆大学出版社,2009 2.西北工业大学数学建模指导委员会 《数学建模简明教程》 高等教育出版社
主讲：重庆大学 龚 劬
主要内容
引 例 基本概念 TSP模型的应用 算法简介 最佳灾情巡视路线的模型 的建立与求解
引 例
•：
1. 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题： 今年(1998年)夏天某县遭受水灾. 为考察灾情、
对角线完全算法
定理 设D’是图G的距离矩阵D的简化矩阵，则D’对应 的图G’的最佳（有向）H圈也是原图G的最佳（有向） H圈。G’只是边权与G不同，去掉权之后完全一样。因 此当简化矩阵中的零元素构成H圈时，该H圈也是原问 题的最佳H圈。
罚数: 在图G的距离矩阵的简化矩阵D’中，第i行的最 小元素与次小元素之差称为第i行的罚数，记为P(i)。 第j列的最小元素与次小元素之差称为第j列的罚数， 记为P’(j)，某行（或列）的罚数即是若H圈不选择该 行（或列）的最小元素会使其权增加的最小值。

机动 上页 下页 返回 结束
2 子哈密顿圈法 定义2 任意图G中包含G的所有顶点的圈称为G的 Hamilton圈，简称H圈。 具有H圈的图称为Hamilton图, 简称H图。 设 C´是图 G 的子图 G ´的哈密顿圈， G 的 k 个不 在 C ´上的顶点为 v1,v2,…,vk， 它们距C´的最短路长分 别为w1,w2,…,wk 。 则问题的较优解 w = w ( C´) + 2 (w1+ w2+ …+ wk ) 这也是一种近似算法。 我们注意到，图G不是哈密顿图，没有哈 密顿圈。 但在去掉顶点 C2， C4， C6， C7， C10，C11 中的任意一个后，G就变成哈密顿图了。
我们可以选择这样的飞行 从C1 沿圈CH 飞到 路线：
C10
C3
C5 ， 然后飞到C10 ， 返回C5 ， 再沿 C4 11 圈CH 飞完未经 6.5 过的城市,最后回到 C1， 这样总票价 w = 91.5 (百元)， 比原来省钱多了。
机动 上页 下页 返回 结束
沿下面的图4飞，总票价 w = 89.5 (百元)，更省。
返回
结束
众所周知，当一个图的顶点个数和边数都较多时， 要判定它是否哈密顿图是困难的。也就是说，找它的 最大子哈密顿圈是困难的。 但是我们即使没有找到它 的最大子哈密顿圈， 只要找到它的极大子哈密顿圈， 也能求出该问题的一个较优解。假设我们只找到本题 图G的一个极大子哈密顿圈如图6中实线。
图6 C2
机动 上页 下页 返回 结束
1 最优生成树法 （1）用 Kruskal 算法求连通赋权图G的一棵最小生 成树T。 （2） 往返T的每一边各一次，得G的近似最小H环 游CH ， CH的权重就是该问题的近似最优解。 它的数学模型是： w ( CH ) = 2 w ( T ) 本问题的一棵最优生成树如图2的树T 。

高一奥数旅行商问题(一)
高一奥数旅行商问题
问题介绍
•旅行商问题是指一个旅行商需要在多个城市之间旅行，每个城市之间的距离和旅行花费都不同，旅行商需要找到一条最短路径，将所有城市都访问一遍，并最终回到出发城市。

相关问题
1.问题一：如何表示城市之间的距离？
2.问题二：如何确定旅行商的出发城市和目的地？
3.问题三：如何计算最短路径？
4.问题四：是否存在多种最短路径？
5.问题五：如何考虑旅行的时间和花费限制？
解决方法
1.问题一的解决方法：
–使用邻接矩阵表示城市之间的距离，矩阵中的每个元素表示从一个城市到另一个城市的距离。

2.问题二的解决方法：
–可以随机选择一个城市作为出发城市，然后使用算法计算最短路径后，再将该城市作为目的地。

3.问题三的解决方法：
–使用图论中的最短路径算法，如Dijkstra算法或Floyd-Warshall算法，可以计算出最短路径和对应的总距离。

4.问题四的解决方法：
–如果存在多种最短路径，则可以选择其中任意一条路径作为解决方案，或者通过增加限制条件来确定唯一的最短路
径。

5.问题五的解决方法：
–在计算最短路径时，可以考虑各个城市之间的旅行时间和花费，并通过设置约束条件来限制旅行商在规定的时间和
花费范围内完成旅行。

总结
高一奥数旅行商问题是一个经典的数学问题，需要使用图论和算法知识来求解。

通过逐步解决相关问题，可以找到最优的旅行路径，并考虑旅行的时间和花费限制。

这个问题可以帮助学生培养数学建模和解决实际问题的能力。

设城市数量为n，则有
( n 1)! 2
条不同路径。
算法的复杂程序呈指数增加。城市数量越多，所需的计算时 间成本越大，当城市数量无穷多时，则不可能被计算出来。 例：当n=20,路径数有1.2×1018 ，即使每秒列举1亿条路径， 需350年才能全部列出。
二、近似算法
• 1、路径构建法： 从距离矩阵中产生一个近似最佳解的途径，有以下几种解法： （1）最近邻点法：一开始以寻找离场站最近的需求点为起始路线 的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到 最后。 （2）节省法：以服务每一个节点为起始解，根据三角不等式两边 之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站， 而后计算路线间合并节省量，将节省量以降序排序而依次合并路线， 直到最后。 （3）插入法：如最近插入法、最省插入法、随意插入法、最远插 入法、最大角度插入法等。 • 2、路径优化法：先产生一条初始巡回路径，再改变其中某些车市的 顺序，使路径优化，逐渐接近最优解。 • 3、智能算法
3、智能算法
• 至今没有找到多项式时间算法解（无法用一个确定的公式 来求解）的一类问题，但问题的所有可能答案，都是可以 在多项式时间内计算得出并进行正确与否的验算。
应用
1、印刷电路版的走刀问题 2、车间调度、电网配线 3、交通运输：航线安排、物流配送
求解算法：
一、精确算法—穷举法 • 旅行商问题实际上是一个排列组合问题。穷举法：将所有 的可能路线全部求出，通过比较找到全局最优解，但计算 量在顶点数稍微多一点情况下，这时由于可行解太多，而 使算法不可行。
旅行商问题是一个典型的组合优化问题，也是一个典型的 NPC问题。 该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合 爆炸。 以42个地点为例：

实验二旅行商问题计算机科学系谢志玺03120104一：问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。

他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。

二：问题分析设顶点集V,S为V的子集。

顶点i通过顶点集S（i∈V-S）的点到达顶点0的最短路径长度为min(i,S),则有递归式：min(i,S)=min{di,j+min(j,S-{j})}(j∈S,di,j为顶点i到顶点j的距离)从而问题的解为min(0,V-{0})(即顶点0通过集合V-{0}的点到达顶点0的最短回路长度)由于求解的时候需要用到子问题min(j,S-{j}),所以可以用动态规划求解.从S=Ø开始，依次对|S|=1,2,┅,n-1计算三：算法描述1：数据结构描述1) 考虑到要做图形演示，需要记录min(i,s)顶点i是通过集合s中哪个顶点得到的.故用nextpoint＝j表示i是通过集合s中的点j得到min(i,s).2) 同时需要记录集合s中有哪些顶点,所有用choose数记录这些顶点.choose[k]=’1’表示顶点k∈s.choose[k]=’0’表示顶点k不属于s.(为了便于比较，这里choose数组用char类型).用min表示min(i,s);3)如果集合s有m个元素(|s|=m),则s有中选择.故用指针next指向下一个|s|=k的集合s.综上所述，有结构类型：struct vertex{char choose[MAX]; //MAX定义为最大的顶点数int min;int nextpoint;struct vertex *next;}分配一个二维指针数组struct vertex *g[MAX][MAX].g[i][j]记录着顶点i通过大小为|s|=j的集合s到达顶点0的信息.另外一个结构:struct point{double x,y;};用于记录各顶点的坐标，以便进行图形演示.2:具体算法1) choose_s(int size,int k,char s[MAX],int n,struct vertex *g[MAX][MAX],intconst_size)该算法进行选择所有大小为|S|=const_size 的集合S.s 数组记录了这些被选中的顶点.然后调用函数i_s_v0_g() 对任意顶点i ∈v-s 计算min(i,S).2) i_s_v0_g(int i,char s[MAX],struct vertex *g[MAX][MAX],int n,intconst_size)该算法用struct vertex* temp 记录min=min(i,S)=min {di,j+min(j,S-{j})}，nextpoint 和choose[]<=s[].然后将temp 加入到g[i][const_size]链中.算法利用到函数int getmin()返回min(j,s-{j})3) int getmin(int j,int n,char s[MAX],struct vertex *g[MAX][MAX],intconst_size)该算法通过查找g[j][const_size]链中的节点temp_recrd->choose[]==s[],然后返回temp->min(即返回min(j,s-{j}))3：图形算法1) 算法 findconnectpoint 通过struct vertex *g[][]中记录的信息求最短路径包含的边.其中connect[i]=k 和connect[i+1]=m 表示最短回路经过边e(k,m).2) 算法 x_y_vi （）计算顶点i 的坐标，存于 p[i]中.其中数组p 是一个struct point 类型的结构.3) 算法printgraph （）利用数组p 和数组connect 打印最短旅行商回路.四：实验结果分析1）TSP4.txt 最短回路：25TSP6.txt 最短回路：175TSP8.txt 最短回路：242TSP10.txt 最短回路：279TSP15.txt 最短回路：3712）时间复杂度分析.|S|=k 的子问题个数为 在|S|=k 时，求最小值需做k-1次比较算法的时间复杂度为k n C 2-)2()1(2212n n k k n n C k Θ=-∑-=-。

a35 a15 a24 a14 a12 a13 a34 a23 a45 a25 3 4 4 9 10 10 11 13 16 20
D(8)= (a35,a15, a14,a12,a13 ) D8=36>d0不可能最短故剪枝，退出后4个元素 D(9)=(a35, a24 a14 a12 a13) D9=36>d0不可能最短故剪枝,退出后5个元素
边 a35 a15 a24 a14 a12 a13 a34 a23 a45 a25 权 3 4 4 9 10 10 11 13 16 20
2)先取 N条边 3)判断是否构成H回路，否则将试探路的最后 元素换成下一个待选元素，直到能构成H回路。 此时记下其路长d(i),并赋给d0. 4)退出上述H回路的最后2个元素，换成新的元 素，判断其路长d(I)是否小于d0. 若小于d0则回到第3步(有可能得到更短的Ｈ 回路)，否则再多退一个元素，重复第4步的判断 工作，若无元素可退则中止寻找工作，即换掉最 后三个元素
便宜算法
往往需要增加一些限制，以便能够 提高计算速度： (1)G是无向正权图。 (2)W(i,j)+W(j,k)>=W(i,k) 任何两边之和大于第三边 基本思路：从编号为1的点出发，寻 找与“已确定的回路”距离最近的点， 插入到回路中。近似最多为精确2倍
１ １ 0 ２ 18
35 25 ５ 27
a43 a21 a52 a42 a32 a54 a41 a51 a53 a31 17 18 19 21 23 24 25 27 28 35
D(11)=(a43 a21 a54 a41 a51 ) d11>d0不可能退栈 D(12)=(a43 a52 a42 a32 a54 ) d12<d0深探？退栈 D(13)=(a21 a52 a42 a32 a54) 仍不深探，栈空

p2 (2, 3, 4) 4 p2 (3, 2, 4) 4 p2 (4, 2,3) 2
当k=3时，即从v1城开始，中间经过三个城市(顺序随便)回 到v1城的最短距离是：
f3 (1, 2， 3， 4) min f 2 (2, 3, 4) d 21 , f 2 (3, 2, 4) d31 , f 2 (4, 2,3) d 41 min 20 8,18 5, 22 6 23
vj
1
0 5 6 3
2
3 0 4 7
3
6 2 0 5
4
7 3 2 0
作业
• 求解5个城市的旅行商问题。
1 1 2 3 4 0 12 23 34 2 10 0 9 32 3 20 18 0 4 4 30 30 5 0 5 40 25 10 8
5
45

11
10
0
例： 求解四个城市旅行推销员问题，其距离矩阵 如表所示。当推销员从v1城出发，经过每个城市一 次且仅一次，最后回到v1城，问按怎样的路线走， 使总的行程距离最短。
vi 1 2 3 4
vj
1 0 8 5 6
2 6 0 8 5
3 7 9 0 5
4 9 7 8 0
解: 由边界条件可知：
f0 (2, ) d12 6, f0 (3, ) d13 7, f0 (4, ) d14 9
动态规划模型
• 设S表示从V1到Vi中间所有可能经过的城市集合，S实际上是包 含除V1与Vi两个点之外其余点的集合，但S中的点的个数要随 阶段数改变。 • 状态变量（i，S）表示：从V1点出发，经过S集合中所有点一 次最后到达到Vi
• 最有指标函数fk(i, S)为从V1出发经由k个城镇的S到Vi的最短距 离