大家好，我是阿Q。

今天先告诉大家一个好消息，鸽了这么久的pdf整理，终于放后台了，也分类好了，欢迎大家下载学习~

那么今天呢，给大家分享一下常见的经典算法~

一、排序算法

十大排序

二、查找算法

七大查找算法

三、分治算法

3.1、基本概念

3.2、基本思想及策略

3.2.1、基本思想

3.2.2、分治策略

3.3、基本步骤

1. 分解（Divide）：将原问题分解成若干个规模较小的子问题，这些子问题通常具有与原问题相似的结构。分解过程需要使子问题之间相互独立，以便能够并行或递归地解决。
2. 解决（Conquer）：递归地解决每个子问题。如果子问题足够小，就可以直接求解而不需要继续分解。这是递归算法的关键点，也是问题的实际求解部分。
3. 合并（Combine）：将子问题的解合并成原始问题的解。这个步骤通常涉及将多个子问题的解组合起来以获得原问题的最终解。这是分治策略的关键点之一。

3.4、优缺点

• 优点
• 可并行性：分治算法通常可以将一个大问题分解成若干个独立的子问题，这些子问题可以并行处理，从而提高了算法的执行效率。这对于多核和分布式计算非常有利。
• 模块化：分治算法将问题分解成相对独立的子问题，这使得算法更易于理解、编写和维护。每个子问题可以单独考虑，降低了问题的复杂性。
• 可复用性：一些分治算法可以用于解决多种不同类型的问题，只需适应性地修改子问题的定义和解合并的方法。这提高了算法的可复用性。
• 高效性：在某些情况下，分治算法的时间复杂度相对较低。例如，归并排序和快速排序等排序算法都具有较好的平均时间复杂度。
• 缺点
• 额外的空间复杂度：分治算法通常需要额外的存储空间来存储子问题的中间结果，这可能导致较高的空间复杂度。这在处理大规模问题时可能成为问题。
• 递归开销：分治算法通常以递归方式实现，递归调用需要额外的栈空间，可能导致栈溢出或降低算法的性能。尤其是在问题的规模非常大时。
• 不一定适用于所有问题：并不是所有问题都适合分治算法。有些问题分解和解合并的开销可能会超过问题本身的计算开销，导致算法效率低下。
• 难以设计：一些问题的分解和解合并过程较为复杂，需要巧妙的设计和分析。不同的问题可能需要不同的分治策略，因此算法的设计可能会具有一定挑战性。

3.5、复杂度分析

• 时间复杂度

• 空间复杂度

3.6、可解决的经典问题

1. 归并排序（Merge Sort）：将一个大的数组分成两个较小的子数组，对子数组进行排序，然后将它们合并成一个有序数组。
2. 快速排序（Quick Sort）：通过选择一个基准元素，将数组分成两部分，小于基准的在左边，大于基准的在右边，然后对两部分分别进行快速排序。
3. 二分查找（Binary Search）：在有序数组中查找目标元素，将数组分成两部分，判断目标元素在左侧还是右侧，然后继续在一侧进行查找。
4. 汉诺塔问题（Tower of Hanoi）：将一堆盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，且大盘子不能放在小盘子上面。
5. 最大子数组和问题（Maximum Subarray Sum）：寻找一个数组中连续子数组的最大和，可以使用分治法来解决。
6. 最接近点对问题（Closest Pair of Points）：在给定的一组点中，寻找距离最近的一对点，可以使用分治法来加速搜索。
7. 矩阵乘法（Matrix Multiplication）：将一个大矩阵分解成小矩阵，分别进行相乘，然后合并结果。
8. 多项式乘法（Polynomial Multiplication）：将两个多项式相乘，可以使用分治法的Karatsuba算法来加速。
9. 寻找中位数（Find Median）：在一组数据中寻找中位数，可以使用分治法来提高效率。
10. 最近邻问题（Nearest Neighbor Problem）：在给定的点集中，寻找一个点的最近邻点，可以使用分治法来优化搜索。

四、动态规划算法

4.1、基本概念

4.2、基本思想及策略

4.2.1、基本思想

4.2.2、策略

4.3、基本步骤

