一、定义与核心思想

深度优先搜索（Depth-First Search, DFS） 是一种基于图或树结构的遍历算法，其核心思想是 "纵向深入探索"。算法从初始节点出发，沿着一条分支尽可能深入搜索，直到达到最深节点或满足终止条件，再回溯到上一个未完全探索的节点继续深入。在人工智能中，DFS常用于需要快速发现可行解或遍历所有可能状态的场景。

二、算法流程

1. 初始化：将起始节点压入栈，并标记为已访问。
2. 迭代遍历：
   • 从栈顶取出当前节点。
   • 若当前节点满足目标条件，终止搜索并返回结果。
   • 将所有未访问的相邻节点按特定顺序（如左到右）压入栈顶，并标记为已访问。
3. 终止：若栈为空仍未找到目标，判定为无解。

三、核心特性

性质	说明
数据结构	基于栈（LIFO）实现，优先深入探索分支
完备性	在有限状态空间中可能找到解（但无限深度时可能失败）
最优性	不保证找到最短路径
空间复杂度	最坏情况与最大深度线性相关，复杂度为O(b·d)（b为分支因子，d为深度）

对比宽度优先搜索（BFS）：

• DFS适合快速发现可行解，BFS保证最短路径。
• DFS空间效率更高，适合深度大的问题；BFS内存消耗更大。

四、典型应用

1. 状态空间穷举
   • 数独、八皇后等约束满足问题（CSP）的暴力破解
   • 组合优化问题的全解搜索
2. 路径探索
   • 迷宫生成与求解（允许非最短路径）
   • 游戏AI中的决策树遍历（如棋类游戏的走法预判）
3. 拓扑分析
   • 有向无环图（DAG）的拓扑排序
   • 强连通分量（SCC）的分解
4. 回溯算法基础
   • 自动推理中的假设验证
   • 编译器的语法分析（如递归下降解析）

五、优势与局限

优势：

• 内存消耗低，适合深度大、分支因子少的问题
• 快速发现可行解（尤其当解分布在深层时）
• 天然支持递归实现，代码简洁

局限性：

• 可能陷入无限深度循环（需设置最大深度限制）
• 无法保证解的最优性
• 搜索路径可能冗余（需结合剪枝策略）

六、算法变体

1. 迭代加深DFS（IDS）：逐层增加深度限制，结合DFS空间效率与BFS完备性
2. 双向DFS：从起点和终点同时展开深度搜索
3. 随机化DFS：随机选择相邻节点顺序，避免搜索偏向性
4. 记忆化DFS：存储中间状态减少重复计算（常用于动态规划问题）

七、总结

在人工智能领域，DFS常与启发式规则结合，例如在AlphaGo的蒙特卡洛树搜索（MCTS）中，通过受限深度探索快速评估棋局价值，或在自动化推理系统中结合剪枝策略提升效率。

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)