《中国邮递员问题各种算法的对比分析(36页).doc》由会员分享，可在线阅读，更多相关《中国邮递员问题各种算法的对比分析(36页).doc（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-中国邮递员问题各种算法的对比分析2008SX 2011002附录2 图论课程专题论文论文题目： 中国邮递员问题各种算法的对比分析 班 级： 2008级数学与应用数学 组 长： 马利巍 姓名马利巍陈世红周子婷石静余庭学号P081513092P081513090P081513091P081513095P081513120成绩分工情况构思论文框架，进行论文摘要部分、以及内容撰写，对论文内容进行审定工作构思论文框架，进行论文主体内容撰写，对论文归纳总结，并进行论文文字敲定工作构思论文框架，进行论文主体内容撰写，总结论文，并进行论文文字敲定工作构思论文框架，对论文内容审定，对论文进行归纳总结，以及论文
2、格式排版工作构思论文框架，进行论文文字敲定，以及论文打印工作2011年 12 月 27 日论文评价指标与鉴定意见论文题目中国邮递员问题各种算法的对比分析完成人 马利巍 陈世红 周子婷 石静 余庭 班级2008级数学与应用数学指标论文评价（对表格中的各栏，用“”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86100分）B（7085分）C（6069分）D（059分）鉴定意见成绩评阅人职 称专 业摘要本文基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,进一步讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型；并研究了随
3、机中国邮递员问题,建立了相应的确定型等价模型。并可以利用奇度数结点的配对来进行求解。根据此思想给出了一种新的求解思路通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。提出了“虚拟权值”和“虚拟节点”的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解；然后,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。通过各种算法分析比较表明,新算法具有易于解读、编码简单等特点。 关键字 ：中国邮递员问题 整数规划 最优化模型 奇度数结点 最小生成树 DNA计算 多聚酶链式反应
4、 AbstractBased on the traditional Chinese to figure without the postman problem,The corresponding display integer programming model，further discussed based on adirected graph of the generalized China the postman problem，the corresponding display integer programming model；And the traditional China th
5、e postman problem，established the corresponding equivalent model that can and can use odd degree of nodes to solving matching。According to this thought gives a new method for solving thinkingby removing the original graph of the degree and use the node accidentally minimum spanning tree to determine
6、 the degree of the nodes pairing。Put forward the “virtual weights ”and “virtual node ”，given China a postman of DNA computing algorithm is based on。First the new algorithm is more Meilian together to exclude the technology of reaction solution，and then got the postman all feasible solutions to probl
7、ems；And then，based on the surface with DNAcalculation methods and fluorescent markers，and from all the feasible solution of eventually get the optimal solution。Through the comparison of the algorithm analysis show that the new algorithm is easy to read，code simple features。Key words：The postman prob
8、lem of China Integer programming Optimization model Odd degree node Minimum spanning tree DNA calculation More Meilian together in response中国邮递员问题（Chinese postman problem）也称中国邮路问题，是我国数学家管梅谷于1960年首次提出来的，引起了世界不少数学家的关注。例如1973年匈牙利数学家Edmonds和Johnson对中国邮路问题提供了一种有效算法。这个问题的实际模型是：一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过
9、由他负责投递的每条街道至少一次，为这位邮递员设计一条投递线路，使其耗时最少。任给定一个图G，对E(G)加权，即对每个，任意指定一个非负实数，求G的一个含有一切边回路W，使得W的总权如果G是Euler图，则所求的中国邮路W就是一条Euler回路。1921年，Fleury给出求Euler图G中一个Euler回路的算法。值得指出的是，即使已知G是Euler图，如果没有一定的路线遵循，也不是漫不经心就可以找出它的一个Euler回路的，例如图1是Euler图，设从开始，寻找一条Euler回路，如果开始三步是就失败了，因为回到之后发现左侧的上的边还没有用过，而的关联边已全用过，不能从再去通过左侧那些未用图
10、 1过的边了（注意每边只能用一次）。究其失败的原因，是因为用了边之后，在未用过的边们导出的子图上，是桥，提前过桥的后果是断了去左侧的后路。这里的教训是，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，Fleury设计了如下求Euler回路的有效算法，代号FE算法：（1） 任取，令.（2） 设行迹已选定，则从中选一条边，使得与相关联，且非必要时，不要选的桥。（3） 反复执行（2），直至每边皆入选为止。 FE算法是有效算法，其时间复杂度是。 用FE算法在上图中可选得Euler回路：FE算法的正确性证明如下： 令G是Euler图，是FE算法终止时得到的行迹，由算法知在中的次数为零，显然，于
11、是是G的一条闭行迹，下证就是G的Euler回路，反证之，若不是G的Euler回路，设是中次数非零的顶组成的顶子集。容易看出，且。令，则；设m是，而的v的下标的最大值，见图2。由于的终点在中，于是是的桥，设e是中与关联的边。且，由算法知e为的桥，故e也是在中导出的子图的桥。设是在中导出的子图，则，于是每顶皆偶次，中无桥，与e是的桥矛盾。 图 2下面讨论加权图G中有奇次顶时中国邮路问题的解法。这种情形有的边不得已要通过至少两次，哪些边要通过不止一次才能使得完成投递的时间最短呢？让我们通过一个实例来探讨这一问题。在图3中，边旁写的是权图 3（1） 在图3中，奇次顶集为（2） 在中，每对顶的距离为（D
12、ijkstra算法去求）：（3） 构造完全加权图，边权，见图4：图 4（4） 求（3）中的最佳（总权最小）的完备匹配， （5） 在G中求得和间最短轨；与间最短轨（6） 在G中沿与把边变成同权“倍边”，见图5图 5（7） 在Euler图5上用FE算法求得一条Euler回路即为所求的中国邮路（不唯一） 上述解法具有代表性，一般的中国邮路解法步骤总结如下： 设G是连通加权图（1） 求G中奇次顶集合.（2） 对中的每个顶对，用Dijkstra算法求距离.（3） 够作加权完全图,，中边之权为.（4） 求加权图的总权最小的完备匹配M.（5） 在G中秋M中同一边之端点间的最短轨.（6） 把G中在（5）求得的
13、每条最短轨之边变成同权倍边，得Euler图G.（7） 用FE算法求G的一条Euler回路W，W即为中国邮路.2.1 中国邮递员问题的整数规划模型关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的，国际上现在统称之为中国邮递员问题。早期关于中国邮递员问题的讨论总是基于无向图展开的，事实上，由于单行线或上下行路线的坡度等原因，这一问题有时必须借助于有向图来进行研究和解决。到目前为止，对中国邮递员问题的研究主要是从图论角度展开的，给出的多数都是各种启发式算法或递推算法。本文从数学规划的角度进行研究。数学规划建模具有借助软件包求解方便、易于修改和推广等多方面的优点，即使对于大型问题也易于建模
14、分析和解决的优点。传统的中国邮递员问题可以概述如下：一个邮递员每次送信要从其所在的邮局出发，走遍所负责投递范围内的每条街道，完成送信任务后回到原来的邮局，应该选择怎样的路线行走，才能使得所走的总路程数最小。把该问题抽象成图论问题就是给定一个连通图G(V，E)，其中：是顶点的集合，表示街道交汇的地方；E是顶点间边的集合，表示街道，即，每个边上有非负，表示边即街道的长度。问题是要确定G的一个子图(是一个圈)，它过每条边至少1次，而且使得该圈的总权(即图上各边的和)最小。从图论知识知，若G不含有奇点(即相邻边的个数为奇数)，则G有圈，它过每边1次且仅仅1次，所以这个圈就是所要求的圈。若G含有奇点(即
15、相邻边的个数为奇数)，则G的任一过每边至少上通过了k次，设，就在与之间添加k-1条新边，并令这些条新边的权都等于边的权，称这些新边为的添加边。显然，若边e上的添加边多余1条，那么去掉其中偶数条后，得到的图中任一过每边至少1次的圈的总权不会增大。因此可以假定每边上添加边的个数至多1条。这样，寻找邮递员最优投递路线的问题就可以归结为如下：给定连通图G(V，E)，每条边对应的顶点和之间添加1条边，得到边数双倍于G的另一个连通图G(V，E)，求 E， E使不含奇点且总权为最小。若 ，则记为或(i，j)，而相应的添加边为，与边相对应，设定0-1整数变量。若，即称边是从到的，或称为弧。这样，就可以把无向图
16、理解为有向图。每个惟一对应一组的值，反之亦然。可以借助变量(i=1，2，n； j=1，2，n)来定义最优投递员问题的约束如下：（1）过每边至少1次且添加边至多1条，E1对应的所有的xi，j的值(称为E1的值系)满足：对（2）图不含奇点，即对于任意一个顶点Vi，有进向弧，必有与之等量的出向弧：这一问题的目标是使得的总权最小，即min，其中，为边上的权，。这样，就得到中国邮递员问题的显式整数规划模型(CPP)如下这一模型不仅可以用于求解中国邮递员问题，而且可以确定相应的最优投递路线：如=1，即表示邮递员应该从沿着边(即街道)到。上节所述的邮递员问题，假定了邮递员投递范围内的每条街道的上行和下行是无
17、差别的，而在实际信件的投递过程中可能不是这样的，如遇到单行线街道、街道有一定的坡度、街道两边不能单行中同时投递等。这样的邮递员问题称之为广义的中国邮递员问题。这一广义的中国邮递员问题可以抽象为一个有向图问题。类似于前面所述的邮递员问题(称为传统的中国邮递员问题)，广义的邮递员问题可以叙述为：给定一个连通有向图G(V，E)，每个弧e上有非负权w(e)，需要寻找G的一个回路，它过每个弧至少1次，且使得总权为最小。对于广义的中国邮递员问题，添加弧的个数至多1条有时已经不再可行，即需要多条添加弧，才能使对应的连通有向图G的任一顶点的进向弧数与出向弧数相同，从而使G(V，E)存在回路(E回路)。在此，如
18、e=(，)E，则称弧e是顶点的进向弧，同时也是顶点的出向弧。可以证明，如G(V，E)的顶点数为n，则每条弧上至多增加(n-1)条添加弧，即可实现各顶点的进向弧数与出向弧数相等。根据以上分析，对于G(V，E)的每条弧E定义一正整数变量，表示弧上增加了条添加弧，由此形成另一个有向图G(V，E)。类似于上节的分析，可以有如下广义中国邮递员问题的显式整数规划模型(GCPP)：通过这一模型的求解，可以得到广义中国邮递员问题的最优投递路线。数值例示求解例一.考虑图1所示的中国邮递员问题：图1传统中国邮递员问题根据前面的模型讨论，这一数值例示邮递员问题对应的整数规划模型如下： +应用整数规划求解工具QSB，
19、求解得到这一问题的最优解，如：其他，最小权重为68。假定邮局在顶点，则有如下最优投递线路：注意，这一问题的最优投递路线不惟一。同理可以求得邮局从任何一顶点出发时的最优投递路线。例2考虑图2所示的广义中国邮递员问题。图2广义中国邮递员问题相应的广义中国邮递员问题的整数规划模型如下：应用相同的整数规划求解软件，求解这一模型得到下列最优解：最小权重为159。假定邮局在顶点，则有如下投递路线：这是一个回路。类似可以确定邮局在任一顶点时的最佳投递路线。这一最优投递路线是根据模型的最优解，采用类似接龙游戏的方法找出的。这里需要注意的是，如某的值大于1，意味着该弧要重复走。所有的和应等于所走的所有街道数(包
20、括重复走的)。2.1.3随机中国邮递员问题及其建模上述讨论的传统的和广义的中国邮递员问题都假定与边或弧相联系的权重是确定型的常数。实际中经常遇到权重非固定的情况，如考虑的权重是该街道上所花费的投递时间，这一参数往往不是常数，每次投递所花费的时间会由于邮件量的多少而变动，但一般会遵循某种变化形式，即权重是具有某种分布的随机变量，这时可以称对应的问题为随机中国邮递员问题。处理传统中国邮递员问题的奇偶点图上作业法及其改进算法对这一随机问题都无能为力，但借助于本文建立的整数规划模型，应用随机规划理论，可以很方便地进行处理。随机问题的处理方法有多种，如期望值法、机会约束法、最优值分布法、相关机会约束法、
21、多阶段(如两阶段)法。本文在此处仅讨论机会约束法，其核心是概率约束条件的确定型等价处理。其他方法可以按照随机规划理论类似处理，在此略去。注意到，CPP或GCPP的约束中都不含有权重参数，因此，处理权重随机的问题只需要将目标函数做相应的确定型等价处理即可。权重随机时，目标函数也是随机变量，根据随机规划理论，随机的CPP问题可以转化为如下2个确定型等价模型： 1-CPP()minw2-CPP(w)max其中，1-CPP()指对固定的求解以及权重w。而2-CPP(w)指对固定的权重w求解和。此处，称为权重w的可行度，w为总权重的希望水平。如果诸权重均服从正态分布而且相互独立，服从，则1-CPP()和
22、2-CPP(w)分别等价于下列2个数学规划：1-NCPP()minw2-NCPP(w)max 其中：F(X)为标准正态累积分布函数；F-1(y)为其逆函数。进一步地，可分别等价于如下2个数学规划问题：1-NCPP() 2-NCPP(w) 其中，注意到F-1()是的单调递增函数。对于其他类型的随机问题也可以类似地进行分析。注意上述规划是非线性的，因此需要借助非线性整数规划的求解工具和软件或两阶段法进行求解，大型问题也可以借助于现代智能优化算法进行求解。对于广义中国邮递员问题也可以类似讨论相应的随机问题，在此从略。基于传统的中国邮递员问题，建立了这一问题的显式整数规划模型，并将之推广到基于赋权有向
23、图的广义邮递员问题和权重不确定的随机邮递员问题。另外的推广是考虑权重是模糊型或灰色型、粗糙型、信度型的中国邮递员问题，根据相应的不确定性内涵，对于目标函数进行相应的确定型转化。本文讨论的是单目标问题，如果考虑多目标中国邮递员问题，数学规划灵活、机动、易于修正和变形的特点，可以用来非常方便地处理这一可能的拓展问题。中国邮递员问题是我国数学家管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？下面用图论的语言来描述：在一个带权图G中，能否找到一条回路C，使C包含G
24、的每条边至少一次且C的长度最短？该问题求解思路大体包括三个方面：(1)若G没有奇度数结点，则G是Euler图，于是Euler回路C是惟一的最小长度的投递路线。(2)若G恰有两个奇度数结点和，则G具有Euler迹，且邮局位于结点，则邮递员走遍所有的街道一次到达结点；从返回可选择其间的一条最短路径。这样，最短邮问题转化为求到的Euler迹和到的最短路径问题。(3)若G中奇数度结点的数目多于2，则回路中必须增加更多的重复边(路径)。这时，怎样使重复边的总长度最小？前面两种情况比较容易求解，第三种情况相对要复杂一些，因为涉及到奇度数结点的配对问题。当奇度数结点数目只有两个时，它存在的配对方案只有1种；
25、当奇度数结点数目有四个时，它存在的配对方案有31=3种；当奇度数结点增加到六个时，它存在的配对方案增加到531=1 5种。依此规律，有下面的结论：定理设连通图G中有n(n2)个奇度数结点，则存在奇度数结点两两配对的方案数共有(n-1)(n-3)(n-5)1种。求解中国邮递员问题的传统方法是通过计算奇度数结点之间的最短路径来确定结点配对，添加重复边。但是，从上面定理的结论可以看出，当图中的奇度数结点数目较多时，其计算量将非常大。因此，我们可以考虑，既然核心问题是要解决奇度数结点的配对问题并在奇度数结点之间添加重复边，那么不妨将原始图中的偶度数结点去掉，只考虑奇度数结点，并利用最小生成树的观点来快
26、速地找出奇度数结点的最优配对方案。具体思路如下：(1)去掉原始图中的偶度数结点，即得到的新图中只包含原奇度数结点与它们之间的路径；(2)求新图的最小生成树；(3)由最小生成树确定奇度数结点的配对；(4)在原始图中添加重复边。3.3 求解实例例 求解如图1所示的中国邮递员问题。解 (1)如图1所示，该中国邮递员问题共有8个奇度数结点，即(2)去掉图1中的偶度数结点，得到新图2。 图1 图2(3)求图2的最小生成树(如图3所示)。(4)由图3可知与配对，与配对，与配对，与配对。图3 图4(5)根据奇度数结点的配对在原始图1中添加重复边(如图4所示)，经检验此方案已是最优。目前，人们已对DNA计算技
27、术展开了深入研究。应用DNA计算方法，开拓性地解决了一个给定有向图的Hamilton路径问题。给出了一种对于可满足性问题(SAT问题)的DNA计算模型。利用单链DNA分子的“发夹”结构，解决了一个3-SAT问题。给出了一种基于表面的SAT问题的算法，随后对其进行了改进。将DNA计算应用于0-1规划问题，解决了一类特殊0-1规划问题，即指派问题的推广。在其基础上完全解决了0-1规划问题，并将进而解决了两类特殊的整数规划问题。中国邮递员问题是运筹学中的一个重要问题，本文提出了“虚拟权值”和“虚拟节点”的概念，然后基于DNA计算在并行运算方面的良好特性，提出了中国邮递员问题的一种基于DNA计算的新求
28、解算法。新算法首先利用多聚酶链式反应技术来排除非解，从而得到中国邮递员问题的所有可行解；然后，结合基于表面的DNA计算方法与荧光标记策略等技术，最终从所有可行解中析出最优解。算法分析表明，新算法具有易于解读，编码简单等特点。4.1DNA计算模型DNA是一种高分子化合物，组成它的基本单位是脱氧核苷酸，每个脱氧核苷酸由一分子磷酸，一分子脱氧核糖和一分子含氮碱基组成。含氮碱基有四种，即腺嘌呤(A)，鸟嘌呤(G)，胞嘧啶(C)和胸腺嘧啶(T)。DNA不仅具有一定的化学组成，还具有规则的双螺旋结构。DNA计算的基本思想是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA
29、分子链，在生物酶的作用下，生成各种数据池(Data Pool)，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控生化反应过程，最后利用多聚酶链式反应PCR，凝胶提纯，诱变等分子生物技术检测所需要的运算结果。DNA计算的核心问题是将经过编码的DNA链作为输入，在试管内或其他载体上经过一定时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物中能得到全部的解空间。4.2中国邮递员问题的DNA计算模型4.2.1中国邮递员问题简介中国邮递员问题是运筹学中的一个重要问题。问题的描述如下：一名邮递员负责投递某个街区的邮件，如何为他(她)设计一条最短的投递路线(从邮局出发，经
30、过投递区内每条街道至少一次，最后返回邮局)？显然，上述中国邮递员问题可抽象为以下图论模型中的问题。中国邮递员问题的距离图模型。对于给定的连通无向图，其中为图中的节点集合，为图中的无向弧集合，令为无向弧对应的距离，则对图中给定的节点，需要从所有可能路径集中求得一条最优路径。其中满足：1) 从节点开始到节点结束；2) ；其中满足：，其中表示路径中所有无向弧对应的距离之和。图1给出了一个中国邮递员问题的图论模型示例。图1具有4条街道的中国邮递员问题的图论模型图1中，标识为节点表示邮局，则显然路径为满足要求的最短路径之一，路径总长度为470m。4.2.2中国邮递员问题的图论模型变换由于4.2.1节中给
31、出的中国邮递员问题的距离图模型无法直接应用于DNA计算，因此需要对其进行适当变换。在给出具体变换模型之前，先给出需要用到的相关概念的定义。定义1虚拟权值。给定的连通无向图，其中为图中的节点集合，为图中的无向弧集合，令为无向弧对应的距离，将按距离长度进行分组，假定可分为个组，其中表示属于组中的无向弧的距离长度。我们称组对应的组号为属于组中的无向弧的虚拟权值。对属于组中的任意无向弧，其虚拟权值记为。由定义1可知，第2. 1节中的中国邮递员问题可转化为以下图论问题。中国邮递员问题的虚拟权值图模型，对于给定的连通无向图，其中为图中的节点集合， 为图中的无向弧集合，令为无向弧对应的虚拟权值，则对图中给定
32、的节点，需要从所有可能路径集中求得一条最优路径。其中满足：1) 从节点开始到节点结束；2) ；其中满足：，其中表示路径中所有无向弧对应的虚拟权值之和。图2给出了图1所示的中国邮递员问题的距离图模型所对应的虚拟权值图模型。图2虚拟权值图模型定义2虚拟节点/路径节点。给定的连通无向图，其中为图中的节点集合，为图中的无向弧集合，令为无向弧对应的虚拟权值，假定无向弧的两个端节点分别为A，B，则在无向弧上可增加个中间节点，将平均分为段，令， 即有，其中表示节点之间的无向弧对应的虚拟权值。以上新增加的中间节点称为“虚拟节点”，而图中的节点集V中的节点成为“路径节点”。由定义2可知，第3. 1节中的中国邮递
33、员问题可转化为任意无向弧的虚拟权值均为1的以下图论问题(除非特别标明，下文中的节点均为对包括虚拟节点和路径节点在内的所有节点的统称)。中国邮递员问题的虚拟节点图模型：对于给定的连通无向图，其中为图中的节点集合， 为图中的无向弧集合，则对图中给定的节点，需要从所有可能路径集Pj中求得一条最优路径j。其中满足：(1) 从节点vs开始到节点vs结束；(2) ；其中满足：，其中表示路径中所有无向弧对应的虚拟权值之和。图3给出了图2所示中国邮递员问题的虚拟权值图模型所对应的虚拟节点权值图模型，其中P、A、B为路径节点，标号1到12的节点为虚拟节点。例如：在图3中，P1234A876P5A9101112B
34、1211109A5P即为一条满足中国邮递员问题要求的最优路径，该路径包含的虚拟权值之和为23。4.2.3中国邮递员问题的DNA算法对给定街区的中国邮递员问题，依据2.2节中的描述，首先给出问题对应的虚拟权值图模型，其中为连通无向图，为图中的节点集合，为图中的无向弧(路径)集合。然后，再给出问题对应的虚拟节点图模型，其中为连通无向图， 为图中的节点集合， 为图中的无向弧(路径)集合。显然，由3.2.2节中的描述可知有：。针对中国邮递员问题对应的虚拟节点图模型，不妨假定节点为邮局，则对应的中国邮递员问题的DNA算法如下：步骤1随机生成大量长度为20-mer的DNA单链，对，选择n个不同的DNA单链
35、分别与其对应。对任意节点，用表示其所对应的DNA单链。步骤2 ，得到对应的反转补链。并在试管T1中生成大量的拷贝。步骤3 ， ，其中为一条邮局节点 (用S表示邮局)， 之间的路径。则用如下方法生成DNA单链、来表示路径，并在试管T2中生成大量、的拷贝。（1）用依次链接上最后再链接上的前10-mer寡聚核苷酸，所构成的长度为20(t+1.5)-mer的DNA单链，来表示路径；（2）用依次链接上最后再链接上的前10-mer寡聚核苷酸，所构成的长度为20(t+1. 5)-me的DNA单链，来表示路径。步骤4， ，其中为一条之间的路径。则用如下方法生成DNA单链、来表示路径，并在试管T3中生成大量、的
36、拷贝。1)用的后10-mer寡聚核苷酸，依次链接上、最后再链接上的前10-mer寡聚核苷酸所构成的长度为20(t+1)-mer的DNA单链，来表示路径； 2)用的后10-mer寡聚核苷酸，依次链接上、最后再链接上的前10-mer寡聚核苷酸所构成的长度为20(t+1)-mer的DNA单链，来表示路径。步骤5将试管T1、T2、T3倒入试管T4。在试管T4中将产生大量的连接酶反应。注：连接酶反应：存在一种称为连接酶的酶，该种酶能将两条不同的DNA单链串联成为一条DNA双链。步骤6利用作为引物，基于多聚酶链式反应(Polymerase Chain Reaction， PCR)放大技术，使得步骤5所得到
37、的产物中，仅以起始，并以结束的DNA双链得到放大。分离放大的DNA链并保存到试管T5。加热解开试管T5中的DNA双链，生成DNA单链。步骤7 ，其中为一条之间的无向弧，为之间的虚拟节点，则分别利用吸附到磁珠上的、来孵化(Incubate)生成的单链DNA。由于只有包含或的DNA单链才能与或产生连接酶反应，因此可通过磁珠的磁性分离出试管T5中包含或的DNA单链。步骤8对步骤7所得到的产物，依次对中的所有其他无向弧分别重复步骤8。保留最终得到的DNA单链。步骤9对步骤8所得到的所有DNA单链，首先，使之带上负电，然后将其放置于矩阵凝胶体(GelMatrix)的负极。基于相斥原理，所有DNA单链将向
38、反方向移动。由于长的DNA链的移动速度小于短的DNA链，因此，可以分离出移动速度最快的DNA单链。步骤10对步骤9所得到的任意DNA单链，按以下方法确定其对应的路径中包含的各条无向弧的访问顺序：1) 将得到的DNA单链固定在表面上；2) ，其中为一条之间的无向弧，为之间的虚拟节点，将、连接上不同的荧光素；3) 将、加到表面上；4) 重复上述步骤2)和3)，直到DNA单链构成DNA双链。5) 利用激光共聚焦显微镜观察表面上的DNA双链的荧光素颜色，即可确定其对应的路径中包含的各条无向弧的访问顺序。显然，针对具有n个节点的模型，步骤1的时间复杂度为O(n)；在步骤2中，由于DNA计算的并行性，针对
39、不同的，在试管T1中生成大量的拷贝是同时进行的，因此其时间复杂度也为O(n)；在步骤3中，假定模型中的不同路径条数为m，则步骤3的时间复杂度为O(m)；类似步骤3，易知步骤4的时间复杂度也为O(m)；步骤5、6、7、8的时间复杂度显然均为O(1)；而对步骤10，由于模型中的不同路径条数为m，因此得到的DNA单链至多为m，因此，其时间复杂度为O(m)。一般而言，由于m n，故综上所述，算法的总的时间复杂度为O(m)。4.2.4算法分析以图3为例，假若节点P为邮局，简要介绍3. 3节中给出的中国邮递员问题DNA算法的具体执行过程。步骤1随机生成大量长度为20-mer的寡聚核苷酸链，对共15个节点选
40、择15个不同的DNA链分别与其对应。例如：可选择、。步骤2对任意，得到对应的反转补链。并在试管T1中生成大量的拷贝。步骤3 ，其中为一条 (用S表示)， 之间的无向弧。生成DNA单链、来表示P，并在试管T2中生成大量、的拷贝。步骤4 ，其中为一条之间的无向弧。生成DNA单链来表示P，并在试管T3中生成大量的拷贝。步骤5 将试管T1、T2、T3倒入试管T4。在试管T4中将产生大量的连接酶反应。步骤6利用作为引物，基于多聚酶链式反应放大技术，使得步骤5所得到的产物中，仅以起始，并以结束的DNA双链得到放大。分离放大的DNA链并保存到试管T5。加热解开试管T5中的DNA双链，生成DNA单链。图4给出
41、了一条以起始，并以结束的DNA双链实例。图4一条以起始，并以结束的DNA双链实例图5给出了一条DNA双链加热解开后生成的DNA单链实例。图5一条生成的DNA单链实例步骤7 ，其中为一条之间的无向弧， 为之间的虚拟节点，则分别利用吸附到磁珠上的、来孵化生成的单链DNA。然后，通过磁珠的磁性分离出试管T5中包含或的DNA单链。例如：分别利用吸附到磁珠上的、即可分别通过磁珠的磁性分离出包含或的DNA单链。显然，图5所示的DNA单链满足要求。步骤8对步骤7所得到的产物，对中的所有其他无向弧分别重复步骤8。显然，最终得到的DNA单链所对应的路径包含中的所有无向弧。例如：依次分别利用吸附到磁珠上的、即可分
42、别通过磁珠的磁性分离出同时包含或、或、或、或的DNA单链。在本例中，显然图5所示的DNA单链满足要求。且易知，最终得到的这种DNA单链所对应的路径包含中的所有无向弧。步骤9对步骤8所得到的所有DNA单链，首先，使之带上负电，然后将其放置于矩阵凝胶体的负极。基于相斥原理分离出移动速度最快的DNA单链。在本例中，显然图5所示的DNA单链满足要求。步骤10对步骤9所得到的任意DNA单链，确定其对应的路径中包含的各条无向弧的访问顺序。例如：针对图5所示的DNA单链，将其固定在表面上，然后将带有不同荧光素的、加到表面上，利用激光共聚焦显微镜观察表面上的DNA双链的荧光素颜色，即可确定其对应的路径中包含的
43、各条无向弧的访问顺序。4.3 总结 DNA计算由于具有良好的并行性，因此在解决一类困难问题，特别是完全问题上具有硅计算机无法比拟的优势。利用多聚酶链式反应放大技术，提出了中国邮递员问题的一种基于DNA计算的求解算法。算法分析表明，新算法具有易于解读、编码简单等特点。权编码方法是DNA计算中一个重要且有挑战性的问题。设计了一种新的用于表示赋权图中边权的DNA编码方案，给出了用该方案求解中国邮递员问题的DNA算法，并利用Markov链分析了DNA算法中生成各种路径的随机过程。对于任一赋权图，首先通过边到点映射把它转换为广义边图。图的每条边被分别映射为图的一个顶点。若中与邻接，则连接中和。若中为奇顶
44、点，则在与关联的边对应的的顶点上添加自环。用于编码顶点的DNA串的长度等于边的权值。用于编码边的DNA串为的后半部分与的前半部分并置后的逆补。所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点。该工作可提高DNA计算中表示和处理数值的能力，扩展DNA计算求解最优化问题的范围。DNA计算是一种利用DNA分子之间的相互作用来实现并行计算的新的计算模式，它借助分子生物技术来发展理论计算机科学。1994年，Adleman利用DNA分子求解了一个7顶点有向图的Hamilton路问题，开创了用分子生物技术进行计算的新方法。自此以后，DNA计算的研究迅速发展起来。1995年，Lipton在Adle
45、man实验的基础上抽象出一种分子计算的并行模型，并利用该模型成功地求解了3-SAT问题。1997年，Ouyang等人利用DNA计算求解了图的最大团问题。2000年，Sakamoto等人利用单链DNA分子的发夹结构将逻辑运算的约束条件编码于DNA分子中。DNA计算的这些早期研究都不需考虑权值的编码问题。然而，有许多实际问题涉及权值，因此，研究权值的DNA编码方法是一个重要且有挑战性的问题。设计了一种新的用于表示赋权图中边权的DNA编码方案，并用该方案求解了中国邮递员问题。为便于计算，假定赋权图中边权值均为偶数。若存在一个或多个奇数的边权值，则将所有边权值均乘以2，此时所求最优解值的一半即为所求。
46、5.1 基于边权的DNA编码方案目前已有的DNA计算模型首先都基于顶点的编码，在选定顶点编码的前提下再换算出边的编码，这就使得边权的处理非常困难本文提出了一种基于边权的DNA编码方案，能很好地解决中国邮递员问题中权值的编码问题。5.1.1无向图的边到点映射定义1给定无向图，构造一个双射函数使之满足：对于图的任一边，图中存在惟一的顶点使得；对于图的任一顶点，图中存在惟一的边使得若中边邻接，则连接中顶点。若中为奇顶点，则在与关联的边对应的中顶点上添加自环。上述过程称为边到点映射。边到点映射所得到的无向图称为的广义边图。考虑图所示的赋权无向图，其边到点映射的过程如下：1)把图的边分别映射为图的顶点；2)考虑中顶点之间的连接情况，由于中边与边邻接，故在中把顶点分别与顶点连接起来，由于中邻接，故在中把连接起来，以此类推；3)考虑中自环的添加情况，由于中顶点为奇顶点，而与关联的边有，故在中顶点上分别添加自环。通过边到点映射所构造的广义边图如图1(b)所示。图1赋权无向图及其广义边图其中，(a)一个赋权无向图；(b) 的广义边图借助于边到点映射，可以把求中经过每条边至少一次的最短回路转换为求中经过每个顶点至少一次的最短回路。需