货郎担问题小论文

　货郎担问题

　一．货郎担问题的基本内容 货郎担问题 TSP (Traveling Salesman Problem)，又称旅行推销员或旅行商问题．是指对于给定的个城市，旅行商从某一城市出发不重复地访问其余每一城市后回到出发的城市，要求找出一条旅行路线，使总的旅行路程最短。用图论来描述，就是给定一个正权完全图，求其总长最短的哈密顿回路。货郎担问题（TSP 问题）是一个组合优化问题。该问题可以被证明具有 NPC 计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。由于问题本身的组合特性，其求解计算量随着城市的个数 n 增加而呈指数关系增长。

　货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。求解问题的典型方法有穷举搜索法、动态规划法、启发式算法等。穷举搜索法虽然能保证得到全局最优解，但面临着计算量组合爆炸的困难，对较大规模的问题无法在可能的时间内完成。动态规划法比穷举法的计算量显著降低，但当 n>20 时其计算量和存贮量之大，仍然几乎无法实现。目前，较为有效的方法主要是利用城市位置、距离、角度等信息构造的各种启发式算法。近年来一些学者还尝试用各种新的优化方法解决旅行商问题，如神经网络方法、遗传算法，模糊算法等，并取得了一些进展。

　货郎担问题是运筹学中一个古老而著名的问题，它是指一个货郎旅游的最短回路问题。货郎从一个城市出发，经过其它所有城市，并且一个城市只能经过一次，再回到出发点，求货郎旅游的最短回路。这个问题可具体描述为：给定城市集合Ｃ＝｛ｃ１，ｃ２，……，ｃｎ｝和任意两个城市ｃｉ，ｃｊ（１≤ｉ≤ｊ≤ｎ）间的距离ｄ（ｃｉ，ｃｊ），要求计算通过每个城市一次且仅一次的旅游回路，使该回路长度最短。找出货郎问题最优解的算法可以通过完全枚举，即通过完全枚举城市集合Ｃ的全排列，计算出每种排列相应旅游回路的长度，从中找出最短的旅游回路。这种完全枚举算法的时间复杂性函数是城市数目ｎ的指数形式，当ｎ值很大时是我们所不能接受的。

　二．货郎担问题的举例 有很多实际问题可归结为货郎担问题。例如邮路问题就是一个货郎担问题。假定有一辆邮车要到 n 个不同的地点收集邮件，这种情况可以用 n 十 1 个结点的图来表示。一个结点表示此邮车出发并要返回的那个邮局，其余的 n 个结点表示要收集邮件的 n 个地点。由地点 i 到地点 j 的距离则由边；上所赋予的成本来表示。邮车所行经的路线是一条周游路线，希望求出具有最小长度的周游路线。

　例如在一条装配线上用一个机械手去紧固待装配部件上的螺帽问题。机械手由其初始位置（该位置在第一个要紧固的螺帽的上方）开始，依次移动到其余的每一个螺帽，最后返回到初始位置。机械手移动的路线就是以螺帽为结点的一个图中的一条周游路线。一条最小成本周游路线将使这机械手完成其工作所用的时间取最小值（注意只有机械手移动的时间总量是可变化的）。

　例如产品的生产安排问题。假设要在同一组机器上制造 n 种不同的产品，生产是周期性进行的，即在每一个生产周期这 n 种产品都要被制造。要生产这些产品有两种开销，一种是制造第 i 种产品时所耗费的资金（1≤i≤n），称为生产成本，另一种是这些机器由制造第 i 种产品变到制造第 j 种产品时所耗费的开支 cij 称为转换成本。显然，生产成本与生产顺序无关。于是，我们希望找到一种制造这些产品的顺序，使得制造这 n 种产品的转换成本和为最小。由于生产是周期进行的，因此在开始下一周期生产时也要开支转换成本，它等于由最后一种产品变到制造第一种产品的转换成本。于是，可以把这个问题看成是一个具有 n 个结点，边成本为 cij 图的货郎担问题。

　三．货郎担问题的分析 货郎担问题要从图 g 的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n 一 1）！条，即等于除始结点外的 n 一 1 个结点的排列数，因此货郎担问题是一个排列问题。排列问题比子集合的选择问题（例如 0/1 背包问题就是这类问题）通常要难于求解得多，这是因为 n 个物体有 n1种排列，只有 2n 个子集合（n!>o（2n））。通过枚举（n 一 1）！条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为 o(n！）。为了改善计算时间必须考虑新的设计策略来拟制更好的算法。

　动态规划就是待选择的设计策略之一。但货郎担问题是否能使用动态规划设计求解呢?下面就来讨论这个问题。

　不失一般性，假设周游路线是开始于结点 1 并终止于结点 l 的了条简单路径。每一条周游路线都由一条边（1，k）和一条由结点 k 到结点 1 的路径所组成，其中 k∈v 一（1）；而这条由结点 k 到结点 1 的路径通过 v 一{1，k}的每个结点各一次。容易看出，如果这条周游路线是最优的，那么这条由 k 到 1 的路径必定是通过 v-{1,k}中所有结点的由 k 到 1 的最短路径，因此最优性原理成立。

　货郎担问题的计算量是相当大的。对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。

　四．参考文献：

　在百度文库和搜狗百科上还有一些相关文章的查阅。