免费看书

手机浏览器扫描二维码访问

第四十二章 DNA计算机（第2页）

艾达否听后，连忙竖起大拇指，“牛啤啊，你还知道多项式时间和约化？”

“切。”

卢赫得意地扬起下巴，“多大点事儿，当谁没编过程似的。不就是时间复杂度里的n出现在底数位置吗？非得给人重起个名叫多项式时间，故弄玄虚。”

“至于约化，不就是解决不了一个问题，就绕过它，去研究一个更复杂的问题，对其进行降维打击吗？举个例子，你脑子不好使死活解不出一元一次方程，灵机一动想出了个点子：

既然我解不出一元一次的，那我干脆去研究二元一次的。一旦我把二元一次的给解出来，那一元一次的就该像喝水一样简单了。”

“至于你说得什么NP完全问题，那不就是以多项式时间作为上限，无限去做约化。我解不出一元一次的，我就去解更复杂的二元一次；解不出二元一次，就去解更复杂的三元一次。

这样无限套娃下去，约化到一个无限复杂的问题，你拍着胸脯说：嘿，只要把这道题解出来，世界上所有问题就都难不倒我了！”

卢赫说完，右手搭在艾达否肩膀上，左手指着天空：“老艾啊，哥送你一句话：仰望星空，脚踏实地。左脚蹬右脚永远都上不了天。”

（）;（）　　艾达否听后不屑地笑了笑，“你可去拉倒吧，你个思想落伍的保守分子。DNA计算机是怎么工作的你知道吗？”

“怎么工作的啊？”

卢赫来了兴致。

艾达否一脸认真地娓娓道来：

“你知道哈密顿问题吗？图论里面的最著名难题。不知道也没关系，给你简单点描述一下：

假如你是一个时间管理大师，同时交往着5的女朋友，这些女朋友分布在5个不同的城市。有一天，你被老板派到另一个城市出差。好巧不巧，在那个城市你一个女朋友都没有，而你非常想念她们，想借着公费出差的机会，把这5个女朋友都见一遍。

由于经费有限，你又很抠门不想多掏机票钱，所以每个城市只能去一次。同时这些城市之间又不全部都有双向直飞航线，你该怎么做呢？

你可以想想，但我告诉你不论你怎么想都没用。因为这类问题的解法只有一个，那就是试！和我们暴力破解密码一样，一个一个试！

进一步的，如果你不只五个女朋友，而是有50个、500个、5万个、无穷个，你该怎么办？”

卢赫对着艾达否逐渐由认真转为嬉笑的脸，思索片刻，答道：“我觉得这个问题我不需要考虑。5个女朋友大眼一瞅在纸上画画也就出来了，如果再多，我肯定会先死在床上。”

“你个死变态。”

艾达否一脸嫌弃道：

“很难对吧？这其实是一个时间复杂度为n!的问题，也就是说，如果你有n个女朋友，就要尝试n的阶乘次。如果你女朋友多达万个，就算是拥有4万个核心天河三号，也要算到你年过花甲。

可这个问题对于DNA计算机来说，却是小菜一叠。它是这么算的：

假如你现在刚见完1号女朋友，准备奔赴到2号的怀抱。那么你离开1号女朋友的行为，就被编码为ACAC；奔赴2号女朋友的行为，被编码为GTGT。把这两串编码合起来，ACACGTGT就代表你从1号到2号的路径。

接下来，你见完了2号女朋友，又匆匆赶往3号。这个过程可以再用编码表示为TCTCAGAG。

也就是说，8个碱基就可以用来表示你和其中一个女朋友从见面到拜拜的全过程。这个时候你肯定就要问了，我要你规划一条连续的路径，可ACACGTGT、TCTCAGAG是分离的两条链，这还怎么能玩儿的下去？

很简单嘛，碱基对是可以互补的。你再找一条CACAAGAG，不就可以跟胶水一样，把那两条毫不相关的链给粘起来了吗？

接下来的事情就更简单了。你有几个女朋友，就用几串8位编码来表示和她们的见面和拜拜的过程。然后你把你的女朋友和胶水都合成一下，扩增个几万亿条，放在一起，养蛊。

根据碱基配对原则，胶水分分钟就能发挥作用，把各种女朋友给粘起来。这个时候，你会得到几万亿条路径。这就是路径遍历的所有结果。

那你又要问，我怎么把最省钱的那一条路径给筛选出来呢？

这也很简单，你的起点和终点是固定的。只要拿起点和终点作引物，扩增一下，起终点正确的路才能被扩增，不正确的会被逐渐稀释掉。至于有些路径上，你少见了几个女朋友，或者重复多见了几个女朋友，这些链的长度肯定是不对的。

最终，你把它们电泳一下，链长的和链短的分开，挑出长度刚好的链，测个序，答案不就出来了吗？”