小猫爬山算法详解

概述

“小猫爬山”是一个经典的算法问题，常用于教授深度优先搜索（DFS）及其剪枝优化技巧。问题描述如下：有 N 只小猫需要坐缆车下山，每辆缆车的最大承重为 W。已知每只小猫的重量，目标是求出最少需要多少辆缆车才能将所有小猫运下山。

该问题本质上是**装箱问题（Bin Packing）**的一个特例，是NP-Hard问题。对于数据范围较小的情况（通常 N <= 18），可以通过DFS配合强力剪枝在可接受时间内求解。

算法核心：DFS与剪枝

基本思路是使用DFS为每只小猫分配缆车（放入已有的车或新开一辆车），并记录当前使用的缆车数量。搜索过程中，通过剪枝避免无效搜索，是算法高效的关键。

关键剪枝策略

1. 优化搜索顺序：将小猫按体重从大到小排序。重量大的小猫选择少，优先处理它们可以减少搜索树的分支数量。
2. 可行性剪枝：在尝试将当前小猫放入某个现有缆车时，如果该缆车当前载重加上小猫重量超过承重上限 W，则不可行，直接跳过。
3. 最优性剪枝（最重要）：在搜索过程中，如果当前已经使用的缆车数量 cnt 已经大于或等于当前记录的最优解 ans，那么即使继续搜索下去，也不可能得到比 ans 更优的解（车数更少），因此可以立即回溯，终止当前分支。
4. 等效状态排除：由于缆车是无差别的，在分配时，规定“将小猫放入一个已有的空缆车”时，只选择第一个空缆车，避免因顺序不同产生的重复状态。

代码实现示例

Python 实现

def kitten_climbing(cats, W):
    n = len(cats)
    cats.sort(reverse=True)  # 优化搜索顺序：从大到小排序
    ans = n  # 最坏情况，每只小猫一辆车
    carriage = [0] * n  # 记录每辆缆车的当前载重，最多n辆车

    def dfs(u, k):  # u: 当前处理到第u只小猫 (0-index), k: 当前已使用的缆车数量
        nonlocal ans
        # 最优性剪枝：如果当前车数已经不可能更优，直接返回
        if k >= ans:
            return
        # 如果所有小猫都已分配完毕，更新答案
        if u == n:
            ans = k
            return

        # 尝试将第u只小猫放入已有的缆车
        for i in range(k):
            if carriage[i] + cats[u] <= W:  # 可行性剪枝
                carriage[i] += cats[u]
                dfs(u + 1, k)
                carriage[i] -= cats[u]  # 回溯

        # 尝试新开一辆缆车来放这只小猫
        carriage[k] = cats[u]
        dfs(u + 1, k + 1)
        carriage[k] = 0  # 回溯

    dfs(0, 0)
    return ans

# 示例
cats = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
W = 15
print(f"最少需要缆车数量: {kitten_climbing(cats, W)}")  # 输出可能为 3

Java 实现

import java.util.Arrays;
import java.util.Collections;

public class KittenClimbing {
    private static Integer[] cats; // 使用Integer以便使用Collections.reverseOrder
    private static int[] carriage;
    private static int W;
    private static int n;
    private static int ans;

    public static int minCarriages(Integer[] weights, int capacity) {
        cats = weights;
        W = capacity;
        n = cats.length;
        ans = n; // 初始化最坏情况
        carriage = new int[n];

        // 优化搜索顺序：从大到小排序
        Arrays.sort(cats, Collections.reverseOrder());

        dfs(0, 0);
        return ans;
    }

    private static void dfs(int u, int k) {
        // 最优性剪枝
        if (k >= ans) return;
        if (u == n) {
            ans = k;
            return;
        }

        // 尝试放入已有缆车
        for (int i = 0; i < k; i++) {
            if (carriage[i] + cats[u] <= W) { // 可行性剪枝
                carriage[i] += cats[u];
                dfs(u + 1, k);
                carriage[i] -= cats[u]; // 回溯
            }
        }

        // 尝试新开一辆车
        carriage[k] = cats[u];
        dfs(u + 1, k + 1);
        carriage[k] = 0; // 回溯
    }

    public static void main(String[] args) {
        Integer[] cats = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int W = 15;
        System.out.println("最少需要缆车数量: " + minCarriages(cats, W)); // 输出可能为 3
    }
}

复杂度分析

• 时间复杂度：理论上最坏是指数级 O(k^n)，但由于强力的剪枝（尤其是最优性剪枝），实际运行效率很高，能够解决 n <= 18 的典型竞赛数据范围。
• 空间复杂度：主要为递归栈和数组存储，O(n)。

总结与扩展

“小猫爬山”是学习DFS剪枝的绝佳例题。它清晰地展示了：

1. 搜索顺序的重要性：通过排序改变决策顺序，能显著影响搜索树形态。
2. 剪枝的艺术：结合问题特性的剪枝（如最优性剪枝）往往比通用优化更有效。

扩展思考：

• 如果缆车数量有上限，如何修改算法？
• 如何将算法改为迭代加深搜索（IDS）？
• 对于更大的 N，可以考虑使用启发式算法、动态规划（状态压缩DP）或整数规划来求解。

掌握“小猫爬山”的解题思路，对于解决其他需要剪枝的DFS问题（如数独、八皇后、排列组合优化等）具有重要的借鉴意义。