地图着色问题算法分析 第2页
算法介绍
D N A 计算
人们一直在追求一种速度更快、体积更小的计算机。1 9 5 6 年， 理查德• 冯纽曼就曾经充满幻想的描述了构建一台“ 亚显微”计算机的可能性。目前，尽管计算机在不断提高速度、 容量和性能上已经取得了巨大的进步， 尽管摩尔定律正在走向极限，但“ 亚显微”计算机的目 标还没有实现。
1 9 9 4 年，美国南加州大学的L e o n a r d M. A d l e m a n 在美国著名杂志S c i e n c e 上发表了一篇划时代的论文，用人眼看不到的D N A分子来做计算解决了一个N P难题一有向哈密顿路径问题，借助生化实验向冯纽曼的理想迈出了开创性的一步， 从而开创了一个非标准计算研究的新领域。 它使人们对计算的本质产生了新的理解和认识。
D N A 计算解决问题的基本思想是: 利用D N A 特殊的双螺旋结构和碱基互补配对原则对问题进行编码，把要运算的对象映射成D N A分子链，在D N A溶液的试管里，在生物酶的作用下，生成各种数据库，然后按照一定的规则将原始问题的数据运算高度并行地映射成 D N A分子链的可控的生化过程。最后，利用分子生物技术破获运算结果
D N A 计算的核心问题是将经过编码后的D N A 链作为输入， 在试管内经过一定时间的生物化学反应来完成运算，使得从反应后的产物及溶液中能得到全部的解空间。
D N A 计算在本质上属于生化反应， 为了利用D N A分子完成给定的任务， 我们必须借助对D N A分子的各种操作技术。对D N A分子的操作，既有物理的，也有化学的。物理操作实质上是调控生化反应的外部条件，例如温度，酸碱度等等。
此外是来自各种生化实验手段，尤其是通过各种酶的操作。经常用到的操作有以下几种：
( 1 )合成:使游离的碱基形成寡核昔酸的过程。
( 2 )混合:把两个试管中的溶液混合。
( 3 )链接:两条带有粘头( 也就是没有完全配对的双链) 的D N A双链在连接酶的作用下， 按W a s t o n - C r i c k 互补配对原则且将缝隙修补好， 从而连接在一起的过程。
( 4 )剪切:利用特定的限制性内 切酶，在D N A 双链的某个位置切断形成带有粘头的两条链的过程。
( 5 )退火和溶解:这是两个完全相反的过程，退火是指两条互补的D N A单链在温度逐渐降低的条件下， 合成一条双链的过程; 溶解是一条D N A双链在温度升
高时，分解为两条互补的单链的过程。
( 6 )放大:利用P C R技术，游离的碱基与作为模板的链配对连接形成双链，然后解成单链，继续这样的过程，于是目标链会以2的指数级增长。
( 7 )提取:将含有特定D N A短链的分子提出来，这要通过将特定短链的互补链吸附在小磁珠上，然后用磁铁将小磁珠吸出来的过程。
( 8 )延长:这一过程需要一条已知单链模板和一条已存在的、并已与模板的一小段匹配的引物D N A 序列， 要延长的D N A 序列根据模板给出的序列结构， 在聚合酶的作用下由5 端到3 端的方向不断延伸。
( 9 )缩短:通过外切核酸酶从D N A 分子的末端去掉一个核昔酸而缩短D N A分子。
( 1 0 )分离: 将D N A 分子置于一有凝胶的电场中，由 于D N A 分子带负电， 在电场中会向正极移动， 长度大的分子链受到凝胶的阻力大， 移动速度慢， 因此可用此技术去获取一定长度的D N A 分子链， 也可区分不同长度的D N A 分子。
D N A 计算之所以具有吸引力，是因为它具有如下三方面的显著特点：
( 1 ) D N A 计算具有高度的并行性，运算速度快。在A d l e m a n的实验中，通过适当估计， D N A串的并行操作数目可达1 0 ， 许多 研究者认为， 用当 前 技术到 1 0 2 0 个 串 的 并 行 操 作 是 可以 达 到 的 ， A d l e m a 。 认 为 这 个 数 字 可 以 达 到l O n u 6
( 2 ) D N A 作为信息的载体其贮存的容量非常之大，1 立方米的D N A 溶液可存储1 万亿亿的二进制数据，远远超过目 前所有电子计算机的总储存量;
( 3 ) D N A计算所消耗的能量只有一台电子计算机完成同样计算所消耗的能量的十亿分之一。
D N A 计算的上述特性， 即运算的高度并行性、 大容量、 低能耗是目 前的计算机和并行计算机所无法比拟和替代的，从这个意义上说，1 9 9 4 年由A d l e m a 。 所开创的分子生物计算技术具有划时代的意义， 正因为如此， D N A 计算机成为人们所追求的目标。
三、地图的着色
预备知识
令G 是 一 个 图 ， V ( G ) 、 E ( G ) 分 别 代 表G 的 所 有 点 和 所 有 边 的 集 合， 其 中V ( G ) 、E ( G ) 是 有 限 集 ， 任 何 一 条 边 和 两 个 顶 点 相 连 接 。 d o ( v ) 代 表 G 中 一 个 点 的度数。
如 果以V ( G )是平面上的点集，G中每一条具有端点的边是平 面 上 一 段以为 末 端的 弧 线， 它 与V ( G )中其它点不相 交 ， 且 任 何 两 条 不 同 的 边 不 可能 交于一个不是它们顶点的点，则称图G是可平面的。 平面上的图G 有一个无限区，它的意义在于欧拉公式的应用，因为欧拉公式是用在平面或球面上的。 对于一个可 平 面图 ， 其 欧 拉 公 式 为P 一 q + r = 2 ， 其中p , q , r 分 别 是 点 、 边 和区 的 个 数 。
在图论中，任何区是三角区的图称为一个三剖分。 e 是三角区; 的三条边，则称e 与三角区r 相关联。
设G 是 一 个 三剖 分， 令。 : E ( G ) - ) { - 1 , 0 , 1 ) 是 一 个映 射，e , f , g 分 别 与 三角 区 相 关 联 ， 若{ , D ( e ) , I D ( f ) , 4 ) ( g ) } 一 { - 1 , 0 , 1 } ， 则 称 ; 被 三 着 色 。 若 G 的 任 何 一 个三角区都被三着色，则称这个三剖分被三着色。①称为G的一个三着色。
令k : V ( G ) 一 { { 1 , 2 , 3 , 4 } 是 另 一 个 映 射， 对 于G 的 任 何 一 条 边 ， 如 果 它 与 点相 关 联， 有k ( u ) * k ( v ) ， 则 我 们 称G 被四 着 色。k 称为G 的 一个四 着色。
对于每一个地图， 我们可以把每一个区〔 区域或国家) 看作一个点， 而区与区之间的邻接关系看作点与点之间的连线， 因此得到一个点线图。 这不是一个三剖分。 但是通过适当加一些边它可以成为一个三剖分。很明显， 如果加边以后的三剖分有一
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页
地图着色问题算法分析 第2页下载如图片无法显示或论文不完整，请联系qq752018766
