毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

地图着色问题算法分析 第5页

更新时间:2009-7-1:  来源:毕业论文
地图着色问题算法分析 第5页
[ 3 ] : F a l s e F a l s e       3 4 4 4 5         T r u e T r u e
[ 4 ] : F a l s e F a l s e       4 5 5 5 6         T r u c T r u e
[ 5 1 : F a l s e F a l s e       5 6 6 6 7         T r u e T r u e
[ 6 ] : F a l s e F a l s e       6 7 7 7 8         T r u c T r u e
[ 7 ] : F a l s e F a l s e       7 8 8 8 9         T r u e T r u e
[ 8 ] : F a l s e F a l s e         8 9 9 9 1 9     T r u e T r u e
[ 9 ] : F a l s e T r u e       1 9 2 0 1 9 9 1 9     T r u e F a l s e
[ 1 0 ] : F a l s e T r u e      1 8 2 0 2 0 1 9 2 0  T r u e F a l s e
[ I 1 ] : F a l s e T r u e       1 7 1 8 1 8 1 8 2 0   T r u e F a l s e 
[ 1 2 ] : F a l s e T r u e    1 6 1 7 1 7 1 7 1 8   T r u e F a l s e
[ 1 3 ] : F a l s e T r u e       1 5 1 6 1 6 1 6 1 7   T r u e F a l s e 
[ 1 4 ] : F a l s e T r u e    1 0 1 5 1 5 1 5 1 6   T r u e F a l s e
[ 1 5 ] : F a l s e T r u e       1 0 1 1 1 0 1 0 1 5   T r u e F a l s e
[ 1 6 ] : T r u e T r u e       0 1 1 1 1 1 0 1 1     T r u e F a l s e
 
     在程序中,我们输出了每一个脉组对应的边的三着色。只考虑1 ,- 1 着色,
     上面( 1 )中“ } 」 I ”号前或后任一部分和( 2 )中“ 日I ” 号前或后任一部分
都可以组成一种着色,不在 ( 1 ) ,  ( 2 )中的边着色为0 。共有四种组合方式。我们分别取前一部分,可以得到表6 - 1 的着色方案。
 
根据前面的对应方法我们将其转换为顶点的一个
四着色,如表所示,着色如图所示
 

五、总结
     地图的着色问题是很著名的图论问题,它是一个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] 下一页

地图着色问题算法分析 第5页下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。