您好、欢迎来到现金彩票网!
当前位置:秒速时时彩计划 > 随机归约 >

旅行商问题的一个精确算法pdf

发布时间:2019-05-20 15:57 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  上 海 机 械 学 院 学 报 第l3卷 第1期 T SHANGHA~ INST MECH. ENG Vo1.I3No.I199t 旅行商问题 的一个精确算法 马 良 王龙德 (上海机械学 院) 摘 要 奉文对经典的旅行商问题给 出一种精确式算法,计算结果表明,它具有一定的 优越性 和 实用性 . . 关键词t旅行商问题I算法 旅行商问题 (TravellingSa]esmai1Problem,简记 TSP)或旅行售货员问题,有时也 称 作货郎担问题,是个古老的难题,至今 尚未完全解决,现 已被归^NP一完备 问题 类.由 于 它在许多领域中都有着广泛的应用,因而对其研究一直没有停止.为了解决实际问题,出现 了许多算法 (精确式或启发式的 ).本文将要给出的是一种在分支定界法基础上融合启发式 算法的精确式算法,能求得 TSP的精确解 ,计算结果表 明,它具有一定的优越性和实用性. 1 问题概述 经典的ISP是这样叙述的:有一商品推销员想去n个城市推销货物,从城市 1出发,经 其余各城市一次,然后回到城市 1,应如何选择行走路线,才能使总行程最短 (各城市间距 离为 已知 )? 从完全图的意义上来说,该问题实际上也是图论中的最小Ham]llon圈问题.本文 以 后 所讨论的TSP都是从完全图的角度来说明的.对于 TsP的算法,现 已有很多种.较早 出现 的精确算法有分支定界法、线性规划方法等等it],后来 ,由于计算复杂性理论的出现,人们 开始转而寻求近似的算法或启发式算法,目前已有的可分为几大类t】:a、插入法 (I~sertion Algorilhm)Jb.局部改进法 (2-OPT,3-OPT,et~、),c、混合法 (CompositeAlgothhm)) d.其他方法.但是,由于启发式方法是一种在很大程度上依赖于经验或直觉的方法,缺乏严 密的逻辑证明,因此尽管它深受实际工作者的欢迎,在理论界仍未受到足够的重视 .本文的 工作正是试图建立一种既能在理论上保证最优,又能为实际使用者所接受的求解 TSP的精确 算法. 收{骞日期:19gO-Og—OB 104 上 海 机 械 学 院 学 报 19o1~-第13卷 记G (v, )为一个赋权完垒 图 (可 以是非对称的 ),= (1,2,…, )为顶点集 , F为边集.各顶点之间的距离 d.f已知. 设 : { 令 , { : tn在最优路线上 于是 XSP的数学模型可写成如下形式 : j“ ’ ,,,菁 ’ …’ i善 , ,,…,” 1.善 ’v L Fo.11 其中,ISI为 S中所含图G的点数. 在上述约束中,如 ,善 -≤ I一去掉,则问题就化为一个典型的分派问题,该分派 问题的解构成了TSP最优解的一个下界.传统的分支定界法的思路正是 由此而引出的. 2 算法思想 我们所提出的算法主要思想来 自分支定界法 【,包括两部分t首先是求 出一个启发式解 作为初始解 ,记其总长为 d}然后接人分支定界法,以d为上界进行分支搜索,最后得到最 优解 .这里,初始解 的获得实际上就是将原来分支定界法中的递归过程去掉,即在得到分支 边之后,不进行分支搜索,而直接将该分支边接人最优路线次循环后就可 得到初始解.这种 以初始解 d作为上界进行搜索的思想能够在绝大多数场台下大大降低分支 定界法的运行时间,使得算法的承解时问易于被接受. 记距离矩阵D:[d]…,则算法包括以下几个子块t a.矩阵归约 (MatrixReduction) function reduce(D )I begin begin rowred()一 行 的最小元素} rvalue—O, (·归约值 ·) ifrowred () 0 lhen for 一1tosizedo {·size为矩 begin 阵阶数 ·) 第1期 马 良等;旅行商问题的一个精确算法 105 从 i行 的每个有 限元素中 . 初始解搜索 减 去 rowred (i), rvalue~rvalue+r0wred ()I proceduresearch一1(edges,cost,D); end; begin end; cost~ cost+reduce (D )I for ·1to izedo ifedges= 一2 then begin begin coired()一 列 的最小元素, 加入最后两条边 ,得到初始解,其总 长记为 d, ifcolred ()O lhen end begin els0 从 0的每个有限元素中 减去 colred()} begin rvalue~rvalue+co!red (,)· 调用 procedurebeA 以确定 (r,c); end} 将边 (,c)记入当前解 中I end, newD—D一列 c一行 (·划去矩 阵r行和 列 ·) reducc~ rval0I search一1(edges+1,cost,newD); end endl b 选择分支边 end procedurebest d.分支定界搜索 bcgJn procedure search一2 (edges,cost,D ), itrosl 一 ∞ J for 一1iosized0 {·行 ·} begin for 一1tosized0 (·列 ·) cobt·一c0st+reduce (D )J ifd.f=0 then ifCOSt≥ d then begin begin min 一}行除 d.j之外 的最小元} 初始解d即为最优解 , toP} mjnc— 列除 d;_之外的最小元} endl total~ mln +m nc1 ifcost tweightthen if totalmo~tthen ifedges= 一2 then begin begin most~ total} 加^最后两条边} — ; {·分支边的行数 ·) tweight~cost; c一 I『 {·分支边的列数 ·) 记下当前新的解} endl end end} else end 106 上海机械学 院学报 l§91年第l3害 begin 减 于是,整个算法可叙述成 解 去 调用 /~rocedurebest以确定 (, ), begin 按最优解包含边 (r,c)和不包含 若干参数赋初值, 得 (r,c)来进行分支搜索且每次搜索均 矩 n search一1求初始解, 按下界值twei~hl的分支进行, tearch一2求最优解, 降 end; erd D = end 1 2 3 4 籼分侄1{日H+●}¨。0。。∞。}。,;;0。∞。。∞ ● ● ● ● ● , 由于上述算法中的过程 sealch一2是一个递归调用过程,因此,该算法仍然是一种属于分 l ∞ 2 4 6 支定界法范畴的递归型算法.但是,初始解的上界限制,将大大降低递归调用的步数,这在 我们的实际计算中已经被充分认识到. 2 l ∞ 3 7 下面,我们用一个简单的倒子说明一下算法的大致运算过程 . . 3 4 8 ∞ 1 例 巳知 4 3 9 5 ∞ 化 元 为 厂 _ , 求 出 从 I 出 发 回 到 的 T S 解 (b)选择分支边 得 i=4,i=3,将边 (4,3)记入当前解,并从矩阵中划去第 4行 和第 3列 ,得 l 2 4 1f 。。0 0 ] 2 l10 ∞ 5 l1 3Ll l0 0 j (a)reduce=OJ 第 1期 马 良等:旅行商问题的一个精确算法 (b)选择分支边.得 (2,1).划去第 2行和第 1列,得 4 0 ] l 0 J 由于 (4,3)、(2,1)巳在当前解 中,故可得T=(1,4,3,2,1}为初始解,总长为9. 以9为上界,运行分支定界法,类似前面所述,可得分支边为 (4,3):n.最优解 包含边 (4, 3),这时下界值大于等于9}b.最优解不包含 (4,3),将 出。换为。。,然后作归约,则 下界值大于等于 9+8:17.由于n b 的下界值大于等于 9,故初始解即为最优解. 3 计算分析 本文的算法用 TurboPascal编制,在 IBM—PC/XT微机上运行.借助 TurboPascal的随 机数发生器生成随机数以构成随机例子,我们计算了 =10,15,20,25,30,35,40的情形, 有关结果见表 1. 表 1 本文算法与分支定界法计算耗 时 (S)比较 (算倒个数 =10) 注:表中的 “一”为经过 l5rain尚无计算结果 . 从表 1中可看出,本文算法与经典的分支定界法相比在统计意义上具有明显的优势.事实 上,本文算法的效率主要依赖于初始解的好坏,如果初始解较差的话,则整个算法的时间仍 有可能变得非常可观.不过从我们的大量计算表明, “坏”的情况其概率极小,这里的初始 解一般都相当理想,非常接近最优解 . 为了有一个更清晰的认识,我们将求初始解的算法与TSP启发式算法中一个较成功的算 法——最远插入法 】作 比较,即将求得的解所对应的 目标函数值与最远插入法求得的解所对 应的目标函数值相比(注意,目标函数是求出最小值 ),有关结果见表2, 108 上 海 机 械 学 院 学 报 1991年 第13卷 表 2 本文算法与最远插 八法计算结果的比值 (算例个数 =10) 由表 2中可看出,随着 值的增大,最远插入法将越来越不如本文I目所采用的启发式算 法.正是这种启发式算法的引入,才使得分支定界法在很多场合下变得非常有效,问鼯规模 越大,越能体现出本文算法的优越性. 4 结束语 TSP有着悠久的历史和广泛的应用背景,多少年来无数优秀的数学家在这方面耗费了他 们毕生的精力,为我们留下了一大批卓越的成果.尽管现已证明TSP是个NP一完备问题,是 否存在多项式阶数算法 (或有效算法)尚不可知 ,但我们相信 ,随着人们的不断努力,终究会 出现一些既有理论依据又具有实用价值的较好算法. 参 考 文 献 1 Be1]moreM .eS4Z..Thetreve]lingsalesman problemlA survey.Operations 丑esearCh, 1968, 16l 538~ 558 2 Golden B. eta1..Approximate travelfing salesman algorithms.Operatino sRe- search. 1980, 28l 694~ 711 3 SysloM .M.et ..DiscreteOptimizatlonAlgorithms.EnglewoodCliffs,N., Prentice—Hal1.1983 第 1期 马 良等:旅行商问题的一个精确算法 、l AN EXACT ALGORITHM FoR THE TRAV量LLING SALESM AN PRoBLEM M a Liang W ang Longde Abstract ThisFal;er offersailexactalgorilhm fortheclassictravetfing salesman problem The . computationalr(suitsshow 1hatithasSOllleobviousadvanlagcsand traclicalapp]ica— tions. Keywords:I PIAlgorithm

http://parroche-dorioz.com/suijiguiyue/43.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有