天才一秒记住【久久文学】地址：https://www.jjwxx.com
在这个问题中你很难找到解决方案（我们在上文讨论过，因为要彻底检查每一种组合需要耗费无尽的时间），但是又很容易验证是否找到了解决方案（在这个示例中，我们可以简单地验证它是否与禁止组队的规则相冲突）。
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年写道：
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！