1. 问题分解：动态规划问题通常可以被分解成若干个子问题，这些子问题的解可以用来构建原始问题的解。这种分解是问题求解的关键。
2. 子问题重叠性：动态规划中的子问题通常不是相互独立的，而是存在重叠的情况，即多次需要求解相同的子问题。这种性质是动态规划算法能够高效求解的基础。
3. 最优子结构：动态规划问题满足最优子结构性质，即一个问题的最优解可以通过其子问题的最优解来构建。这意味着可以通过解决子问题来构建整体问题的最优解。
4. 状态定义：动态规划问题中需要明确定义问题的状态。状态是问题的一个关键属性，它包含了问题的关键信息，通常用于描述问题的不同变化情况。
5. 状态转移方程：动态规划问题的核心是建立状态之间的转移关系，也就是如何从一个子问题的解推导出另一个子问题的解。这一步通常通过状态转移方程来实现。
6. 初始化条件：动态规划问题通常需要初始化一些状态，以便在迭代求解过程中能够顺利开始。这些初始化条件是问题求解的起点。
7. 计算顺序：动态规划通常有两种计算顺序，一种是自顶向下的递归计算，另一种是自底向上的迭代计算。自底向上的迭代方法更常用，因为它避免了重复计算。

4.4、优缺点

• 优点
• 高效性：动态规划通常能够在多项式时间内解决复杂的问题，因此在计算效率上具有很大的优势。对于一些指数级别的问题，动态规划往往能够在合理时间内找到解决方案。
• 问题解决：动态规划适用于多种问题，包括优化问题、组合问题、搜索问题等。它能够找到问题的最优解，或者在有限时间内找到一个近似最优解。
• 避免重复计算：动态规划的核心思想是将问题分解成子问题，并将子问题的解保存起来，避免了重复计算。这大大提高了计算效率。
• 可读性良好：动态规划的思路清晰，通常可以通过递归或迭代的方式实现，代码结构较为清晰，易于理解和维护。
• 缺点
• 状态空间大：对于某些问题，动态规划需要构建一个庞大的状态空间，需要大量的内存来存储中间结果。这可能导致内存消耗过大，甚至无法运行。
• 状态转移方程难以确定：对于一些复杂问题，确定合适的状态转移方程可能较为困难。在解决问题之前，需要深入分析问题的特性和规律。
• 计算时间较长：对于某些问题，尤其是指数级别的问题，动态规划虽然可以找到解决方案，但计算时间较长，可能不适合实际应用。
• 不适用于所有问题：动态规划并不是万能的，不适用于所有类型的问题。有些问题可能根本无法用动态规划解决，或者需要结合其他方法。
• 局部最优解：动态规划通常能够找到全局最优解，但在某些情况下可能会陷入局部最优解，需要谨慎设计状态空间和转移方程。

4.5、复杂度分析

• 时间复杂度：
• 状态个数：动态规划的时间复杂度通常与状态的个数成正比。如果问题的状态空间大小为N，状态转移方程需要O(1)时间计算，那么动态规划的时间复杂度为O(N)。
• 状态转移方程复杂度：如果状态转移方程的计算复杂度为O(K)，其中K是一个常数，那么动态规划的时间复杂度为O(NK)。
• 自底向上 vs. 自顶向下：动态规划可以使用自底向上（迭代）和自顶向下（递归）两种方法实现。自底向上通常更节省时间，因为它避免了递归调用的开销。
• 问题性质：动态规划问题的性质不同，时间复杂度也会不同。一些问题可以用线性时间解决，而其他问题可能需要更多的时间。
• 空间复杂度：
• 状态空间大小：动态规划的空间复杂度通常与状态空间的大小成正比。如果问题的状态空间大小为N，那么动态规划的空间复杂度通常为O(N)。
• 状态转移表：在自底向上的动态规划中，需要创建一个状态转移表或数组来存储中间结果。这个表的大小与状态空间大小相同，因此会占用额外的空间。
• 滚动数组（可选）：为了降低空间复杂度，有时可以使用滚动数组技巧，只保留当前阶段的状态和前一阶段的状态，从而减少空间需求。

4.6、可解决的经典问题

