|
|||||
|
|
| 基于“DNA折纸术”设计图着色问题的解决方案 | |
| 摘 要： | 色数是图论中的一个重要的参数,其属于著名NP(Non-deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案. |
| 本文献已被 CNKI 等数据库收录！ | |