一．货郎担问题

    货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。该问题的基本描述是：某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短?此问题可描述如下：设g=(v，e)是一个具有边成本c_ij的有向图，c_ij的定义如下，对于所有的i和j ,c_ij>0，若<i，j> e，则c_ij＝ 。令|v1|=n，并假定n>l。g的一条周游路线是包含v中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本和。货郎担问题(traveling sales person problem)是求取具有最小成本的周游路线问题。

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

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

    注意 只有机械手移动的时间总量是可变化的。

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

二．货郎担问题的分析

    货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有(n一1)!条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。排列问题比子集合的选择问题(例如0／1背包问题就是这类问题)通常要难于求解得多，这是因为n个物体有n1种排列，只有2ⁿ个子集合(n!>o(2n))。通过枚举(n一1)1条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为o(n1)。为了改善计算时间必须考虑新的设计策略来拟制更好的算法。动态规划就是待选择的设计策略之一。但货郎担问题是否能使用动态规划设计求解呢?下面就来讨论这个问题。

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

g(1，v一{1})是一条最优的周游路线长度。于是可以得出

    g(1，v一{1))＝ {clk十g(k，v一{1,k}))

将(4．19)式一般化可得

    g(i，s)— {cij+g(j，s—{j})}    (4．20)

如果对于k的所有选择，知道了g(k，v一<1，k))的值，由(4。19)式就可求解出g(1，v一{1})。而这些g值则可通过(20)式得到。显然，g(1，∮)=cil，l<i≤n。于是，可应用(20)式去获得元素个数为1的所有s的g(i,s)。然后，可对 =2的s得到g(i，s)等等。当 <n一1时，g(i，s)所需要的i和s的值是i≠1，1 s且i各s的那些值。

三．例子

    例17 考虑图4。13(a)，其边长由图4.13(b)中的矩阵c给出：

    g(2，∮)＝c_2l=5    g(3，∮)=c₃₁＝6    g(4，∮)=c₄₁＝8

由(4．20)式得

    g(2，{3})=c₂₃+g(3，∮)=15 g(2，{4})＝18

    g(4，{2}=13 g(4，{3})=15

接着，计算在 ＝2且i≠1，1 s，i s情况下的g(i，s)：

    g(2，{3，4})=min{c₂₃+g(3，{4})，c₂₄+g(4，{3})=25

g(3，{2，4})＝min{c₃₂2+g(2，{4})，c₃₄+g(4，{2})}＝25

g(4，{2，3})＝min{c₄₂2+g(2，{3})，c₄₂+g(3，{2})}＝23

 

                图13                               （演示）

最后，由(19)式得

    g(1，{2，3，4})＝min{c₁₂-g(2，{3，4})，c₁₃+g(3，{2，4})，c₁₄+g(4，{2，3})}＝min{35，40，43}=35

    图13(a)中的这个有向图的最优周游路线长度为35。如果对每个g(i，s)，保留使(20)

式右边取最小值的那个j值，那末就可构造出这一最优周游路线。令j(i，s)是这个值，则j(1，{2，3，4})=2。它表示这条周游路线由1开始并通到2。剩下的路径可由g(2，{3，4})得到。因j(2，{3，4})＝4，故这下一条边是(2，4)。以后的剩余段由g(4，{3})来获得j(4，{3})=3。因此这条最优周游路线是1，2，4，3，l。

设n是用(4．19)式计算g(1，v一{1})以前需要计算的g(i，s)的数目。 的取值在不同的决策阶段分别对应为0，1，…，n一2。对于 的每一种取值，i都有n一1种选择。不包含1和i在内的大小为k的不同s的个数 是因此，

n=

又因为在 ＝k时，由(20)求g(i，s)的值要进行k一1次比较，所以用(19)和(20)求最优周游路线的算法要求的计算时间为⊙(n²,2ⁿ)。由此可知，用动态规划设计的算法比枚举法求最优周游路线在所用的时间上有所改进，但这种方法的严重缺点是空间要求要有o(n u)，这太大了，因而实际上是不可取的。在以后的章节里，将对货郎担问题作进一步的讨论。