（管理科学与工程专业论文）基于linkernighan改进型算法的可视化tsp处理软件的实现.pdf

摘要 t s p ( t r a v e l i n gs a l e s m a np r o b l e m ，旅行商问题) 是组合优化领域的重要问题 之一，同时也是众多现实问题的原形，对其开展深入广泛的研究具有重要的理论价 值和实用价值。本文在借鉴国外前沿启发式算法思想的基础上，基于l i n - k e m i g h a n 改进型算法引擎，开发了能够高效解决t s p 的可视化处理软件。在如下几方面做了 深入研究： 首次将t s p 处理软件的开发作为一个研究课题。说明对t s p 问题的研究，应 该将算法设计与软件构建并列考虑，并特别重视对完整软件的开发，以促进优秀算 法的广泛传播和改善发展。 本文对可视化t s p 处理软件的概念界定是一个研究亮点。基于概念界定设计 了合理的软件功能架构，使t s p 问题生成的可视化、t s p 数据显示的可视化、t s p 求解性能的可视化集一大成。 在引进了经典的l i n - k e m i g h a n 算法基础上，对该算法作了较大改进。特别深 入的探讨了候选边集的生成方法，即运用最小1 树和升级( a s c e m ) 操作确定d 接 近度，由此对边的优先性排序。相比于传统的近邻法，a - 接近度法确定最优边的性 能大大改善。 本文特别重视阐述算法实现细节与其性能间的深刻联系，用两章的篇幅分别介 绍了算法引擎的c 语言开发和可视化平台的v c 开发。其中在算法引擎章，围绕引 擎的总体流程，对重要启发式算子的程序实现作了深入说明，并穿插了边成本的快 速诗算、存储和查找策略；初始解的生成策略；数据结构的选择策略等。在可视化 章。围绕软件模块架构，依次介绍了数据处理模块的开发、可视化模块的开发和扩 展模块与算法引擎的整合，并穿插了大量的数据结构介绍和容器选取应用策略。这 两章内容是难得的开发模块化的高效t s p 程序软件的指南。 基于本文开发的可视化t s p 处理软件性能优良。首先，它广泛支持t s p l i b 的t s p 、a t s p 、h c p 类问题，对t s p l i b 中大部分问题都在较短时间内求出了最优 解，包括7 3 9 7 点的t s p 问题。其次，它的扩展模块支持t s p 问题快速生成、地图 模式和坐标模式的人机交互操作。文中解决的案例和各类图示都说明该软件对广大 研究、应用人员有重要的研究应用价值。 顼士研究生：于龙振( 管理科学与工程) 指导教师：戴更新副教授 关键词；t s p ；l i n - k e r n i g h a n 算法；改进：软件：可视化；t s p l i b i m p l e m e n t a t i o no f t h ev i s u a lp r o c e s ss o f t w a r ef o r s o l v i n gt s p b a s e do nm o d i f i e dl i n k e r n i g b a na l g o r i t h m a b s t r a c t t s pi sa t y p i c a lp r o b l e mo fi t sg e n r e ：c o m b i n a t o f i a lo p t i m i z a t i o n f u r t h e r t t l o r e t s p i st h eo r i g i n a lf o r mo f m a n yr e a l i s t i cp r o b l e m s s o ，t h a t t a k i n gat h o r o u g ha n db r o a ds t u d y o nt s ph a si m p o r t a n tt h e o r yv a l u ea n dp r a c t i c a lv a l u e t h i sp a p e rd e s c r i b e sa l le f e e c t i v e v i s u a lp r o c e s ss o f t w a r ef o rs o l v i n gt s pw h i c h sc o n s t r u c t i o ni 8b a s e d0 1 3t h em o d i f i e d l i n k e r n i g h a na l g o r i t h me n g i n e s u b j e c t sa sf o l l o w sa r em a d eat h 0 1 0 1 t g t ls t u d y f o rt h ef i r s tt i m e ，t h ed e v e l o p m e n to ft h et s pp r o c e s ss o f t w a r ei sc o n s i d e r e da sa c e n t e rr e s e a r c hp r o b l e m i nf a c t a l g o r i t h m sd e s i g na n ds o f t w a r e sc o n s t r u c t i o na r et h e t w od o m i n a t i n gf a c e t st h a td e t e r m i n et h ef i n a ls u c c e s s t h e r e f o r e ，i t sn e c e s s a r yt og i v e e m p h a s i so nt h eb o t hs i d e s t h ed e f i n i t i o no ft h ev i s u a lp r e c e s ss o f t w a r ef o rs o l v 协gt s p ( v p s - t s p li sa r e s e a r c hi n n o v a t i o n a c c o r d i n gt ot h ed e f i n i t i o n ， v i s u a l ”e o n s i s i so fv i s u a l i z eo ft h e s t a n d a r dp r o b l e mc r e a t e ，v i s u a l i z eo ft h ed a t ad i s p l a y , a n dv i s u a l i z eo ft h er e s u l ta n dt h e p e r f o r m a n c e a tt 1 1 ef a s tc h a p t e r , c l a s s i cl i n - k e r n i g h a na l g o r i t h mj si n t r o d u c e d o nw h i c ha c o m p r e h e n s i v em o d i f i c a t i o ni sm a d et h e n a ni m p o r t a n tm e a s u r e 一旺- n e a l t l e s si su s e dt o p r o d u c et h ec a n d i d a t es e t ，c o m p a r e dw i t ht h en e a r e s tn e i g h b o rr n e a g u l 七, g - h e a r t l e s s b r i n g so u tm u c hb e t t e rp e r f o r m a n c e r e l a t i o n s h i pb e t w e e n t h ep r o g r a m sd e t a i la n da l g o r i t h m sp e r f o r m a n c ei st h o u g h t m u c ho f i tt a k e st w os e p a r a t ec h a p t e r st oi n t r o d u c et h ed e s i g no f a l g o r i t h m se n g i n e ( b y cl a n g u a g e ) a n dt h ec o n s t r u c to ft h ev p s - t s p ( b yv i s u a ic + + ) a tt h es e c o n dc h a p t e r , a c c o r d i n gt ot h ee n g i n e sg e n e r a lp r o c e d u r e i m p o r t a n th e u r i s t i co p e r a t o r sa r ep r e s e n t e d a st h ef o r mo fp s e u d oc o d ei nt u r n a n d t h es t r a t e g i e sf o rs i m p l i f yt h ec o s t sc a l c u l a t e s t o r ea n dl o o k u p ：p r o d u c i n gi n i t i a l t o u r ；s e l e c t i n gs u i t a b l ed a t as r f u c t - t l r e , n c ，a r e p r e s e n t e d a tt h et h i r dc h a p t e r , a c c o r d i n gt ov p s - t s p sm o d u l a r i z a t i o r t , d e v e i o p m e n to f t h ed a t ap r o c e s s i n gm o d u l e v i s u a l i z em o d t t l ea n di n t e r g r a t i o no f t h ee x t e n d e dm o d u l e a n dt h ea l g o r i t h me n g i n e e ra r ep r e s e n t e di nd e t a i l s i naw o r c lt h ep a p e ri saf u l lg u i d e f o rd e v e l o p i n gh i g hq u a l i t yt s ps o f t w a r e t h et e s to fv p s - t s pi si m p r e s s i v e a t 盘s t i tc a l ls u p p o r tm a n yk i n do ft s p ( i n c l u d et s ea t s pa n dh c p ) a n dc a uf i n dt h eb e s tt o u ro ft s p l i b sm a j o r i t yp r o b l e m s i nl i t t l et i m e ( t h el a r g e s tp r o b l e mh a sad i m e n s i o no f 7 3 9 7p o i n t s ) s e c o n d l y , i t se x t e n d e d m o d u l es u p p o r t sq u i c k l yc r e a t i n gt s pp r o b l e m ，i t sm 印a n dc o o r d i n a t em o d u l ee n a b i e i n t e r a c t i n go p e r a t i o nb e t w e e nt h eu s e ra n dt h es o f t w a r e p o s t g r a d u a t es t u d e n t ：l o n g z h e ny u ( m a n a g e m e n ts c i e n c e e n g i n e e r i n g ) d i r e c t e db ya s s o c i a t ep r o t g e n g x i nd a i k e y w o r d s ：t s p ：l i n - k e r n i g h a na l g o r i t h m ；m o d i f y ；s o f t w a r e ；v i s u a l ；t s p l i b 引言 引言 1 t s p 问题研究意义 t s p 问题( 旅行商问题) 的重要性当然不仅仅是因为旅行商迫切希望减少旅行 ( t o u r ) 成本。该问题具有众多方面的应用价值，而其中有些应用在表面看起来与旅 行路径并没有直接关系。 例如，考虑一个加工计划问题：有一批任务要通过一台机器加工而该机器在 同一时间只能加工一个任务，并且在一项任务即将被加工前，机器还要有个准备阶 段( 比如清洁、调试等) 。已知每项任务的加工时间和任意两项任务之间的交接时间， 要安排一个所有任务的完工次序，以使全部任务完工所用总时间最短。 以上问题其实是t s p 的一个现实问题的变形。可以用c 日表示从完成任务i 到 完成紧随其后的任务i 所需的时间，它等于任务i 与任务j 的交接时间加上任务j 的 完工时间。另外再假设一个任务( 完成时间为0 ) 代表整个n t 过程的开始和结束。 这样该问题就可转化成一个t s p 而予以解决。 许多现实问题都可以被看作是t s p 问题的变形。例如：网络配线、安排运输 路线、结晶学、机器人控制、电路板钻孔、项目时间排序等等。 t s p 问题是组合优化领域的典型问题，这意味着对t s p 问题开展深入的理论 研究会使组合优化领域其他问题的深入研究同样受益。事实上，组合优化领域的许 多研究进展都源于对t s p 问题的研究进展。例如该领域著名的计算方法“分支定界 法”首先是被用于解决t s p 问题 1 ：1o 另外值得注明的是：对t s p 问题的研究是上 世纪7 0 年代起兴起的“计算复杂性理论”研究进展的重要推动力之一口 。 然而，t s p 问题的魅力还不止于实践和理论上的重要性，解决这个问题的智力 挑战同样不容忽视。尽管t s p 问题易于描述，但是它确实难于求解。可以从一个相 对简单的t s p 问题的可能旅行数量上窥见一斑即便是极小规模的t s p 问题，它 的可能旅行数量也是天文数字。对于一个包含n 个点的对称t s p 问题，它有( n - 1 ) ! 2 条可能旅行。假设n 等于2 0 ，那么可能旅行的数量超过1 0 e + 1 8 条。再如t s p l i b ( 世界著名的t s p 问题集) 中的7 3 9 7 点t s p 问题，它有1 0 e + 2 5 0 0 0 条可能旅行。 相比而言，整个宇宙的基本粒子总数估计也不过1 0 e + 8 7 个。而t s p l i b 中规模最大 的t s p 问题为8 5 9 0 0 个点，这是典型的n p 完全难题。 青岛大学硕士学位论文 图1 p l a 8 5 9 0 0 ( 来源：t s p l i b9 5 。8 5 9 0 0 个点的t s p 问题) 2 t s p 算法的研究现状 t s p 问题己被证明是n p 难题之一，该类难题的时间复杂度接近指数变化。 值得庆幸的是，同属于n p 难题的各子类问题间具有相关性，即：如果找到了对其 中一个子类问题求解的较好方法( 时间复杂度呈多项式变化) ，那么该方法经过适 当改进也可以用于求解其他子类问题。不幸的是，已有研究都证实对于n p 难题， 时间复杂度呈多项式分布的算法不存在。因此在目前，构造以多项式变化的时间复 杂度解出t s p 的算法的尝试必然( 即便是将来也极有可能) 失败。换句话说，目前 为止的任何一种解决t s p 的算法，其执行时间至少要随着问题维数的单位增长呈指 数增长( 注意：上述时间复杂度是指在最坏情况下的时间复杂度) 。当然，并不能 完全否定时间复杂度呈多项式分布的算法的存在性，这还有待深入研究。 目前求解t s p 的算法主要可分为两类： ( 1 ) 精确算法 精确算法是指在有限步骤内找到问题最优解的算法。目前的研究表明1 0 0 个 点内的对称t s p 问题都可以用精确算法找到最优解( 某些文献也宣称用精确算法找 到了数百点规模的t s p 问题的最优解) 。 有记载的最有效的精确算法要数切面算法( 或称作割平面算法、搜索平面算 法) 卜6 。这类算法非常复杂，其程序代码的实现需要将近1 0 0 0 0 行。另外，该类 引言 算法的性能很大程度上依赖于计算机硬件性能。例如，在一台大型计算机上求解 2 3 9 2 点的对称t s p 问题需时2 7 个小时口 ( 1 9 9 1 ) 。而在一个大型计算机网络上求 解摘要中提到的7 3 9 7 点的t s p 问题需时3 4 年【6 】( 1 9 9 5 ) 。 ( 2 ) 近似算法( 或称“启发式算法”) 与精确算法不同，近似算法的目标是获得满意解而非最优解。相对于精确算 法，这类算法一般都实现简单，运行时间也短得多。许多优良的近似算法得到的满 意解的平均质量与最优解仅相差千分之几。因此，如果这个足够小的偏差可以被接 受，那么使用近似算法比精确算法要合适得多。 近似算法可以被进一步划分为如下三类：旅行构造算法( t o u rc o n s t r u c t l o n a l g o r k h m s ) 、旅行改善算法( t o u ri m p r o v e m e n ta 崦o r k h m s ) 和组合算法( c o m p o s “e a l g o r i t h m s ) 。 旅行构造算法的每一步插入一个点，n 步将n 个点全部插入( 假设t s p 问题 的维度是n ) ，即得到一条完整旅行。该类算法的最简单例子是“近邻算法”口1 ：随 机选取一点始发，从未被访问的所有点的集合中挑选距离当前点最近的点作为要走 的下一点：反复这一过程，在所有点都被访问有且仅有一遍后，回到始发点，既获 得了一条旅行。许多构造算法都基于该算法改进得来的。( 如【8 l o 】中例子) 旅行改善算法基于现有的一条完整旅行，通过各种边交换和点交换的方法， 而获得最终满意旅行。相比于前一种算法，该算法更加有效。该类算法的一种最简 单形式是2 一o p t 算法：给出一条初始旅行，搜索到旅行中的两条边，如果改变这两 条边对应四个端点的连接关系可以使总旅行变短，则用新的两条边取代原来的两条 边。搜索过程持续下去，直到无法使总旅行再变短为止。 著名的l i n k e r n i g h a n “ 算法源于2 - o p t 算法的思想，国外众多学者围绕该算 法进行了做有成效的研究1 1 2 旧，国内的魏平等学者也将2 - o p t 算法与遗传算法结 合，构造了性能优良的新算法。 组合算法是将上述两种算法混合运用的启发式算法，不再赘述。 图2 2 - o p t 移动示范图 在研究进展方面，普遍的国外学者要比国内学者研究得更深入。例如， a d r a b i n s k y ”、p e r t t u n e n 【1 8 1 、c l a r k e 19 1 、r e m e k 9 1 专门就t s p 启发式算法初始解的获 得方法和编程实现作了研究他们的研究建议不要用随机生成的方法获得初始解， 青岛大学硕士学位论文 而是最好根据原算法程序架构的特征，将专门生成初始解的启发式算子与原算法结 合应用，这样做可有效提高原算法的鲁棒形。再例如，一些国外学者专注于研究t s p 问题集，p a p a d i m i t r i o u 和s t e i g l i t z t 2 0 l 开发了类t s p 问题，该类问题特别不适合使用 局部寻优的启发式方法求解( 比如使用传统的l i n - k e r n i g h a n 算法) ，p a p a d i m i t r i o u 和 s t e i g l i t z 给这一类问题赋予了一个有意思的名字“悖理问题”( p e r v e r s e ) 。在此问题 集中，每个问题都有n _ 8 + k 个点，其最短旅行成本都等于n 。同时，有多达2 “( k 1 ) ! 条接近最优旅行的旅行，但他们的旅行成本却可以任意大，要从他们中的任意一条 转化为最优旅行都要移动不少于3 - k 条的边。由此可见，这类问题非常不适合用局部 寻优的算法解决。以上这些学者的研究工作对推进t s p 算法的研究都起到了非常重 要的作用。 3t s p 相关软件的研究意义 ( 1 ) t s p 软件的研究意义 t s p 问题历来是各界的研究热点之一，但是就t s p 问题的软件开发，目前能找 到的研究成果却特别的少。通过g o o g l e 和百度搜索发现，所谓的“t s p ”软件一是指 t i m es e r i e sp r o g r a m ( 时间序列分析程序) 、二是指t u n n e ls e i s m i cp r e d i c t i o n ( 隧道地 震波超前预报) ，这和t r a v e l i n gs a l e s m a n p r o b l e m ( 旅行商问题) 风马牛不相及。事 实上，t s p 算法本身的研究与其对应软件的研究开发，对解决t s p 问题是同等关键的 两个方面；而要检验一个t s p 算法的优劣性，检验该算法的配套软件性能又是至关 重要的一环。因此开展对t s p 相关程序软件的研究非常必要。 一是优良的算法必须要有优良的软件架构来付诸实施。将算法比喻为大脑，那 么软件架构就是身躯聪明的大脑固然重要，但是如果没有健壮的身躯供以营养， 那大脑迟早会因为营养缺乏而丧失再发育。同样的道理，一个t s p 算法固然优良， 但是如果不能规划出相应的优良软件架构，那该算法的优越性必会大打折扣。t s p 算法与对应的软件架构是相辅相成的关系。 二是算法性能的优越性是相对的，而提高算法性能的途径不仅可通过改进算法 达到；也可以通过改进其软件实现来达到。对每一位编程者而言评价软件优劣的根 本依据都是其时空复杂度，为了获得最好的软件性能，编程工作需要严谨性和灵活 性的完美结合。差之毫厘、谬以千里，基于相同算法设计的不同软件实现，可能会 在解决相同的问题时出现显著的快慢之分。问题只能出在软件实现上，并不是说谁 的软件错误，而是因为有更巧妙的软件实现方法。再例如：基于c _ h 开发t s p 数据处 理引擎，开发人员当然可以自己编链表和堆栈，但可以基本确信的是：他自行开发 的链表堆栈肯定不及s t l 中的标准模板来的高效。 4 引言 三是从对算法性能评价的公正性而言，用相同的神经网络算法软件解决同一个 t s p 问题，在赛扬机上和在奔驰机上运行的性能不会一样：在w i n d o w s 系统和l i n u x 系统上运行的性能不会一样。那么该如何公正的评价算法性能呢? 一种较好的办法 是把该软件发到网上去( 例如幽婴q 避鱼磐：q 萨”是最大的开源软件站) ，让仁者 见仁、智者见智，可以确信大部分测试者能够认可的软件至少是较好的。这样做的 前提是必须把算法做成了一个具有友好的用户接口的软件。 四是从推进算法的改进发展而言。遗传算法之所以能够久经“进化”、风靡全 球，从开源社区w w w s o u r c e f o r g e o r g 上可略见一斑，该社区关于遗传算法的开发项目 多达3 9 个，这些充满活力的软件项目促进了遗传算法的不断更新发展。国内外作t s p 研究的学者不少，如果能把各自的算法程序都统一放到开源社区里，相信群策群力 一定会找到更好的算法。当然，实现这一目标的前提是要求各位学者把各自的算法 做成功能完备的软件。 综上所述，为了推广优良算法，并促进其不断完善发展，把它作成功能完备的 软件是非常必要的。 ( 2 ) t s p 可视化软件的研究意义 前文已提到，求解t s p 问题的现成软件很少；而可视化( v i s u a l ) 的t s p 处理软 件更是少之又少。开发出可视化的t s p 处理软件会有什么重要意义吗? 正! t l v i s u a l c 上+ 取代t c 、v i s u a lb a s i c 取代b a s i c ：可视化软件与字符界面软件做比较，开发调试 的功能和方便性上都不可同日而语。从大多数种类软件发展的历程来看，可视化界 面取代字符界面、可视化操作代替字符操作、用户接口越来越友好、简单是大势所 趋。因此开发可视化t s p 处理软件具有重要的意义。 首先、可视化t s p 处理软件将t s p 问题描述规范可视化处理。国际上比较公认 的t s p 问题描述规范是t s p l i b9 5 中应用的规范。所谓规范，即对相同类型的t s p 问 题统一预定义的表示格式，例女i t s p 上的两点距离( 或称两点“权重”) 既可以采用 矩阵形式也可以采用二维欧几里德坐标( i i u l 何坐标) 形式；前一种类型采用 f u l lm a t r i x 统一定义，后一种类型则采用e u c2 d 统一定义：f u l lm a t r i x 和 e u c 2 d 都是问题描述规范的一个具体表示形式。在t s p 数据文件的开头部分加入问 题描述规范一方面告知了t s p 数据是如何组织的，一方面也限定了对t s p 数据的求解 方式；因此问题描述规范在t s p 数据文件中必不可少。可视化t s p 处理软件内嵌入了 t s p l i b9 5 中关于多种t s p 问题的描述规范，可根据使用者的要求自动生成t s p 数据 文件开头部分的问题描述规范，这极大方便了使用者制作规范的t s p 数据文件。 其次、可视化t s p 处理软件整合了二维图形处理模块。我们大多研究的狭义t s p 问题都基于二维几何坐标表示点，点与点间距离直接采用几何距离表示，例如电路 板上布线图、平面地图上的旅行线路( 比较典型的如中国1 4 4 座城市环游问题) 等。 青岛大学硕士学位论文 该大类问题的一个共同特点是易于还原为二维图形，很多学者也都喜欢把这样生成 的一幅二维连线图放在自己的算法论文中以增强说服力。在没有可视化t s p 处理软 件之前，还原二维图形的工作大都会交给m a t l a b 或m se x c e l 等大型应用软件的图像 处理引擎来完成：这需要通过数据文件内容的重新整理和数据格式转化再图形生成。 相比之下t s p 可视化软件更加方便、专业。在可视化软件打开二维几何坐标形式表 示点的t s p 数据文件时，会自动生成对应的图形模式，而一旦计算最短路径获得， 图形模式上会自动绘出最优旅行；算法性能的优劣性由此一目了然。二维图形模块 不仅可以完成由点坐标到图形显示的转换，也可以逆向完成图上点到数据文件中坐 标的转换。使用者在图上点击添加点的同时，对应的t s p 数据文件中会同步添加该 点的坐标数据。 第三、可视化t s p 处理软件使算法求解数据和算法性能数据可视化。在应用t s p 的领域，获得求解数据至关重要。另一方面，评价t s p 相关算法优劣的主要指标， 一是比较求出的近似解和已知最优解之间的差异有多大；二是看算法求解的时间复 杂度( 当基于同等配置的电脑对不同的算法进行比较时，对空间复杂度的比较可以 忽略) ；这两项指标都可以通过算法性能数据得到。t s p 可视化软件在求出一个t s p 问题的最优解的同时，自动打开新视图将求解数据和算法性能数据显示，这不论是 对应用t s p 还是对测试t s p 算法性能都提供了很大便利。 综上所述，t s p 问题具有极高的实际应用价值、学术研究价值和智力挑战魅力； t s p 相关程序软件的研究开发对解决t s p 问题至关重要；而从软件进化的趋势来看， 可视化t s p 处理软件将会成为t s p 软件开发研究的重中之重。 4国内t s p 相关程序软件的研究现状 算法是软件架构的灵魂，在t s p 的世界里尚没有被广泛认可的最优良算法，关 于t s p 软件的研究开发也就变成无源之水。 目前国外学者在t s p 可视化软件领域的研究较少，而在t s p 软件架构领域作的 相关研究却相当细致。举例而言，关于t s p 上点的数据结构表示方法，a p p l e g a t e l 2 、 f m a r g o t 9 3 1 、m l f r e d m m l 2 4 1 等分别撰文作了论述，k e l dh e l s g a u n i s 0 1 在其改进的 l i n - k e r n i g h a n 算法实现中提到当问题规模小于1 0 0 0 点时，适宜采用双向链表结构 ( d o u b l yl i n k e dl i s t ) ，而在问题规模大于1 0 0 0 点时，适宜采用二层树结构( t w ol e v e l t r e e ) 。相比之下，国内学者在t s p 软件架构领域的研究比较薄弱，而在t s p 可视化软 件的研究领域基本空白。通过维普搜索t s p 算法，相应能找到各种t s p 程序开发平台 的文章，但这些文章很少能涉及到t s p 软件及可视化软件的研究细节。也有一些关 于程序架构的文章，但它们一般都侧重介绍整个程序流程，而在技术细节上却一笔 引言 带过。 马良等【2 5 用d e l p h i y ：发了解决大规模t s p 的程序，求解质量在高维表现良好( 解 决p c b 3 0 3 8 误差为0 0 2 4 ) ，但在低维的表现却有些差强人意( 解决p r 7 6 点误差高达 o 0 2 3 ) 。这有些让人难以理解，因为t s p 是超线性的n p 难题，即对任何算法( 目前 的研究公认) ，伴随点数的增加，其计算复杂度都成指数增加，依据常理，其误差也 应当趋向指数增加。从7 6 点到3 0 3 8 点，计算复杂度放大了成千上万倍，为什么会出 现误差相近的悖理现象? 该问题有待深入研究：另外，如果在他们的论文中附有程 序实现的具体介绍，相信会大大增加说服力。 储理才拉6 悃m a t l a b 开发了基于遗传算法的t s p 程序，同样做的还有陆子强等1 2 ”。 他认为m a t l a b 的矩阵向量结构易于实现遗传操作，且较c 等语言“简单、方便、直观”。 对这种认识不能苟同，基于m a t l a b 开发t s p 算法的模型比较合适，但是要解决实际 t s p 问题并不十分合适。m a t l a b 是解释性语言，速度慢是它致命的弱点( 目前还是) 。 但是求解t s p 问题需要太规模计算，编写t s p 算法程序的一个主要关注点就是运算速 度。同样的程序用c 语言较m a t l a b 实现要快几十倍甚至上百倍，为了编写程序上的方 便而尚失求解效率，这样做得不偿失。 陈东方等口8 编写了基于v i s u a lp r o l o g 的t s p 算法程序，没有提及性能，解决的问 题简单单一( 6 点的t s p ) ，如果用于解决其他问题就需要重写代码，这不值得推荐。 吴春英等【2 9 】用硬件实现遗传算法，并用于解决t s p ，这似乎可以获得最大的求解速 度，有兴趣者可以参考其论文。 还有一些国内的研究人员并没有直接提及开发t s p 软件，而是基于开发g i s 、物 流配送系统等系统间接介绍t t s p 软件的开发方法，例如陈彦军等【3 0 j 丑m a p l n f o ， m a p x 5 0 二次开发工具以及v b 6 开发g i s ，其解决的问题的实质是矩阵型数据组织的 t s p 。结合前文提到的可视化t s p 软件的特征，这一类目标简单的图上作业问题也可 以由可视化t s p 软件解决。 在广泛阅读国内众多学者论文的基础上，笔者对国内t s p 程序软件的研究现状 深有感触： 首先，大多数国内学者都重在研究算法，然后将算法做成程序，然后借助e x c e l 、 m a t l a b 等大型软件的图形引擎将数据映射成图上的点点连线( 大多采用二维几何坐 标表示点) ，却鲜有将算法程序拓展为软件( 更不用提可视化) ，无法实现算法引擎 与应用软件的高效整合。 其次，大多数国内学者描写算法论文的通用流程是：先将算法步骤由初到细的 描述出来，随后直接转入算题测试，并由此推知算法性能。这样做就忽略了从步骤 描述到程序测试之间的一个至关重要的阶段编程实现。还有一些学者将算法程 序摆出来，但他们的论文都侧重介绍算法整体实现的伪代码，而不重视对技术细节 青岛大学硕士学位论文 上的难点作深入描述，编程实现的着力深度不足。 第三，国际通行的广义t s p i h 题类型包括s y m m e t r i ct s p ( 对称旅行商问题) 、 a s y m m e t r i c t s p ( 非对称旅行商问题) 、h a m i l t o n i a nc y c l e p r o b l e m s ( 汉密尔顿环游 问题) 等好几种类型，我们一般研究的狭义t s p 问题即对称旅行商问题，简记作t s p 。 国内学者的研究重点是狭义t s p 问题，对其他几类t s p 问题较少涉及。即便是狭义的 t s p 问题，根据t s p l i b 中的定义规范，有c e i l2 d 、e u c2 d 、a t t 、g e o 、m a t r i x 等多种类型，类型之间的主要区别表现在点到点的成本表示方式不同，国内的学者 大都侧重解决e u c2 d 和m a t r i x 类型开发的配套程序也只适合解决少数问题，极 少能兼顾多种问题类型，这大大降低了程序适用性。 5 、本文主要内容 本文首先介绍了对l i n k e r n i g h a n 经典算法的改进。其中两方面主要改进分别是 基于0 t 接近度获取候选边集和升级( a s c e n t ) 操作。另外，对算法构造的重要细节， 第一章也给出较大篇幅介绍，包括选取待删除边的方法、基本移动的设计和初始解 的获取策略等。 随后，本文详细介绍了改进型l i n 。k e r n i g h a n 算法引擎的c 语言伪代码实现。在 内容上不仅包括了引擎整体框架的构建，还包括了引擎的i o 设计、相关数据结构设 计、对程序执行瓶颈的处理技巧等方面。 基于算法引擎，接下来的章节重在介绍v c 开发t s p 可视化处理软件。该软件扩 展模块包括数据处理模块和可视化模块两部分，对应各模块都有专门的模块架构策 略，本文给出了深入阐述。另外，就扩展模块和算法引擎的整合方法，本文也作了 详细论述。本文对构建通用t s p 算法引擎的难点下了很多笔墨，同时也对t s p 可视化 处理软件的开发策略作了深入剖析，这对广大t s p 研究开发人员的工作具有极强的 现实指导意义。 最后在软件测试部分，可视化t s p 处理软件对广义t s p ( t s p 、a t s p 、s c p ) 提 供了较满意的求解，它不仅适于解决t s p l i b 中的大部分问题，更是人工编写广义t s p 问题的集成开发环境。对于熟悉t s p 问题的研究者而言，该软件对其研究工作大有 裨益。而对不熟悉t s p 问题的应用者来说，该软件可协助做出t s p l i b 通用的t s p 问 题文件，进而提供满意解答。 一 改进型l i n - k e r n i g h a n 算法 一改进型l in k e r n i g h a n 算法 1 l i n - k e r n i g h a n 经典算法 1 1 基本算法 事实上，2 - o p t 算法是l - o p t 算法的一个特例【1 2 】，其中玲_ 2 。n o p t 算法在运算 的每一步将当前旅行上的x 条边用另外九条边取代，目标要使产生的新旅行比当前 旅行短。换句话说，该算法的每一步都要破坏九条边，再将相关的2 * x 个点重新组 合成九条新边，这可以看作是对条或多条子旅行进行逆序，从而获得比当前旅行 短的新旅行。 k o p t 算法基于n 最优性原理。 k 最优性原理：如果用任意x 条新边( 1 i n k ) 取代任意九条现有边获得的新旅 行都不及现有旅行的成本低，那么现有旅行满足k 最优( 或简记作h o p t ) 。 从以上定义非常容易推知任意满足x 最优的旅行也满足l - 最优，其中 1 - x 、 降= 1 ) ，其中t 2 i _ l 、t 2 。表示边x i 的两个端点；则有 y i = ( t 2 i ，t 2 h 1 ) ，x i + l = ( t 2 i + l ，t 2 i + 2 ) 。如下图所示，( x 1 ，y l ，x 2 ，y 2 ，x 3 ，y 3 ，) 【r ，y d 构成一 条链( ac h a i no f a d j o i n i n gl i n k s ) 。 图2 - 2 限制节点x i ，y i , x i + l ，y i + 1 的选取 使链( x t ，y i ，x 2 ，y 2 ，x 3 ，y 3 ，x r ，y ，) 成为旅行的一个必要条件是它是闭的，即y r _ ( t 2 r t 1 ) 。称这种情况下的交换是有序的( s e q u e n t i a l ) 。 一般而言，选取适当规模的边集并采用有序交换总可以使旅行得到改善，但 是这并不绝对。下图示意了一个非有序交换的例子。 x 一 ：li 一池 图2 - 3 非有序4 - o p t 移动 可行性规则( t h ef e a s i b i l i t yc r i t e r i o n ) 选取边x i - ( t 2 i 1 ，t 2 i ) 所依赖的根据是t 2 。连接t l ( 即y i ) 可以构成一条合法旅 行。这个规则是对= 3 的情形而言的，因为这样做可以确保尽快得到一条合法旅 行。从而缩短算法运行时间，并简化编程。 正获利规则( t h ep o s i t i v eg a i nc r i t e r i o n ) 本规则要求交换边集必须使旅行成本减少，换句话说即“正获利”。设当前边 集包含r 个连接，用g i - c ( x i ) c ( y 。) ( 1 0 。 如果找不到满足要求的y l ，则转步骤1 2 。 步骤5 ：令i = i + l 。 步骤6 ：选择边x i = ( t 2 j - 1 ，t 2 i ) t ，并使之满足t 2 ，与t l 相连可得到了一条新 旅行t 、；对所有的s o ； 对所有的s = 2 ) 情况下，x i 只有一种选 择才能保证在步骤7 ( 即y j = ( t 2 。，t 1 ) ) 构成一条合法旅行，而另一种选择却会导致 生成两条不相连的子旅行( 不合法的) 。但是对i = 2 是一种特殊情况，这种不合法的 旅行是被允许的，如下图所示。 1 ：1 ) 图2 - 4 选择x 2 ，而没有“闭上”( c l o s e u p ) 旅行 青岛大学硕士学位论文 如果边y 2 的另一个端点t 5 选取点t 2 和t 3 之问的点，则通过下一步边交换可构 成一条合法旅行。但是需要注意，点t 6 选择t 5 两个邻接点中的任意一个都可行，如 下图所示，算法要把两种情况都考虑进去。 图2 - 5x 3 有两种选择 另一方面，如果边y 2 的另一个端点t s 选取在t 4 和t l 之间，则下一点t 6 只能选 择t 4 和t 5 之间的点，再下一点t 7 必须选择t 2 和t 3 之间的点，再下一点t 8 可以选择t 7 两个邻接点中的任意一个，如下图所示。原算法分析了该情况下使c ( t ，t s ) 最大化 的各点选择策略。 图2 - 6该图中x 3 只有一种选择n 的选择范围受限制，而) 【4 有两种选择 步骤6 和7 的条件都用于确保边集x 和y 不存在公共边。即要添加的新边 y i 不能是之前刚被破坏掉的边，而要破坏的边x i 也不能是之前刚被添加的新边。 步骤8 1 2 导致算法回溯。注意，只有在实在找不到解改善的情况下，才要考 虑回溯操作，且回溯的层次只能是1 和2 。 步骤1 3 关于算法的终止条件，是指点t 。已将所有的可行点尝试完，而当前旅 行无法迸一步改善。如果必要，由步骤1 重新开始。 1 2 对基本算法的精练 算法运行的一个瓶颈是搜索合适的边放入边集x 和y 中。为了提高运