1. 斐波那契数列（Fibonacci Sequence）：计算斐波那契数列的第n个数字。这是动态规划的入门问题，通常用于说明其基本原理。
2. 背包问题（Knapsack Problem）：给定一组物品的重量和价值，以及一个背包的容量，确定如何选择物品放入背包，以使得背包中的物品总价值最大。
3. 最长公共子序列（Longest Common Subsequence）：给定两个序列，找到它们的最长公共子序列，不要求连续。这常用于字符串比对和DNA序列比对。
4. 最短路径问题（Shortest Path Problem）：寻找两个顶点之间的最短路径，如Dijkstra算法和Floyd-Warshall算法。
5. 最长递增子序列（Longest Increasing Subsequence）：给定一个序列，找到其中的一个最长递增子序列。
6. 编辑距离（Edit Distance）：计算将一个字符串转换为另一个字符串所需的最少编辑操作次数，如插入、删除和替换。
7. 硬币找零问题（Coin Change Problem）：给定一组面额不同的硬币和一个目标金额，确定组合硬币的最小数量以达到目标金额。
8. 矩阵链乘法问题（Matrix Chain Multiplication Problem）：给定一组矩阵，确定以何种顺序相乘这些矩阵以获得最小的计算成本。
9. 最长回文子串（Longest Palindromic Substring）：找到一个字符串中的最长回文子串，即正着读和倒着读都相同的子串。
10. 打家劫舍问题（House Robber Problem）：给定一组房屋，每个房屋中有一定数量的钱，相邻的房屋被安装了警报系统，阻止小偷入侵。确定小偷在不触发警报的情况下能偷到的最大金额。
11. 单词拆分问题（Word Break Problem）：给定一个字符串和一个单词词典，确定字符串是否可以由词典中的单词拼接而成。
12. 股票买卖问题（Stock Buy and Sell Problem）：给定一组股票的价格，确定何时买入和卖出以获得最大的利润。

4.7、适用情况

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

五、贪心算法

5.1、基本概念

5.2、基本思路

1. 问题建模： 将问题转化为一个数学模型，明确定义问题的目标和约束条件。通常，贪心算法适用于那些具有最优子结构性质的问题，即问题的最优解可以通过子问题的最优解来构建。
2. 候选集合：对于每一步，确定可供选择的候选项集合。这是贪心算法的核心部分，因为在每一步中都需要从候选项中选择一个。
3. 选择最优：从候选项集合中选择一个最优的候选项，通常是根据某种规则或者评估函数来选择。
4. 更新状态：更新问题的状态，通常包括更新问题的目标和问题的约束条件。
5. 终止条件：判断是否满足问题的终止条件，如果满足，则算法结束；否则，返回第2步继续执行。
6. 构建解：根据选择的最优候选项构建问题的解。在贪心算法中，每一步的选择都会被纳入最终解中。
7. 优化：可能需要对最终解进行优化，以满足问题的特定需求。

5.3、优缺点

• 优点：
• 简单易实现：贪心算法通常相对简单，容易理解和实现。这使得它成为解决许多问题的快速选择。
• 高效性：贪心算法通常具有很高的执行速度，因为它在每一步都选择局部最优解，而不需要考虑全局问题。
• 适用性广泛：贪心算法适用于那些满足最优子结构性质的问题。也就是说，问题的最优解可以通过子问题的最优解来构建。
• 不需要 exhaustive search：贪心算法不需要像穷举法那样遍历所有可能的解空间，因此在某些情况下，它可以在合理的时间内找到一个接近最优解的解。
• 缺点：
• 不一定得到最优解：贪心算法每一步都选择局部最优解，但这并不意味着它能够找到全局最优解。在某些情况下，贪心算法可能陷入局部最优解，导致得到次优解。
• 问题选择限制：贪心算法适用于一些特定类型的问题，但对于那些不满足最优子结构性质的问题，贪心算法通常无法给出正确的解。
• 需要证明正确性：在应用贪心算法时，通常需要证明它的正确性。这可能需要更多的工作，并且并不是所有问题都容易证明。
• 局部决策可能导致全局不一致：贪心算法是一种基于局部决策的方法，因此可能会导致全局不一致的结果。这是因为每一步都是基于当前情况下的最优选择，而不考虑未来可能的变化。

5.4、复杂度分析

• 时间复杂度：

• 对于具有最优子结构性质的问题，贪心算法通常可以在O(n)时间内找到最优解，其中n是问题规模。
• 对于不具备最优子结构性质的问题，贪心算法的时间复杂度可能会更高，可能是O(n log n)或更高，具体取决于问题的特性。

• 空间复杂度：

• 如果贪心算法只涉及到常数级别的额外空间，空间复杂度将是O(1)。
• 如果算法需要存储和处理输入数据的数据结构，空间复杂度将依赖于这些数据结构的空间需求，通常是O(n)。

5.5、可解决的经典问题

