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