方法[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 的终止端点,则

上一篇:国内外深基坑工程风险分析与防控对策研究现状
下一篇:大学生体质评估研究现状

中小民营企业的融资问题国内外研究现状

验证码识别算法国内外研究现状和参考文献

幼儿饮食习惯存在的问题研究现状

中学化学教学实施能力测...

国内外路径规划算法研究现状

滚动轴承研究现状与存在问题

多智能体系统的一致性问题国内外研究现状

安康汉江网讯

张洁小说《无字》中的女性意识

老年2型糖尿病患者运动疗...

新課改下小學语文洧效阅...

互联网教育”变革路径研究进展【7972字】

我国风险投资的发展现状问题及对策分析

ASP.net+sqlserver企业设备管理系统设计与开发

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

网络语言“XX体”研究