请输入您要查询的百科知识:

 

词条 货郎担问题
释义

货郎担问题也叫旅行商问题,即TSP问题(Traveling Salesman Problem),是数学领域中著名问题之一。

其一般提法为:有n个城市,用1,2,…,n表示,城i,j之间的距离为dij,有一个货郎从城1出发到其他城市一次且仅一次,最后回到城市1,怎样选择行走路线使总路程最短?

旅行商问题的提法为:假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

货郎担问题(TSP问题)是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。

动态规划解

阶段变量k:按所经过的城市个数划分阶段k,k=1,2,…,n-1.

状态变量Sk:设第k阶段到达城市i时途中所经过的k个城市集合为S

=====================================================================

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

货郎担问题的分析

货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线,而由始点出发的周游路线一共有(n一1)!条,即等于除始结点外的n一1个结点的排列数,因此货郎担问题是一个排列问题。排列问题比子集合的选择问题(例如0/1背包问题就是这类问题)通常要难于求解得多,这是因为n个物体有n1种排列,只有2n个子集合(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的那些值。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/1/31 1:31:29