1. 最小生成树问题：例如，Kruskal算法和Prim算法用于寻找加权无向图的最小生成树。
2. 单源最短路径问题：Dijkstra算法通常用于寻找从一个源节点到图中其他所有节点的最短路径。
3. 哈夫曼编码：贪心算法用于构建最优的变长编码树，通常用于数据压缩。
4. 任务调度问题：例如，贪心算法可用于在给定机器上安排任务，以最小化总完成时间（最短作业优先算法）。
5. 零钱找零问题：在给定一组面额不同的硬币和一个要找零的金额时，贪心算法可以用于找到最少的硬币数量。
6. 背包问题的一些变种：一些背包问题中，贪心算法可以用于找到一个接近最优解的解决方案，例如分数背包问题。
7. 调度问题：在一些作业调度问题中，贪心算法可以用于找到一个接近最优的作业顺序。

六、回溯算法

6.1、基本概念

6.2、基本思想及策略

6.2.1、基本思想

6.2.2、策略

6.3、基本步骤

1. 建立解空间树：将问题的所有可能解构成一棵解空间树，树的节点表示问题的不同状态或者部分解。
2. 深度优先搜索：从树的根节点开始，采用深度优先搜索的方式，逐步向树的叶子节点搜索。
3. 剪枝操作：在搜索的过程中，根据问题的限制条件进行剪枝操作，即丢弃那些不可能满足条件的子树。
4. 记录解：如果在搜索的过程中找到一个满足条件的解，就记录下来。
5. 回溯操作：如果当前搜索无法继续，就回溯到上一个节点，尝试其他的选择，继续搜索。
6. 结束条件：当搜索完所有可能的解或者找到一个满足条件的解时，算法结束。

6.4、优缺点

• 优点：
• 能够找到所有可能的解：回溯算法通过穷举的方式搜索问题的解空间，可以找到所有可能的解，因此适用于那些需要找到所有解的问题。
• 灵活性强：回溯算法的实现相对灵活，可以根据具体问题设计不同的状态转移和剪枝策略，因此适用于各种类型的组合问题。
• 可以求解最优解：在回溯搜索的过程中，可以记录和更新当前的最优解，从而找到问题的最优解。
• 不需要额外的空间：回溯算法通常不需要额外的数据结构来存储搜索状态，因此空间复杂度相对较低。
• 缺点：
• 指数级时间复杂度：在搜索空间较大的情况下，回溯算法的时间复杂度会呈指数级增长，因此对于大规模问题，计算时间可能会非常长。
• 无法应对某些问题：对于某些问题，回溯算法可能并不是最优的选择，因为它需要搜索所有可能的解，而有些问题存在更高效的算法。
• 可能会陷入局部最优解：回溯算法不一定能够找到全局最优解，特别是在搜索空间较大且存在多个局部最优解的情况下，可能会陷入局部最优解。
• 搜索空间大时效率低下：在搜索空间非常大的情况下，回溯算法的效率很低，因此需要合理设计问题的限制条件和剪枝策略，以提高算法的效率。

6.5、复杂度分析

• 时间复杂度：
• 最坏情况下的时间复杂度：在最坏情况下，回溯算法需要遍历状态空间的所有可能路径，因此时间复杂度为指数级别，通常为O(2^n)，其中n是问题的规模或状态空间的大小。
• 平均情况下的时间复杂度：平均情况下的时间复杂度可能会依赖于问题的具体性质和剪枝策略。对于某些问题，合理的剪枝策略可以显著减小搜索空间，从而降低平均时间复杂度。
• 空间复杂度：
• 系统栈空间：回溯算法通常使用递归或迭代的方式来实现，每次递归调用或迭代都会消耗一定的系统栈空间，其空间复杂度取决于递归或迭代的最大深度。在最坏情况下，递归的最大深度可能达到问题的规模n，因此空间复杂度为O(n)。
• 状态空间的存储：如果需要在回溯算法中存储状态空间的信息，例如用于记录路径或保存中间结果，那么空间复杂度将取决于状态空间的大小。如果状态空间很大，可能需要较多的额外空间。

6.6、可解决的经典问题

1. 八皇后问题（N皇后问题）：在一个8x8的国际象棋棋盘上放置8个皇后，使得它们互相不能攻击（不在同一行、同一列、同一对角线上）。这是经典的回溯问题。
2. 0-1背包问题：给定一组物品，每个物品有重量和价值，以及一个背包容量限制，要求在不超过背包容量的情况下，选择物品放入背包，使得放入背包的物品总价值最大。
3. 排列和组合问题：生成给定元素的所有排列或组合。这种问题在密码学、组合数学和生成测试用例时非常有用。
4. 数独问题：填充一个9x9的数独棋盘，使得每一行、每一列和每一个3x3的子网格中都包含了1到9的数字，且不重复。
5. 全排列问题：给定一组不同的元素，生成它们的所有排列。
6. 子集和问题：给定一组正整数和一个目标整数，确定是否存在一个子集的和等于目标整数。
7. 图的着色问题：给定一个图，找到一种方式为每个节点分配颜色，使得相邻的节点颜色不同。
8. 迷宫问题：在一个迷宫中找到从起点到终点的路径，通常包括了不同的障碍物和路径限制。
9. 电话号码的字母组合：给定一个数字字符串，每个数字对应于电话按键上的一些字母，求出所有可能的字母组合。
10. 单词搜索：在一个二维字符网格中搜索给定的单词，可以朝上、下、左、右相邻的单元格中寻找。

