你能组建一支合适的队伍吗?
这道问题的答案显然是“能”,你可以选择约翰、乔治和林戈,或者保罗、乔治和林戈(请注意,这是该问题仅有的两种解法)。
然后我们再加上一个限制:约翰和乔治不能一起工作。那么答案就明显了:保罗、乔治和林戈。
现在我们加上最后一个限制:保罗和乔治不能一起工作。
那么我们的答案就变为“不能”,因为没有一种组合可以同时满足三个“禁止组队”的要求。
我们用抽象的方式来描述这个问题[28] :
首先给出一个包含n个人的列表(在上述例子中,这些人就是约翰、保罗、乔治和林戈,因此n = 4),以及一个“禁止组队”的列表(例如,“约翰和保罗不能在一起工作”)。那么,我们能否得到一个包含m个人的团队,使得所有禁止组队的条件都能得到满足?(显然,要使得这个问题有意义,m必须小于n。)
必须指出的是,这个问题在原则上是很容易解决的。简单地列出所有含有m个成员的团队名单,并检查每一个团队名单是否与禁止组队列表有冲突即可。用计算机编程来做这个步骤非常容易。因此,在图灵的观念里,这个问题很容易求解。
那么,问题的关键来了,我们需要检查多少种组合的可能性呢?如果是4人团队里面选3人,那很容易,你需要检查4个有可能的选择。但当团队人数增多,会出现什么情况,我们来看看吧。
如果是10人团队选5人,你就得检测252种可能性。好吧,很枯燥,但是还能忍受。不过可以看到的是,选择可能性的增长速度远远大于整个团队成员或者目标团队成员的数量增长的速度。
如果是100人团队里面选50人,那你就得检测大约1029 这么多种可能性了。一台当代的大型计算机每秒可以评估大约1010 种可能性——听起来挺多的,但是,稍微计算一下你就能意识到,即便算到宇宙末日,也无法检测完毕。期待英特尔的工程师们提供计算速度更快的芯片也无济于事:传统计算机技术再怎么突飞猛进,也无法在合理的时间内完成这个数量级的计算任务。
我们在这里所看到的现象也是组合爆炸的例子。在研究搜索树的时候我介绍过组合爆炸的概念,搜索树中的每个层级都呈指数型增长。所以在层级增多的时候,组合爆炸会导致可能出现结果的增长速度超乎想象。在团队建设的案例中,只要团队总人数增加1个人,我们必须考虑的潜在组合型就会翻倍。
所以,这种彻底列举每一种组合可能性的方式,是不可行的。理论上它行得通(如果时间足够,总会得到正确的答案),但在实践中它毫无意义(因为对每种可能的组合做判断需要的时间是天文数字)。
正如我们之前提到过的,简单的穷尽式搜索是一项非常原始的技术。我们可以使用启发式方法来对它进行优化,但是并不保证一定有效。有没有一种更聪明的方法可以寻找到合适的组合,又不用彻底检查所有的备选方案?很遗憾,答案是没有。你会发现对搜索方式的优化可以改善一些东西,但是,最终你仍然无法绕过组合爆炸。在大多数情况下,能在理论上确保问题可以解决的方案,在实践中都会遇到这个问题。
因为我们的问题是一个NP完全问题 的案例[2] 。恐怕这个首字母缩写对不熟悉计算机编程的人而言太过陌生:“NP”代表“不确定多项式时间”,具体的技术定义相当复杂。幸运的是,NP完全问题背后的逻辑很简单。
组合问题是一个NP完全问题,就像我们团队建设的例子。
在这个问题中你很难找到解决方案(我们在上文讨论过,因为要彻底检查每一种组合需要耗费无尽的时间),但是又很容易验证是否找到了解决方案(在这个示例中,我们可以简单地验证它是否与禁止组队的规则相冲突)。
NP完全问题还有一个重要特征,为了理解它,我们要引入另一个问题(请相信我,这个真的很有必要),这个问题相当著名,你可能听说过它。它被称为旅行推销员问题[29] :
有一位推销员要去被道路连接的若干城市推销商品,走完所有城市以后他必须回到起点。并非所有城市都有公路直接相连接,而有公路连接的城市,推销员知道每条公路的具体长短。请问:推销员走遍所有的城市,最终回到起点,怎样选择一条最短的路径?
这个问题跟团队建设类似,都是组合类问题。我们可以用蛮力计算来解决它,只要列出所有可能的路线,并检查每条路线的长短,然后选择最短的一条即可。然而,正如你现在所想的那样,随着城市数量的增加,可能存在的行进路线会呈指数级增长:如果要走遍10座城市,就得考虑360多万种可能性,11座城市就会激增为4000万种。
所以,旅行推销员问题和团队建设问题一样,都会面临组合爆炸的难题。但除此之外,这两个问题似乎没什么共通之处,毕竟团队建设和寻找最短路径有什么关联呢?但是在NP完全问题的范畴内讨论的话,这两个问题,虽然看上去差别很大,但本质上是同一个问题。
我这句话的意思可以这么理解:假设我已经发明了一种巧妙的方法,可以保障高效又准确地找到团队建设问题的正确答案,现在你给我一个旅行推销员问题的案例,我就可以把这个旅行推销员问题转化为团队建设问题的一个特例,我的方法可以迅速解决它,你则可以得到想要的答案。这就意味着,如果你发明了一种可以高效又准确解决团队建设问题的方法,那么就等同于你发明了可以高效又准确解决旅行推销员问题的方法。这种神奇的方法并不仅仅适用于这两个问题,而是可以解决所有NP完全问题。
所有的NP完全问题都能共通,可以互相转换。这就意味着一个很明显的事实:要么所有NP完全问题存在通用的解,要么它们都无解。如果你能找到高效又准确解决某个NP完全问题的方法,就意味着你能够解决所有NP完全问题。但是,到目前为止,还没有任何人寻找到解决NP完全问题的高效准确的方法。事实上NP完全问题能否有效解决,是当今科学界最重要的开放性问题之一。这个问题被称为P与NP问题[30] ,如果你能证明这个问题是否有解,并且能让科学界认同,你将获得克雷数学研究所提供的100万美元奖金,正是该研究所于2000年将其确定为“千年问题”之一。精明的投资商认为NP完全问题不能得到有效解决,同样也是精明的投资商告诉我们,要确切知道这一点,还有很长的路得走。
如果你发现自己要解决的问题是NP完全问题,这就意味着传统意义上的计算机技术在解决该问题上是行不通的:从精准的数学意义来说,你的问题太难了。
NP完全问题的基本结构早在20世纪70年代就已成形。1971年美籍加拿大数学家斯蒂芬·库克(Stephen Cook)的一篇论文确定了NP完全问题的核心思想,随后美国人理查德·卡普(Richard Karp)证明了库克NP完全问题的范畴比最初想象的要广泛得多。整个20世纪70年代,人工智能领域的研究人员开始利用NP问题完全性理论来研究他们的课题,结果令人震惊。不管哪个领域——解决问题、玩游戏、计划、学习、推理任何方面——似乎关键性的问题都是NP完全问题(甚至更糟)。这种现象普遍得成了一个笑话——所谓的“AI完全问题”[3] 意味着“一个和AI本身一样难的问题”,如果你能解决一个AI完全问题,你就能解决所有AI问题了。
发现你正在研究的问题是NP完全问题——或者更糟——真是个沉重的打击,在NP完全性理论及其论证结果被理解之前,人们总是希望出现重大突破使得这些问题变得简单——用术语来说就是易处理。从技术上讲,这种希望还是存在的,因为我们还没有明确地证明NP完全问题不可解。但到了20世纪70年代,NP完全性理论和组合爆炸成为笼罩在人工智能领域的阴影,以计算复杂性的形式阻拦在人工智能发展道路上,使它陷入停滞。黄金年代发展起来的技术似乎都无法扩大它们的使用范围,走不出玩具或者特定小世界(比如积木世界)的范畴。50到60年代过于乐观的预测遇到了现实难题,这让人工智能领域的先驱者们无比困扰。
本书评论