穷举搜索（Exhaustive Search），又称暴力搜索（Brute-Force Search），是一种在问题求解中对所有可能的情况进行逐一列举和检查的基本搜索算法，以下是对其更详细的介绍：
算法原理
- 基于问题的解空间，对其中的每一个可能解进行系统的、全面的遍历和评估，不依赖任何启发式信息或特定的搜索策略来缩小搜索范围。
- 对于一个给定的问题，穷举搜索会生成所有可能的候选解，然后逐一验证这些解是否满足问题的约束条件或目标函数，直到找到一个可行解或确定问题无解为止。
实现步骤
- 定义解空间：明确问题的所有可能解的集合，确定解的表示形式和范围。
- 生成候选解：按照一定的顺序或规则，依次生成解空间中的每一个候选解。
- 评估候选解：对每个生成的候选解，根据问题的要求进行评估，判断其是否满足条件。
- 确定结果：如果找到满足条件的解，则返回该解；如果遍历完整个解空间都没有找到解，则根据具体情况返回相应的结果，如无解提示等。
时间复杂度和空间复杂度
- 时间复杂度：通常非常高，在最坏情况下，需要遍历解空间中的所有元素，其时间复杂度往往是指数级或阶乘级的。
- 空间复杂度：取决于解空间的大小和存储每个候选解所需的空间，可能也会随着问题规模的增大而急剧增加。
应用案例
- 旅行商问题：给定一组城市和它们之间的距离，要求找到一条经过所有城市且每个城市只经过一次的最短路径。穷举搜索会生成所有可能的城市排列顺序，计算每个排列的路径总长度，然后找到最短的路径。
- 背包问题：有一个背包和若干物品，每个物品有一定的重量和价值，要求在背包容量有限的情况下选择物品，使背包中物品的总价值最大。穷举搜索会考虑所有可能的物品组合，计算每个组合的总重量和总价值，找到满足背包容量且价值最大的组合。
- 数独求解：对于一个给定的数独谜题，穷举搜索可以尝试所有可能的数字填充方案，直到找到一个满足数独规则的解。
优化与改进
- 剪枝策略：通过分析问题的特点和约束条件，在搜索过程中提前排除一些明显不可能是解的分支，减少不必要的搜索。
- 并行计算：利用多核处理器或分布式计算环境，将搜索任务并行化，同时处理多个候选解，提高搜索效率。