深度优先搜索（DFS）入门到进阶：回溯、剪枝、迭代加深

DFS 是最基础的搜索算法，但它的变化和应用非常丰富。

一、DFS 本质
DFS = 深度优先搜索 = 一条路走到黑，碰壁再回头。

void dfs(int u) {
    if (到达目标状态) { 处理答案; return; }
    for (每个可能的下一步 v) {
        if (v 合法且未访问) {
            标记 v 已访问;
            dfs(v);
            取消标记（回溯）;
        }
    }
}

1. 图/树的遍历：最基础的应用，前序/中序/后序遍历


2. 回溯算法：八皇后、全排列、子集枚举、组合


3. 记忆化搜索：用数组存储已计算状态，避免重复计算

• 可行性剪枝：当前分支不可能到达解，直接返回


• 最优性剪枝：当前分支不会比已有最优解更好，直接返回


• 顺序剪枝：改变搜索顺序，优先搜索更可能成功的分支


• 对称性剪枝：利用对称性减少搜索空间

• 设定深度限制 depth


• 如果未找到解，逐步增加深度限制


• 结合 A 启发式函数 → IDA 算法

• 八皇后：经典回溯


• 洛谷 P1706 全排列问题


• 洛谷 P1219 八皇后（加强版）


• 洛谷 P1120 小木棍（经典 IDDFS + 剪枝）