深度优先搜索总是优先扩展边界中最深的节点。它可以通过调用 Best-First-Search 来实现，其中评价函数 f 为深度的负数。然而，它通常不是以图搜索的形式实现而是以树状搜索(不维护已达状态表)的形式实现。搜索的过程如图3-11所示，搜索先之间到达搜索树的最深层，这里的节点不存在后继节点。然后，搜索将“回退”到下一个仍存在未扩展后续节点的最深节点。深度优先搜索不是代价最优的，它会返回它找到的第一个解，即使这个解不是路径代价最小的。
对于树型的有限状态空间，算法是有效且完备的。对于无环状态空间，算法可能会通过不同路径多次扩展同一状态，但是(最终)将系统地探索整个空间。
在有环状态空间中，深度优先搜索算法可能陷入无限循环；因此，一些深度优先搜索算法的实现会检查每个新节点是否存在循环。在无限状态空间中，深度优先搜索不是系统性的：即使没有循环，它也可能陷入无限路径。因此，深度优先搜索是不完备的。
那么，为什么还会有人选择使用深度优先搜索而不是广度优先搜索或最佳优先搜索呢？答案是，对于使用树状搜索可以处理的问题，深度优先搜索对内存的需求要小得多。深度优先搜索根本不保留 reached 表，并且边界集很小：如果将广度优先搜索中的边界集视为不断扩展的球体的表面，那么深度优先搜索中的边界集只是球体的半径。
由于其对内存的节约使用，深度优先树状搜索已经成为许多人工智能领域的基本工具。回溯搜索是深度优先搜索的一种变体，它使用的内存更少。在回溯搜索中，一次只生成一个后继，而不是所有后继节点；每个部分扩展的节点会记住下一个要生成的后继节点。
[1]
-
从明天起做一个快乐的agent工程师 ↩
