深度优先搜索

深度优先搜索

深度优先搜索就是把OPEN表中的结点以搜索树中结点深度的递减顺序排列，深度最大的结点放在最前面，深度相同的结点可以任意排列。由于搜索树中深度最大的结点，总是首先被扩展，因此称为深度优先搜索。为了防止搜索过程沿着某条无益的的路径一直延伸下去，所以应提供一个深度限制，超过这个深度就不再继续往下扩展。深度优先方式与回溯方式相比，如果深度优先方式每次只扩展出一个结点的话，两种方式的对应关系就是精确的。但回溯方式实现起来比较简单，并且存储量比较小，因此‘回溯方式更为优越。

如果有启发式信息可以利用，例如用某一结点与目标结点的差异来计算该结点与目标结点的相似程度，就可以对OPEN表中的结点进行评价，并以此指导排序。利用问题启发方式信息，用爬山法的方式可以对深度优先搜索进行改进。方法是对OPEN表中深度最大的结点(可以有若干个)根据启发式信息排序，将与目标结点最接近的结点放在前面，这搜索效率可以得到提高。