6.7、回溯VS递归

七、分支限界法

7.1、基本概念

7.2、基本思想

7.3、基本步骤

1. 问题建模：首先将原始问题建模成一个可行解空间的树形结构。每个节点表示一个子问题，通常包括了问题的某个部分解，同时计算出该部分解的上下界。
2. 状态空间树：构建一个状态空间树，树的根节点表示原始问题，树的每个节点表示一个子问题。通过分支操作，从根节点扩展出子节点，每个子节点代表一个更小的子问题。
3. 分支操作：选择一个尚未被探索的节点进行扩展，通常选择具有最有希望的子问题。这个选择可以基于某种启发式方法或者问题的特性来决定。分支操作可能包括问题的分割、约束的添加等操作。
4. 上下界估计：对每个子问题计算一个上界和下界。上界是当前子问题的最优解的估计值，下界是当前子问题可能达到的最优解的下限。这些界用于确定哪些子问题值得进一步探索。
5. 剪枝操作：如果一个子问题的上界小于目前已知的最优解，或者一个子问题的下界大于目前已知的最优解，那么可以剪去该子问题，因为它不可能包含最优解。
6. 搜索策略：选择如何探索子问题的策略非常重要。深度优先搜索和广度优先搜索都可以用于不同情况下。一些高级搜索策略，如最佳优先搜索（Best-First Search）和A*算法，也可以用于提高搜索效率。
7. 迭代搜索：通常，分支限界法采用迭代搜索策略，逐步改进最优解的估计。每次迭代都尝试寻找更好的解，直到找到最优解或者达到停止条件。
8. 停止条件：停止条件可以是找到最优解或者达到一定的时间或计算资源限制。

7.4、优缺点

• 优点：
• 能够找到最优解或高质量解：分支限界法设计了上下界的计算策略，可以有选择地探索最有希望的子问题，从而更有可能找到最优解或接近最优解的高质量解。
• 剪枝操作：分支限界法通过剪枝操作来排除不可能包含最优解的子问题，从而显著减少搜索空间，提高了求解效率。
• 适用性广泛：分支限界法适用于各种组合优化问题，如旅行商问题、0-1背包问题、调度问题等，因此具有广泛的适用性。
• 可扩展性：分支限界法可以与其他算法和启发式方法结合使用，以进一步提高求解效率，例如与贪心算法、动态规划等结合。
• 缺点：
• 可能受限于问题规模：对于某些问题，尤其是NP难问题，分支限界法的搜索空间仍然可能非常大，导致计算复杂度很高，难以在合理的时间内找到最优解。
• 不一定能找到所有解：分支限界法的主要目标是找到最优解，因此它通常不适用于需要找到所有解的问题。如果需要找到所有解，回溯法可能更合适。
• 需要设计合适的上下界计算策略：分支限界法的效果在很大程度上取决于上下界的计算策略。设计合适的界限计算方法可能需要一定的领域知识和问题理解。
• 对问题表述敏感：分支限界法对问题的表述形式较为敏感，不同的问题表述可能需要不同的搜索策略和启发式方法，因此需要根据具体问题进行调整和定制。

7.5、复杂度分析

