在人工智能发展初期,组合爆炸被认为是根本性问题,麦卡锡将其确定为1956年人工智能暑期学校的重要研究课题之一。人们的关注点主要集中在提高搜索效率上,对此,有几种不同的解决方案。
一种是以某种方式集中搜索。其中一种典型的方式是并非逐级建立完整的搜索树,而是沿着其中一个分支构建搜索树。这种方式被称为深度优先搜索。通过深度优先搜索,我们沿着一个分支往下扩展,直到得到解决方案或者确信无法得到解决方案。如果遇到困难(比如类似图4中最左边的分支,又回到一个已经出现过的状态),那么我们就停止在该分支上的扩展,返回到上一级,选择另外的分支。
深度搜索的主要优点在于不用存储整个搜索树,只需要存储当前正在处理的分支即可。但它有一个很大的缺陷:如果选择了错误的分支进行探索,可能会在错误的路上越走越远,永远找不到解决方案。所以,要想使用深度优先搜索,首先我们得确认哪个分支最值得搜索。这时候,我们就需要启发式搜索来帮忙了。
启发式搜索的概念就是使用所谓的“经验法则”来指导搜索的重点。通常我们也无法寻找到直指正确搜索路径的启发式方法,但我们往往可以在感兴趣的问题上找到启发式搜索方向。当然,我们也明白,有些情况下,启发式搜索的运行情况并不那么尽如人意。