数据结构与算法-搜索-剪枝

在深度优先搜索（DFS）算法中，剪枝是一种优化策略，用于减少不必要的搜索，从而提高算法的效率。以下将详细介绍 DFS 剪枝的相关内容：

剪枝的基本概念

在进行深度优先搜索时，搜索空间往往非常庞大，如果对所有可能的路径都进行搜索，会消耗大量的时间和空间资源。剪枝的核心思想是通过一些判断条件，提前排除那些不可能产生最优解或者有效解的分支，避免对这些分支进行不必要的搜索，就像修剪树枝一样，将无用的部分去掉，让搜索过程更加高效。

常见的剪枝策略

1. 可行性剪枝

原理：在搜索过程中，如果当前状态已经不满足问题的某些约束条件，那么从这个状态继续搜索下去不可能得到有效的解，此时可以直接剪去该分支。

示例：在一个迷宫问题中，要求从起点走到终点，并且每一步只能向右或向下移动。如果当前位置已经超出了迷宫的边界，那么从这个位置继续搜索显然是没有意义的，因此可以直接剪去该分支。

2. 最优性剪枝

原理：如果当前的搜索路径所得到的结果已经不可能比当前已知的最优解更优，那么可以直接剪去该分支。

示例：在求解最短路径问题时，已经找到了一条长度为 min_dist 的路径，如果当前搜索路径的长度已经超过了 min_dist，那么从这个路径继续搜索下去不可能得到更短的路径，因此可以直接剪去该分支。

3. 重复性剪枝

原理：在搜索过程中，如果某些状态是重复的，那么只需要对其中一个状态进行搜索，避免对重复状态进行多次搜索。

示例：在全排列问题中，可能会出现一些重复的排列情况，可以使用一个集合来记录已经生成的排列，避免重复生成相同的排列。

4.优化搜索顺序

基于问题特性选择优先方向

在许多搜索问题里，问题本身具备一定的特性，依据这些特性挑选合适的搜索方向，能让搜索更快接近目标。

比如一个迷宫中，我们要从左上角走到右下角，所以我们更希望先走下和右

简单说，大部分情况下，我们更希望走分支更小的节点

5.记忆化搜索

原理：在递归求解问题的过程中，很多子问题会被重复计算，这会导致时间复杂度大大增加。记忆化搜索的核心思想是使用一个数据结构（通常是数组或哈希表）来记录已经求解过的子问题的结果。当再次遇到相同的子问题时，直接从记录中获取结果，而不需要重新计算，从而避免了大量的重复计算，提高了算法的效率。

习题1（小猫爬山）：

分析：

回溯法思路

状态表示：用一个列表记录每只小猫分配到的缆车编号（初始为未分配状态），以此作为当前分配状态。

初始状态：所有小猫都未分配缆车。

状态转移：对于每只小猫，依次尝试将其放入已有的缆车或新开启一辆缆车。放入前需检查该缆车加上这只小猫后的重量是否超过最大承重 W。

终止条件：当所有小猫都分配完缆车时，记录此时使用的缆车数量。在搜索过程中，记录遇到的最小缆车数量，遍历完所有可能的分配情况后，得到的最小数量就是答案。但这种方法时间复杂度高，在 N 较大时可能超时。

伪代码：

习题2（数独）：

分析：

这是一个数独求解问题，常见的解决方法是使用深度优先搜索（DFS）结合回溯算法，以下是具体分析：

算法思路

状态表示：用一个二维数组 sudoku[9][9] 来表示数独棋盘，其中已有的数字直接填入，空白格用 0 表示。

初始状态：根据给定的不完整数独，初始化 sudoku 数组。

状态转移：从棋盘的左上角开始，按行优先顺序遍历每个格子。对于空白格（值为 0），尝试填入 1 到 9 的数字。在填入数字前，检查该数字在当前行、当前列以及所在的 3×3 九宫格内是否已经出现，如果未出现，则将该数字填入，并继续递归处理下一个空白格；如果出现，则回溯，尝试下一个数字。

终止条件：当所有的空白格都被成功填满，且满足数独规则（每行、每列、每个 3×3 九宫格内数字 1 - 9 恰好出现一次）时，数独求解完成；如果尝试了所有可能的数字组合都无法填满数独，则表示当前数独无解（但本题给定的数独通常是有解的）。

这个题可以通过判断行，列，伪九宫格进行可行性优化，通过搜索顺序实现搜索顺序优化

这里也可以用二进制，方便的去查找可行的数字

伪代码：

习题3（木棒）：

分析：

深度优先搜索（DFS）思路

状态表示：用一个列表记录所有截断木棍的长度，当前已拼接好的木棒数量、当前正在拼接的木棒长度以及剩余未使用的木棍。

初始状态：给定的截断木棍列表，已拼接木棒数量为 0，当前正在拼接的木棒长度为 0，所有木棍都未使用。

状态转移：从剩余未使用的木棍中依次尝试选取一根，将其加入到当前正在拼接的木棒中。若当前木棒长度加上该木棍长度不超过可能的原始木棒长度，继续递归尝试拼接；若恰好等于可能的原始木棒长度，则已拼接好的木棒数量加 1，重新开始拼接新的木棒；若超过，则回溯，尝试下一根木棍。

终止条件：当所有木棍都被成功拼接成若干根长度相等的木棒时，记录此时假设的原始木棒长度，在尝试完所有可能的长度后，找到满足条件的最小长度。

剪枝优化：

伪代码：

习题4（生日蛋糕）：

分析：

这是一个优化求解问题，目标是在给定蛋糕层数(M)和总体积(Npi)的条件下，找到每层蛋糕半径(R_i)和高度(H_i)的组合，使得蛋糕外表面面积(S)最小（最下层下底面除外）。

深度优先搜索（DFS）

思路

 - 状态表示：用当前层数(cur_layer)表示当前搜索到的蛋糕层数，已用体积(used_volume)表示当前已组合出的蛋糕体积，已用表面积(used_area)表示当前已确定的蛋糕外表面面积（不包含最下层下底面），并记录每层蛋糕的半径(R)和高度(H)。

 - 初始状态：(cur_layer = M)（从顶层开始搜索），(used_volume = 0)，(used_area = 0)。

- 状态转移：对于当前层，按照半径和高度的递减规则（因为(R_i > R_{i + 1})且(H_i > H_{i + 1})），从可能的最大值开始枚举半径(R)和高度(H)。若当前层体积加上已用体积不超过总体积，且当前层侧面积加上已用面积有可能小于当前记录的最小面积，就将当前层加入蛋糕组合，递归搜索下一层；若不满足条件，则回溯，尝试其他半径和高度组合。

- 终止条件：当层数为(0)且总体积恰好满足时，更新最小表面积；若层数为(0)但总体积不满足，直接回溯。     

优化策略（剪枝）

体积剪枝：计算从当前层到最底层所需的最小体积，如果已用体积加上这个最小体积超过总体积，直接剪枝。比如第i层最小半径为i，最小高度为i，其最小体积为i^3*pi，可据此计算后续层最小体积总和。

面积剪枝：计算从当前层到最底层所需的最小侧面积，如果已用面积加上这个最小侧面积超过当前记录的最小表面积，直接剪枝。每层最小侧面积为2 pi i^2（为层数对应的最小半径），可据此计算后续层最小侧面积总和。

伪代码：