五、总结
地图的着色问题是很著名的图论问题，它是一个N P 难题。 本文考察了三剖分边着色的性质， 根据三剖分脉的定义提出了平滑三剖分三着色脉组的概念， 从而我们通过寻找脉组就可以立刻找出它的着色来。 根据这一特点， 我们设计了一个三着色的D N A 算法， 这一算法可以找出平滑三剖分所有的三着色来， 通过这种设计， 我们还给出了一个顶点四着色的算法。由于任何一个地图都可以转化成一个三剖分的顶点着色问题，从而对于任何一个地图，我们都可以对它进行着色。
本文的研究工作有以下创新之处;
1 .提出了脉组的概念，证明了平滑三剖分三着色的脉组存在性定理;
2 .本文的编码方式十分简单、直观，编码具有规律性，易于实现;
3 .对平滑三剖分，给出了新的具有多项式时间复杂度的D N A三着色算法和四着色算法;
4 .本文对平滑三剖分的三着色算法和四着色算法，是具有线性空间复杂度的， 这一点在以往D N A 计算中是很少有。 因此极大的提高了D N A 计算可以解决问题的规模;
5 .对算法进行了计算机的模拟验证。尽管如此，由于学科的交叉性强的特点和自身能力的不足， 文中也出现了一些遗憾。有几个方面:
本文没有经过生化实验的验证。 虽然文中的例子和计算机模拟生化反应都验证了算法的可行性， 但是如果没有经过生化实验， 算法只能说是理想的。以后应当提出更加详细的编码方案， 从而方便以后的生化反应的实现， 但是要实现很好的编码，需要更多生物、化学知识的支持。计算机模拟部分还有很多工作可做，比如可以通过程序寻找两两不同的脉组的个数， 来寻找色数和图的关系式; 可以
使程序自动生成图的全部四着色方案: 可以模拟分子反应的动力学机制， 从而更加贴近实验室环境等方面。
本文算法只局限于对地图进行着色时有良好的性质， 用本文的方法， 我们只能造成一台地图着色的D N A专用计算机， 而离一台通用的、 可以编程的D N A 计算机还有很长的路要走。 地图的着色和四色定理的解决息息相关，以后的工作如果能从这里找到解决四色定理的更有效的算法，将是一件更加有竟义的事信。
优、小组成员分工情况：
刘洋：主要负责具体的算法设计和源代码的编写。
杨丽：主要负责着色问题和四色定理的资料的收集和相关代码的编写。
王玲：主要负责程序调试和修改、DNA算法资料的收集以及文档的整理。
参考文献
[1]王晓东 《计算机算法设计与分析》电子工业出版社
[2]冯舜玺 《数据结构与算法分析》机械工业出版社
[3]李红 《算法分析设计与实践》清华大学出版社
[4]陈红 《计算机算法》电子工业出版社
[5]余胜泉 《计算机算法分析》人民邮电出版社
[6]王晓东 《算法设计与分析》电子工业出版社
[7]汪琼 《计算机算法实例》机械工业出版社
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页