搜索的剪枝优化 - NOI提高级教程

📖 算法原理：可行性边界与最优性淘汰

深度优先搜索 (DFS) 会沿决策树一路向下，直到叶子。如果状态树极深，盲目暴力遍历会导致时间复杂度爆炸。剪枝 (Pruning) 指在搜索过程中，根据已知信息提前判断并回溯。

📐 核心剪枝策略

1. 可行性剪枝 (Feasibility Pruning)：
在搜索当前分支时，一旦发现当前状态已经不合法/越界（例如：背包已超重、累计价值为负、棋盘冲突等），则立即回溯返回，不再向下探索。
2. 最优性剪枝 (Optimality Pruning)：
维护一个全局最优解 best_val。在搜索当前分支时，若当前已花代价已经大于或等于 best_val（即便后面全是免费的，也不可能比 best_val 更好），则立即回溯剪枝！
3. 搜索顺序剪枝 (Search Order)：
优先搜索分叉少或代价极端的节点（例如从大到小放入物品），可尽早发现一个极佳的全局解 best_val，从而大幅度触发后续的最优性剪枝。

优化模式：

演示速度：

选择模式并点击"开始演示"观察 DFS 决策路径，以及红色/橙色剪刀切断 subtrees 的生动画面。

🌲 DFS 搜索空间剪枝树 (Scissor Pruning Overlay Visualizer)

已扫描节点：0 / 15

可行性截断：0

最优性剪枝：0

int best_ans = INF;

void dfs(int u, int cost) {
    // 1. 可行性剪枝 (越界判断)
    if (cost > LIMIT) {
        return; 
    }
    // 2. 最优性剪枝 (劣于当前全局最优解)
    if (cost >= best_ans) {
        return; 
    }
    
    if (u == target) {
        best_ans = min(best_ans, cost); // 更新全局最优
        return;
    }
    
    for (int v : adj[u]) {
        dfs(v, cost + val[v]);
    }
}

📋 DFS 深度探索步骤日志