DFS之剪枝与优化——AcWing 165. 小猫爬山

DFS之剪枝与优化

定义

DFS之剪枝与优化指的是在执行深度优先搜索(DFS, Depth-First Search)时，采取的一系列策略来减少搜索空间，避免无效计算，从而加速找到问题的解。剪枝是指在搜索过程中，当遇到某些条件不符合解的要求或者可以预判后续搜索不会产生有效解时，直接放弃这条搜索路径，这一过程称为剪枝。优化则是指通过调整搜索策略、顺序等，提高搜索效率。

运用情况

组合优化问题：如全排列、组合总和、子集问题等，剪枝可以避免生成无效解。
图的遍历与搜索：在寻找特定路径或计算连通分量时，剪枝可以减少搜索范围。
游戏AI：如棋类游戏中预测对手可能的走法，剪枝减少计算量。
约束满足问题：如数独、任务调度等，剪枝帮助快速排除不满足条件的解。

注意事项

剪枝条件的选择：剪枝条件应严格且准确，避免误剪有效解。
搜索顺序：合理安排搜索顺序，优先探索最有希望的分支。
状态重置：回溯时确保正确恢复现场，避免状态污染。
记忆化：对于重复子问题，使用记忆化技术存储中间结果，避免重复计算。
资源管理：注意栈或递归深度限制，防止栈溢出。

解题思路

明确剪枝条件：分析问题特性，确定何时可以安全地剪枝。
优化搜索顺序：
- 分支较少优先：优先探索分支较少的路径，减少搜索深度。
- 启发式排序：依据某种评估函数排序待探索节点，优先探索最有潜力的节点。
可行性剪枝：在探索前，如果可以证明当前路径无法导致有效解，立即剪枝。
最优性剪枝：在某些最优化问题中，如果已知当前路径不能优于已找到的最佳解，剪枝。
迭代加深DFS：结合深度限制，逐步增加深度限制进行搜索，适用于寻找最短路径等问题。
记忆化搜索：在适用场景下，利用动态规划思想存储中间结果，避免重复计算。

AcWing 165. 小猫爬山

题目描述

165. 小猫爬山 - AcWing题库

运行代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k)
{
    if(k >= ans) return;
    if(u == n)
    {
        ans = k;
        return;
    }
    for(int i = 0; i < k; i ++ )
        if(sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u];
        }
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> w[i];
    sort(w, w + n, greater<int>());
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

代码思路

输入与初始化：读取小猫数量 n 和缆车最大承重 m，以及每只小猫的重量 w[]，并按重量从大到小排序。
DFS搜索：定义一个深度优先搜索函数 dfs(u, k)，其中 u 是当前考虑的小猫索引，k 是当前已经考虑过的缆车数量。
- 当搜索到的缆车数量 k 大于或等于已知的最小缆车数量 ans 时，提前结束此分支的搜索。
- 当所有小猫都被考虑过后，更新最小缆车数量 ans。
- 对于每辆缆车，尝试将当前小猫放入（如果总重不超过 m），递归搜索下一个位置的小猫。递归结束后回溯，撤销选择。
主函数逻辑：初始化数组 sum[] 用于记录每辆缆车的当前载重，然后调用 dfs() 函数，最后输出最小缆车数量 ans。

其它代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k)
{
    if(k >= ans) return;
    if(u == n)
    {
        ans = k;
        return;
    }
    for(int i = 0; i < k; i ++ )
        if(sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u];
        }
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> w[i];
    //sort(w, w + n, greater<int>());
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

代码思路

变量定义:
- n: 表示小猫的数量。
- m: 表示每辆缆车的最大承重。
- w[N]: 存储每只小猫的重量。
- sum[N]: 记录每辆缆车当前的总重量。
- ans: 初始设置为一个较大的数（N），用于记录最少需要的缆车数量，最终会被更新为实际的最小数量。
主函数逻辑:
- 读取小猫数量 n 和缆车最大承重 m。
- 输入每只小猫的重量 w[]。注意代码中去掉了原先对w[]进行排序的部分，这在原始代码中是为了优化搜索过程，因为通常按照重量从大到小处理可以更快达到最优解，但这里为了保持原始逻辑解释，未进行排序。
- 调用深度优先搜索函数 dfs(u, k) 进行求解，其中 u 表示当前考虑的小猫索引（从0开始），k 表示当前已经分配的缆车数量。
- 输出最少缆车数量 ans。
深度优先搜索 (DFS) 函数逻辑:
- 剪枝条件: 当已分配的缆车数量 k 大于等于已知的最小缆车数量 ans 时，直接返回，因为后续的搜索不会得到更好的解。
- 终止条件: 当所有小猫都被考虑过（即 u == n）时，更新 ans 为当前的缆车数量 k，然后返回。
- 尝试分配小猫到已有缆车:
  - 遍历之前的所有缆车（用 i 表示），检查当前小猫是否能加入到缆车 i 中（即 sum[i] + w[u] <= m）。
    - 如果可以加入，就临时增加 sum[i] 的值，然后递归调用 dfs 函数尝试分配下一个猫，分配完后再恢复 sum[i] 的值（回溯）。
- 尝试分配到新缆车:
  - 将当前小猫分配到一个新的缆车（即 sum[k] = w[u]），然后递归调用 dfs 函数分配下一个猫，分配完后清空 sum[k]（因为这是尝试过程中的状态，不是最终分配）。