吾尊百科网

美国DNA计算机解题能力创新高

美国科学家利用简单的DNA计算机,在实验中为一个有24个变量、100万种可能结果的数学难题找到了答案。这是迄今利用非电子化计算手段解出的最复杂数学问题,表明DNA计算机研制又迈出了重要一步。  美国南加利福尼亚大学教授阿德勒曼将这一研究成果发表在新一期美国《科学》杂志上。  DNA(脱氧核糖核酸)是生物遗传的物质基础,它通过4种核苷酸的排列组合存储生物遗传信息。将运算信息排列于DNA上,并通过特定DNA片段之间的相互作用来得出运算结果,是DNA计算机工作的主要原理。  阿德勒曼教授是DNA计算机研究领域的先驱。他于1994年在实验中演示,DNA计算机可以解决著名的“推销员问题”,首次论证了这种计算技术的可行性。“推销员问题”用数学语言来说,是要求在7个城市间寻找最短的路线,这一问题相对简单,心算就可以给出答案。  但这次阿德勒曼教授用DNA计算机演示新问题难度就大多了,靠人脑的计算能力基本无法处理。这一逻辑问题名叫“NP完全3-SAT问题”,听起来不知所云,但可以形象化地表述如下:  假设你走进一个有100万辆汽车的车行,想买一辆称心的车。你向销售员提出了一大堆条件,如“想买一辆4座和自动档的”,“敞蓬和天蓝色的”宝马车等等,加起来多达24项。在整个车行中,能满足你所有条件的车只有一辆。从理论上说,销售员必须一辆辆费劲地找。传统的电子计算机采用的就是这种串行计算的办法来求解。  阿德勒曼等设计的DNA计算机则对这一问题进行了并行处理。他们首先利用DNA片段编码了100万种可能的答案,然后将其逐一通过不同容器,每个容器都放入了代表24个限制条件之一的DNA。每通过一个容器,满足特定限制条件的DNA分子经反应后被留下,并进入下一个容器继续接受其它限制条件的检验,不满足的则被排除出去,  从解决这个问题的过程中可以看出,理论上,DNA计算机的运算策略和速度将优于传统的电子计算机。阿德勒曼教授说,虽然他们的新实验进一步提高了DNA计算机模型的运算能力,但总的来说,DNA计算机错误率还是太高;要真正超越电子计算机,还需要在DNA大分子操纵技术等方面有大的突破。