天才一秒记住【久久文学】地址：https://www.jjwxx.com
在实践中，要考虑比简单的启发式算法更复杂的情况：因为跳棋是一种对抗游戏，你必须考虑到对手可能如何行动。
塞缪尔的跳棋程序会认为你的对手会做出对你最不利的举动。
这种“最坏情况推理”
的方法（即假设对手的行为会使得自己的得分最大化，让你的得分最小化）称为极大极小值搜索，是对抗性游戏的基本概念。
大部分早期的启发式搜索算法，包括塞缪尔的程序，都使用了某种特别的启发方式——“尝试—实践—判断”
。
20世纪60年代末，美国SRI人工智能研究中心的尼尔斯·尼尔森（NilsNilsson）和他的同事取得了突破，他们开发出名为A*的技术，作为我们之前讨论过的SHAKEY项目的一部分。
A*定义了一些简单的规则，让我们可以确定哪些启发是“有益的”
。
在A*之前，启发式搜索不过是一个猜谜游戏；而在A*之后，它是一个数学上很容易理解的过程[27]。
A*现在被视为计算机科学中的基础算法之一，并且在实践中得到了广泛的应用。
其实，我们在生活中经常会遇见使用A*算法的程序，比如车载卫星导航系统等。
尽管A*很惊艳，但它仍然依赖于使用特定的启发式搜索：好的启发能很快地找到解决方案，而差的启发就没什么价值。
对如何为特定问题找到更优秀的启发，A*本身并没有给出答案。
人工智能遇上了复杂性障碍
我们在上一章讲过，计算机的出现源自艾伦·图灵想解决一个彼时数学界的世纪难题。
图灵发明计算机可能算是计算机科学史上最大的讽刺之一，因为他的本意是证明有些事情计算机永远也办不到。
在图灵的研究成果问世后的几十年里，探索计算机能做和不能做的事情的范围形成世界各地数学系的小分支的研究方向。
这项工作的重点在于把那些固有的不可判定问题（无法用计算机解决的问题）和可判定问题（能够用计算机解决的问题）区分开来。
从那时起，人们发现了十分有意思的现象——不可判定的问题存在层次结构：即存在某些问题，不仅不可判定，还是高阶不可判定的（这对某些研究特定领域的数学家而言很棘手）。
不过在20世纪60年代，确定一个问题是否可判定，还远远不够。
一个问题在图灵看来是可以解决的，并不意味着它在实际操作上是可以实现的：图灵只是从理论上证实某些问题有解，但是有些问题的解决方式需要消耗庞大的计算资源——需要动用的计算机内存大到不可估量，或者计算机的运行速度慢得出奇，能计算出结果的时间遥遥无期。
很明显，许多人工智能问题陷入了这样尴尬的境地。
下面就是一个例子，按照图灵的理论，很容易证明它能被解决：
你能组建一支合适的队伍吗？
这道问题的答案显然是“能”
，你可以选择约翰、乔治和林戈，或者保罗、乔治和林戈（请注意，这是该问题仅有的两种解法）。
然后我们再加上一个限制：约翰和乔治不能一起工作。
那么答案就明显了：保罗、乔治和林戈。
现在我们加上最后一个限制：保罗和乔治不能一起工作。
那么我们的答案就变为“不能”
，因为没有一种组合可以同时满足三个“禁止组队”
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！