• 时间复杂度：
• 搜索树的大小：分支限界法的时间复杂度与搜索树的大小密切相关。搜索树的大小取决于问题的规模和特性，通常情况下，问题规模越大，搜索树越大，时间复杂度越高。
• 剪枝策略：分支限界法的时间复杂度还受到剪枝策略的影响。剪枝策略的质量越高，能够剪掉的无效分支越多，从而减少搜索时间。不同问题可能需要不同的剪枝策略。
• 问题的性质：问题的性质也会影响时间复杂度。有些问题具有特殊的性质，例如具有子问题重叠性的问题，可能可以通过记忆化搜索减少冗余计算，降低时间复杂度。
• 搜索策略：分支限界法的时间复杂度还取决于搜索策略，即选择哪个子问题进行扩展。最佳的搜索策略通常依赖于问题的特性。
• 空间复杂度：
• 搜索树的深度：空间复杂度主要取决于搜索树的深度，因为递归调用或使用堆栈来管理子问题的状态需要一定的内存空间。搜索树的深度与问题的规模和特性有关。
• 状态空间大小：空间复杂度还取决于状态空间的大小，即存储每个子问题的状态所需的内存。状态空间大小与问题的规模和状态表示方式有关。
• 剪枝策略：剪枝策略可以降低空间复杂度，因为它可以减少需要存储的子问题状态数量。剪枝得越多，空间复杂度越低。
• 记忆化搜索：对于具有子问题重叠性的问题，可以使用记忆化搜索来存储已计算的子问题结果，从而减少重复计算，但需要额外的内存空间。

7.6、可解决的经典问题

1. 旅行商问题（TSP）：在给定的一组城市之间找到最短的路径，使得每个城市只访问一次，然后回到起点城市。
2. 0-1背包问题：给定一组物品，每个物品有重量和价值，找到一个组合，使得在限定的背包容量内，总重量不超过容量，但总价值最大化。
3. 图着色问题：给定一个图，找到一种方式为每个节点分配颜色，使得相邻节点具有不同的颜色。
4. 任务分配问题：将一组任务分配给一组工作者，以最小化总成本或最大化总效益。
5. 集合覆盖问题：给定一组集合和一组元素，找到最小的子集合，以覆盖所有元素。
6. 子集和问题：给定一组正整数和一个目标值，确定是否可以从这组整数中选择一个子集，使得子集的和等于目标值。
7. 最大团问题：在无向图中找到一个完全子图（即每对节点都相邻），使得该子图的大小最大。
8. 排列问题：找到一组元素的全排列，满足一定的条件，例如字典序最小或最大。
9. 时间表调度问题：安排一组任务的执行顺序，以最小化总时间或最大化资源利用率。
10. 机器调度问题：将一组任务分配给一组机器，以最小化总执行时间或最大化机器利用率。

7.7、回溯法VS分支限界法

1. 基本思想：
1. 回溯法：回溯法是一种暴力搜索算法，它通过深度优先搜索的方式，穷举所有可能的解空间，并在搜索过程中剪枝以提高效率。回溯法通常用于在搜索过程中找到满足特定条件的解。
2. 分支限界法：分支限界法也是一种搜索算法，但它引入了一些策略来限制搜索空间，以提高效率。分支限界法通过计算每个子问题的上下界，并有选择地探索最有希望的子问题。
2. 搜索策略：
1. 回溯法：回溯法通常采用深度优先搜索策略，它会一直搜索下去，直到找到问题的解或者确定没有解为止。
2. 分支限界法：分支限界法可以采用不同的搜索策略，包括深度优先搜索、广度优先搜索，以及一些高级的启发式搜索策略，如最佳优先搜索。
3. 剪枝操作：
1. 回溯法：回溯法通常在搜索的过程中进行剪枝，以排除不满足条件的路径，以节省搜索时间。它的剪枝操作通常基于当前路径的状态和约束条件。
2. 分支限界法：分支限界法的剪枝操作更加精细，它会根据计算得到的上下界信息来剪枝，从而排除那些不可能包含最优解的子问题。
4. 问题适用性：
1. 回溯法：回溯法适用于需要找到所有解的问题，它可以穷尽所有可能的解空间。
2. 分支限界法：分支限界法适用于需要找到最优解或高质量解的问题，它通过限制搜索空间来提高效率，通常不会找到所有解。
5. 复杂度：
1. 回溯法：回溯法的时间复杂度通常较高，因为它需要穷尽所有可能的解，搜索空间较大。
2. 分支限界法：分支限界法通常具有较低的时间复杂度，因为它通过剪枝和启发式策略有选择地探索子问题。

7.8、两种常见的分支限界法

1. 队列式分支限界法
1. 按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。
2. 从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同。
2. 优先队列分支限界法（代价最小或效益最大）

• 每个结点都有一个对应的耗费或收益，以此决定结点的优先级。
• 从优先队列中选取优先级最高的结点成为当前扩展结点。
• 如果查找一个具有最小耗费的解：则活结点表可用小顶堆来建立，下一个扩展结点就是具有最小耗费的活结点。
• 如果希望搜索一个具有最大收益的解：则可用大顶堆来构造活结点表，下一个扩展结点是具有最大收益的活结点。