启发式搜索

“启发式的”（heuristic）和“找到了”（Eureka）在英文中有相同的词根：来自意为“寻找”或“发现”的希腊语。启发法得到了早期GOFAI学派的重视，并且经常被看作“编程技巧”。但是，这个术语并非源于编程：逻辑学家和数学家对其早已熟悉。早在数千年前，人类就用启发法解决问题（有意或无意地），远远早于埃达·洛夫莱斯伯爵夫人（Ada Love Lace's）预见人工智能的时间。

无论是对人还是对机器来说，启发法都有利于问题的解决。强人工智能使用启发法的模式是：让程序只针对搜索空间的某些部分，同时避开其他部分。

很多启发式算法都属于无法保证成功的经验法则，如早期人工智能使用的大多数经验法则。在启发法引导下，系统正好忽略了某部分的搜索空间，而解决方案可能正好位于这部分空间里。例如，在国际象棋中，“保护女王”是一条非常有用的规则，但偶尔也应该违背。

还有一些启发式算法从逻辑学角度或数学角度被证明是合理的。如今，人工智能和计算机科学领域的大量工作都是为了确定程序可证明的属性。这是“友好人工智能”的一个方面，因为人类安全可能由于使用从逻辑学角度看不是很可靠的系统而受到的威胁（详见第7章，启发式算法和算法之间原则上没有区别，许多算法实际上是包含多个特定启发式算法的微型程序）。

无论启发法可靠与否，它对人工智能搜索来说都不可或缺。上文提到人工智能越来越专业化，这部分取决于能显著提高效率的新启发法的定义，但仅限于限制颇多的某类问题或搜索空间。一个非常成功的启发法可能并不适合让其他人工智能程序“借用”。

如果我们给定几种启发法，那么应用它们的顺序就可能变得很重要。例如，即使这种排序偶尔会导致灾难，也应该先考虑“保护女王”，再考虑“保护象”。不同的顺序将定义不同的搜索树遍历整个搜索空间。给启发法下定义和排序是现代人工智能的关键任务（启发法在认知心理学中的地位也很突出，例如，“快速节俭启发式”指出进化如何让人获得对环境作出有效回应的方法）。

利用启发法，我们不再需要穷举搜索整个搜索空间，但它们有时会和（有限的）穷举搜索结合使用。1997年，因击败世界冠军加里·卡斯帕罗夫（Gary Kasparov）而名声大噪的IBM国际象棋程序深蓝（Deep Blue）使用的是专用硬件芯片，每秒能处理2亿个位置，可以知道接下来8步的所有备选棋步。但是，它不得不用启发法来选择备选棋步中的“最佳”棋步。由于启发法可信度不高，所以即使是深蓝，也不能每次都胜出。