一个糖果厂老板决定推出一个活动,将五张金券藏到巧克力的包装里,而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。 如何找到这些金券?你可以买尽可能多的巧克力。你可能会试试用磁铁,可惜金没有磁性。或者你可以雇用数千人,让他们每人筛查一小堆巧克力。这听起来很傻,但是小姑娘维露卡•索尔特就要这么做,因为她特别想得到一张金券,去参观威利•旺卡的巧克力工厂。 维露卡的父亲索尔特先生是个富商,他决定买光他能找到的巧克力。这还不够,就算有堆积如山的巧克力,要从中找到小小的金券也很困难。索尔特先生也有一家工厂,他不惜动用工厂的工人,终于找到了一张金券。他对记者讲述了找到金券的过程: 我是做花生生意的,知道吧,我有大约100个女工为我剥花生,然后将它们做成烤花生米和腌花生米。她们整天就坐在那儿剥花生。所以我跟她们说:“好了姑娘们,不要剥花生了,大家开始给我剥这些破糖纸吧!”然后她们就剥。我让工厂的每一个工人都铆足了劲地撕掉巧克力的包装纸,从早干到晚。 但是三天过去了,我们还是没走运。哦,那可真够呛!我可怜的小维露卡越来越暴躁,每次我一回家她就朝我嚷嚷:“我的金券在哪儿?我要我的金券!”她撒泼又打滚儿,踢腿又叫喊,实在招人烦。我可不希望看到我的小宝贝这么不高兴,所以我决定一直找,不找到她要的东西誓不罢休。终于,在第四天的晚上,一个女工大叫:“我找到金券了!”然后我说:“把它给我,快!”她给了我,然后我跑着回家把它交给了亲爱的维露卡,她高兴得合不拢嘴。我们家又变得其乐融融了。 和索尔特先生一样,无论你打算怎么找那张金券,你都需要大量时间、金钱,或者运气。也许有一天,有人能发明出一个快速找到金券的便宜装置,也许这样的装置并不存在。 然而,1000万对于今天的计算机来说只是很小的数字。如果你把糖果数字化,录入一个数据库,现在的电脑只用不到一秒就能把它找一遍。虽然计算机比人快得多,但它面对的问题的规模也比在糖果里找金券大得多。 现在最大的电子数据集合规模有多大?比如,整个互联网,考虑到所有视频、音频、电子邮件及其他一切,总的信息量差不多有1 000 000 000 000 000 000字节,最多相差几个0。一个字节大致对应键盘上的一个字符。这个数很大,但记住,计算机也很快。一般的笔记本电脑每秒可以执行1万亿次操作,这样算来,理论上只需要不到4个月就能搜完整个互联网的内容,前提是你能把整个互联网装到你电脑的内存里。Google每时每刻都在搜索整个互联网,它使用了几十万台快速的计算机。 如果计算机可以很快地搜遍整个互联网,看起来好像我们就解决了这个找金券问题的电子版。但是,计算机不仅要帮人们搜索已有的数据,还要搜索问题的所有可能解。 认识一下可怜的旅行推销员Mary,她来自华盛顿特区,为美国木槌集团公司工作。她需要从家乡旅行到48个州的首府,向各州法院推销木槌。木槌公司为了削减成本,让Mary找到通过所有城市的最短路径。Mary画了一张图,写写画画了一会儿,制订了一个不错的路线。 差旅部门的人想让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想知道有没有比穷举更好的方法找到最佳路线,就像在所有可能行程的“巧克力山”里面刨出那张小小的金券。 图1-1 旅行推销员问题的地图 这就是本书最基本的问题:P/NP问题。其中的一个实例就是能否为旅行推销员找到最短路径。P和NP自有其十分专业的定义,但是把它们看做概念比看做数学对象更好。NP是存在解的问题的集合,P则是能很快找到解的问题的集合。 意味着我们能总是很快地计算出任何问题的解,当然也包括找到旅行推销员的最短路径。相反, 意味着我们不能。 1.1 划分的难题 看下边38个数字: 14 175, 15 055, 16 616, 17 495, 18 072, 19 390, 19 731, 22 161, 23 320, 23 717, 26 343, 28 725, 29 127, 32 257, 40 020, 41 867, 43 155, 46 298, 56 734, 57 176, 58 306, 61 848, 65 825, 66 042, 68 634, 69 189, 72 936, 74 287, 74 537, 81 942, 82 027, 82 623, 82 802, 82 988, 90 467, 97 042, 97 507, 99 564 这38个数字之和为2 000 000。你能把它们平分成两组,每组19个数字之和分别为1 000 000吗?你可以使用计算器、电子表格或写一个计算机程序。(答案在本章最后。) 不那么简单,是吧?把这些数分成两组有170亿种方式。如果程序编得巧妙,使用当今较快的计算机能够找到一个解。但如果给你3800个数,或者3800万个数呢?短小的计算机程序可没法给出答案了! 这只是个无意义的数学谜题吗?就算存在一个厉害的计算机程序,它能解决这个平分数组的问题(假设有解),那又如何呢?如果是这样的话,我们能用这个程序做更多的事。这个程序能解决所有的问题,包括旅行推销员问题。这个简短的难题抓住了P/NP问题的本质:一个程序如果能解决这个难题的复杂版本,那么它也能解出任意问题。
可能与不可能的边界——1.1 划分的难题
书名: 可能与不可能的边界
作者: [美] Lance Fortnow
出版社: 人民邮电出版社
原作名: The golden ticket:P,NP,and the search for the impossible
副标题: P/NP问题趣史
译者: 杨 帆
出版年: 2014-1
页数: 160
定价: 39.00
装帧: 平装
ISBN: 9787115335661