第1章 金券

一个糖果厂老板决定推出一个活动,将五张金券藏到巧克力的包装里,而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。

如何找到这些金券?你可以买尽可能多的巧克力。你可能会试试用磁铁,可惜金没有磁性。或者你可以雇用数千人,让他们每人筛查一小堆巧克力。这听起来很傻,但是小姑娘维露卡·索尔特就要这么做,因为她特别想得到一张金券,去参观威利·旺卡的巧克力工厂。

维露卡的父亲索尔特先生是个富商,他决定买光他能找到的巧克力。这还不够,就算有堆积如山的巧克力,要从中找到小小的金券也很困难。索尔特先生也有一家工厂,他不惜动用工厂的工人,终于找到了一张金券。他对记者讲述了找到金券的过程:

我是做花生生意的,知道吧,我有大约100个女工为我剥花生,然后将它们做成烤花生米和腌花生米。她们整天就坐在那儿剥花生。所以我跟她们说:“好了姑娘们,不要剥花生了,大家开始给我剥这些破糖纸吧!”然后她们就剥。我让工厂的每一个工人都铆足了劲地撕掉巧克力的包装纸,从早干到晚。

但是三天过去了,我们还是没走运。哦,那可真够呛!我可怜的小维露卡越来越暴躁,每次我一回家她就朝我嚷嚷:“我的金券在哪儿?我要我的金券!”她撒泼又打滚儿,踢腿又叫喊,实在招人烦。我可不希望看到我的小宝贝这么不高兴,所以我决定一直找,不找到她要的东西誓不罢休。终于,在第四天的晚上,一个女工大叫:“我找到金券了!”然后我说:“把它给我,快!”她给了我,然后我跑着回家把它交给了亲爱的维露卡,她高兴得合不拢嘴。我们家又变得其乐融融了。

和索尔特先生一样,无论你打算怎么找那张金券,你都需要大量时间、金钱,或者运气。也许有一天,有人能发明出一个快速找到金券的便宜装置,也许这样的装置并不存在。

然而,1000万对于今天的计算机来说只是很小的数字。如果你把糖果数字化,录入一个数据库,现在的电脑只用不到一秒就能把它找一遍。虽然计算机比人快得多,但它面对的问题的规模也比在糖果里找金券大得多。

现在最大的电子数据集合规模有多大?比如,整个互联网,考虑到所有视频、音频、电子邮件及其他一切,总的信息量差不多有1 000 000 000 000 000 000字节,最多相差几个0。一个字节大致对应键盘上的一个字符。这个数很大,但记住,计算机也很快。一般的笔记本电脑每秒可以执行1万亿次操作,这样算来,理论上只需要不到4个月就能搜完整个互联网的内容,前提是你能把整个互联网装到你电脑的内存里。Google每时每刻都在搜索整个互联网,它使用了几十万台快速的计算机。

如果计算机可以很快地搜遍整个互联网,看起来好像我们就解决了这个找金券问题的电子版。但是,计算机不仅要帮人们搜索已有的数据,还要搜索问题的所有可能解。

认识一下可怜的旅行推销员Mary,她来自华盛顿特区,为美国木槌集团公司工作。她需要从家乡旅行到48个州的首府,向各州法院推销木槌。木槌公司为了削减成本,让Mary找到通过所有城市的最短路径。Mary画了一张图,写写画画了一会儿,制订了一个不错的路线。

enter image description here

图1-1 旅行推销员问题的地图

1 1英里约合1.609千米。——编者注

差旅部门的人想让Mary试试能否找到另一条路线,把路程缩短到11 000英里以下。Mary写了个计算机程序,试图穷举所有可能的路线,找出最短的一条,但是一周以后,程序还没跑完。Mary坐下来开始算数。作为第一站的城市有48种选择,然后从剩下的47个城市中选一个作为第二站,再从剩下的46个城市中选一个,以此类推。可能的路径共有48×47×46×…×2×1种,也就是下面这个62位数:

12 413 915 592 536 072 670 862 289 047 373 375 038 521 486 354 677 760 000 000 000

即使计算机计算一条路线的时间等于光通过最小的原子直径的时间(大约0.000 000 000 000 000 000 33秒),仍然需要十亿亿亿倍于宇宙年龄的时间才能算完。难怪Mary的电脑算了一周还没有完。Mary想知道有没有比穷举更好的方法找到最佳路线,就像在所有可能行程的“巧克力山”里面刨出那张小小的金券。

这就是本书最基本的问题:P/NP问题。其中的一个实例就是能否为旅行推销员找到最短路径。P和NP自有其十分专业的定义,但是把它们看做概念比看做数学对象更好。NP是存在解的问题的集合,P则是能很快找到解的问题的集合。P=NP意味着我们能总是很快地计算出任何问题的解,当然也包括找到旅行推销员的最短路径。相反,P≠NP意味着我们不能。

目录