本文共 1559 字，大约阅读时间需要 5 分钟。

穷举法及其应用实例

1. 穷举法概念

穷举法，又称穷举搜索法，是一种在解空间中对所有可能解逐一检查的方法。

2. 设计思路

使用穷举法解决问题，主要包含两个核心步骤：

2.1 解空间定义

解空间是问题的候选解的约束范围，通过明确这一范围，可以聚焦搜索目标，避免无效遍历。定位正确的解空间，是实现高效穷举的关键。

2.2 穷举策略与剪枝

穷举解空间需要根据其结构选择策略：

• 盲目搜索：不加任何假设，全面检查所有可能的解，这虽可靠，但效率低。
• 启发性搜索：利用启发函数，缩小搜索范围，优先检查更有可能的解，显著提高效率。

为了提升效率，可以结合剪枝策略：

• 基于问题特点，评估解空间中的某些状态是否可能被排除，从而避免不必要的计算。
• 剪枝的难点在于如何设计有效的评估函数。

此外，对于$search-depth受限的问题（如博弈树搜索），限制搜索深度可以加快收敛，但需权衡是否有遗漏最优解的风险。

2.3 剪枝策略

剪枝是穷举算法的高效性关键。在遍历解空间时，若某些状态明确无法达到最优解，应立即跳过其子树的遍历。

3. 实例分析

3.1 百钱买鸡问题

问题&目标：100个钱购买100只鸡（公鸡5元，母鸡3元，小鸡1元）。求购买方案数。

• 盲目搜索：通过三重循环检查所有可能的购买组合，输出符合预算和总数量的组合。由于缺乏限制条件，导致搜索次数大幅增加。

  for x in range(1, 100):
      for y in range(1, 100):
          for z in range(1, 100):
              if x + y + z == 100 and 5x + 3y + z/3 == 100:
                  print(x, y, z)

• 启发性搜索：基于鸡的数量有限制（x ≤20，y ≤33），优化搜索范围。通过优化，速度提升10倍。

  for x in range(1, 21):
      for y in range(1, 34):
          if x + y + (100 - x - y)/3 == 100:
              print(x, y, 100 - x - y)

3.2 鸡兔同笼问题

问题&目标：斑马和鸡的数量已知头和脚的总数，求鸡兔数量。

• 盲目搜索：遍历所有鸡兔组合，满足头和脚的条件。检验效率较高，但方案直接。

  for x in range(1, 51):
      for y in range(1, 51):
          if x + y == 50 and 2x + 4y == 120:
              print(x, y)

• 启发性搜索：基于鸡的数量限制（x ≤40），直接计算兔的数量，极大提升效率。

  for x in range(1, 51):
      if 2x + 4*(50 - x) == 120:
          print(x, 50 - x)

总结

穷举法通过全面或有策略的搜索，确保能找到问题的解。其适用范围广，设计时需关注问题特点和解空间结构。通过结合剪枝策略和启发性搜索，显著提升解算效率。