第二部分 我们是怎么走到这一步的 第二章 黄金年代（第4页）

不过在20世纪60年代，确定一个问题是否可判定，还远远不够。一个问题在图灵看来是可以解决的，并不意味着它在实际操作上是可以实现的：图灵只是从理论上证实某些问题有解，但是有些问题的解决方式需要消耗庞大的计算资源——需要动用的计算机内存大到不可估量，或者计算机的运行速度慢得出奇，能计算出结果的时间遥遥无期。很明显，许多人工智能问题陷入了这样尴尬的境地。

下面就是一个例子，按照图灵的理论，很容易证明它能被解决：

你能组建一支合适的队伍吗？

这道问题的答案显然是“能”，你可以选择约翰、乔治和林戈，或者保罗、乔治和林戈（请注意，这是该问题仅有的两种解法）。

然后我们再加上一个限制：约翰和乔治不能一起工作。那么答案就明显了：保罗、乔治和林戈。

现在我们加上最后一个限制：保罗和乔治不能一起工作。那么我们的答案就变为“不能”，因为没有一种组合可以同时满足三个“禁止组队”的要求。

我们用抽象的方式来描述这个问题[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完全问题的基本结构早在20世纪70年代就已成形。1971年美籍加拿大数学家斯蒂芬·库克（StephenCook）的一篇论文确定了NP完全问题的核心思想，随后美国人理查德·卡普（RichardKarp）证明了库克NP完全问题的范畴比最初想象的要广泛得多。整个20世纪70年代，人工智能领域的研究人员开始利用NP问题完全性理论来研究他们的课题，结果令人震惊。不管哪个领域——解决问题、玩游戏、计划、学习、推理任何方面——似乎关键性的问题都是NP完全问题（甚至更糟）。这种现象普遍得成了一个笑话——所谓的“AI完全问题”[3]意味着“一个和AI本身一样难的问题”，如果你能解决一个AI完全问题，你就能解决所有AI问题了。

发现你正在研究的问题是NP完全问题——或者更糟——真是个沉重的打击，在NP完全性理论及其论证结果被理解之前，人们总是希望出现重大突破使得这些问题变得简单——用术语来说就是易处理。从技术上讲，这种希望还是存在的，因为我们还没有明确地证明NP完全问题不可解。但到了20世纪70年代，NP完全性理论和组合爆炸成为笼罩在人工智能领域的阴影，以计算复杂性的形式阻拦在人工智能发展道路上，使它陷入停滞。黄金年代发展起来的技术似乎都无法扩大它们的使用范围，走不出玩具或者特定小世界（比如积木世界）的范畴。50到60年代过于乐观的预测遇到了现实难题，这让人工智能领域的先驱者们无比困扰。

人工智能等于炼金术？

20世纪70年代初，人工智能的瓶颈让科学界越来越沮丧，没有太多有用的核心研究进展，而某些研究人员又大肆鼓吹人工智能的未来，于是，到了70年代中期，批评人工智能的风潮达到狂热的程度。

虽然我们不赞成德莱弗斯批判人工智能的方式，但很难回避这个现实：他的某些观点是有道理的，特别是关于人工智能先驱者们浮夸的观点和宏伟的预测。赫伯特·西蒙（后来获得了诺贝尔经济学奖）在1958年写道：

这并非耸人听闻，但是……现在世界上出现了能够思考、学习和创造的机器。在可以预见的未来，它们的能力将迅速增强，能够处理的问题范围将迅速扩大到人类思维的范围。

在当时，这样的说法很多，我引用西蒙的观点是因为他最有名气。虽然西蒙是人工智能乐观主义者，但他绝不是最狂热和不讲理的倡导者。令人痛心的是，事后看来，他的乐观预测是不切实际的。时至今日，人工智能界的一些成员认为，当时的研究人员之所以做出这样的乐观声明仅仅是因为他们被兴奋冲昏了头脑——也有人持更为愤世嫉俗的观点，称这种大肆炒作的目的是吸引投资和研究基金。

不管怎么说，我的专业敏感性让我必须声明一下，虽然当年的研究人员乐观得近乎天真，但并没有出现大规模蓄意欺骗或者歪曲人工智能研究状态的事情。研究人员之所以乐观过头，是因为他们热爱这门学科，并且真的相信——也希望其他人相信——他们确确实实建立了可以学习、计划和推理的程序，尽管有诸多局限性。他们只是乐观地认为，扩大这些程序的应用范围应该很容易。

所以，我认为某些乐观过头的情绪是可以被谅解的。尤其是，当年的研究人员没有意识到正在研究的问题本质上是计算机无法处理的，因而总存在出现突破性进展，使得问题迎刃而解的可能性。但当NP完全问题无解的概念开始普及以后，社会各界才慢慢明白，人工智能所面临的问题有多艰难。

黄金年代的终结

1972年，英国一个重要的科研资助机构要求著名数学家詹姆斯·莱特希尔（JamesLighthill）爵士评估人工智能的现状和前景。据说因当年世界最先进的人工智能研究中心之一（如今也是）——爱丁堡大学人工智能社区出现学术斗争的相关报道，所以才要求做这样的评估。莱特希尔荣列当年剑桥大学卢卡斯数学教授席位，这是英国数学家所能担任的最负盛名的学术职务，斯蒂芬·霍金（StephenHawking）后来也曾担任过。莱特希尔在实际应用数学方面有着丰富经验，时至今日，重读莱特希尔报告，可以看出他为当年人工智能的繁荣感到相当迷惑：

莱特希尔在报告中对当时的主流人工智能相当不屑一顾，他明确指出组合爆炸是人工智能领域无法解决的关键问题之一。他的报告立刻导致英国各地对人工智能研究经费的严重削减。

在美国，人工智能研究的资金大多来自军方，以国防高级研究计划局（DARPA）及其前身高级研究计划局（ARPA）为主。但到了20世纪70年代初，因为未能兑现诸多乐观的承诺，美国对人工智能研究的资助也随之削减。

20世纪70年代初到80年代初这10年被称为人工智能寒冬，更确切地说应该是人工智能的第一个寒冬，因为此后还有类似事件发生。人们得出了一个普遍结论，人工智能研究人员对这一领域充满了盲目乐观和毫无根据的预测，结果什么都没有。当时人工智能的名声就像医学界的顺势疗法[4]，作为一门严肃的学科，它似乎正在走向衰落。