复杂性屏障

一秒记住【xiaoyanwenxue】精彩无弹窗免费！

“企鹅科普（第一辑）（.shg.tw）”

！

复杂性屏障

早期的人工智能系统展现出的“智能表现”

给了人们希望，所有人都以为人工智能会在更高级的问题上继续迅速发展，可惜希望最终落空。

诸如积木世界这种在微型世界场景中看似前景不错的技术，无法扩展到能解决现实世界的问题。

“计算复杂性”

（putationalplexity）是一种关于计算机解决问题的数学理论，该理论解释了为什么会出现这样的挫折。

在20世纪70年代早期，斯蒂芬·库克（StephenCook）、莱昂纳德·莱维（LeonidLevin）和理查德·卡普（RichardKarp）发现了一类计算问题，现称“NP完全问题”

（NP-plete，全称“非确定性多项式算法的完全问题”

）。

对于有些问题来说，计算机能迅速检验出答案正确与否，但想要计算机自己找到正确的答案则需要耗费大量时间。

“旅行推销员问题”

（TravellingSalesmanProblem）就是一个著名的例子：

一个推销员必须开车参观一些城市，最后返回出发地，车的汽油有限。

是否存在一条路径，可以使得推销员在不再加油的前提下完成这趟旅行？

解决NP完全问题最好的方式是穷尽所有可能的解决方案。

若推销员需要参观70个城市，所需要考虑的所有路线数目将会是个天文数字。

无论计算机的运算速度多么快，用这种穷举的方法来解决NP完全问题显然不可行。

很不幸，对于人工智能研究人员来说，似乎他们感兴趣的每个问题到头来都被证明是NP完全问题（或者更糟）。

人工智能从此从黄金时代走向停滞。

本章未完，点击下一页继续阅读