方法[1]。而这些CPP问题它的边长的权就是为1的。 1970年，一篇是关于中国邮递员问题在公共事业里的应用，原来是麻省理工的研究生

R.Stricker的论文。这也许是在“The Chinese postman problem”以后，早些时候发现的与 CPP问题有关系的。之后在1973，Edmonds、Johnson共同发出了“Euler tour and the Chinese Postman Problem”这一文。这是发现的第一篇比较系统的研究了CPP的论文。[1]

还是1973年，N.Christofides发布了文“The optimal traversal of a graph”，这篇文章也 是比较早的研究CPP问题。后来，Christofides和他的小组做了很多有关CPP的研究。1974 年Beltrami和Bodin的Networks and vehicle routing for municipal waste collection，以及1978 年Bodin和Kursh的A Computer-Assisted System for the Routing and Scheduling of Street Sweepers，也是早期关于CPP应用性的文章[1]。这几位作者，都是美国马里兰大学的。他 们的研究队伍，在此后的几十年中对CPP的理论与应用做了许多工作。

1976年，H.Papadimitriou证明了混合图上的CPP是NP-完全的，在已知无向图和有向图 上的CPP都是有多项式算法的情况下，这是第一个出现的NP-完全问题。不过，以后出现的 新的推广就几乎都是NP-完全的了。

近期在二十一世纪中国邮递员问题有关于的DNA脱氧核苷酸的计算：因为具有挺好的 一致性，所以这些问题得到了搞定，针对的是在完全问题上有硅而计算机却没法比拟的优 点。我们知道DNA脱氧核苷酸的稳定性还是比较好的，会看到在反应时的过程中是不会看 见发夹结构的而产生错解。在2000年Head的研发小组就是将DNA用于计算给出了最大单集 问题的质粒计算模型，就是Head的小组根据图的顶点用双链DNA进行排列编码，用DNA的 碎片当作外源DNA嵌入到经过改进后的质粒体中，就是运用DNA的基因重组技术开始编码， 再根据图的边批改质粒，直到做完运算。在质粒的DNA计算模型中它的主要优点是：在运 算中，目标DNA双链一直保持着双链，质粒的形状的变化为：从环形到线性再到环形，质 粒打开与关闭均是相应的一些酶精准的限制，在运算的过程中根据需要能够任意将质粒植 入宿主进行重组了。

CPP问题的延续还有2007年山东大学计算机系的写了一篇有关于基于一种新的边权编 码方法NBA计算模型。这是一个有困难有挑战的问题就是权编码方法去计算DNA的。制定了 一种用于表示有权的图中边权的DNA编码新的方案，还给出了用该方法去求解CPP的算法， 并利用Markov链解析了算法中怎么生成各种路径的随机过程。所提出的编码方案具有易 于编码、易于推广且错误率低的特点E该工作可提高DNA计算中表示和处理数值的能力，扩

展DNA计算求解最优问题的范围。 紧接着就有CPP的动态规划算法：算法原理CPP问题的多阶段决策过程模型 Nk 与传统

的确定性多阶段决策过程模型相比，具有本质的区别。使用动态规划逆向算法求解多阶段

决策过程模型 Nk ，该模型的初始权值0特性使得逆向求解得到错误结论。在多阶段决策过 程模型 Nk = <A，V，E>中，动态规划逆向算法不能直接求解CPP问题。CPDPA算法针对无向 CPP问题，结合动态规划中的决策思想，提出了该算法所具有的一些性质。步骤1：取一未 处理的多阶段决策模型进行逆向搜索；取 i=2m-1；步骤2：从第i阶段终端 aq 出发，当第

i-1允许状态集中某终态变量遍历次数小于2且非 aq 附属状态变量，满足

fk (xk ) min[dk (xk ,uk (xk ) fk 1(xk 1))] ，选其为下一策略 uq (aq ) 走向；若所有状态遍历次数 等于2，选取 aq 附属状态变量；若其与前一状态变量 aq 公共端点非 aq 的终止端点，则