回溯算法的简单描述

# JJU_干干

1. 回溯的思想：

• 回溯是穷举方法的一个改进，它在所有可行的选择中系统地搜索问题的解。假定解可以有向量的形式（x1,x2,...,xn）来表示，其中x_i的值表示：在第i次选择所作出的决策值，并以深度优先的方式遍历向量空间，逐步确定X_i的值，直到解被找到。
• 回溯法会列举出解空间中所有可能的情形来确保解的正确性
• 假设我们已经确定部分解的集合（x1,x2,...,xi），在此基础上通过增加元素 X_i+1 来扩展解，确定 X_i+1 的值后，我们要测试（x1,x2,...,xi,xi+1）是否仍是可行解。

2. 回溯算法的基本步骤：

1. 定义问题的解空间。（这个空间必须包含一个问题的最优解）；（如果Si 是 xi 的范围，那么S1 * S2 *...* Sn 是问题的解空间）
2. 组织好解空间以便使搜索更容易。（典型的组织方式是利用图或树的结构）
3. 以深度优先的方式搜索解空间，利用剪枝函数来避免搜索进入不可能得到的子空间。

3. 生成问题状态的基本方法

• 扩展结点：一个正在产生儿子的结点
• 活结点：一个自身已生成但其儿子还没有全部生成的结点
• 死结点：一个所有儿子已经产生的结点

4. 一句话描述回溯法：为了避免生成那些不可能产生最佳解的问题的状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。（具有限界函数的深度优先生成法称为回溯法）

5. 解空间的组织：

• 任何时候，在构造问题解的时候，都包含做出一系列的决策，如果我们将做出的决策画出来，这个图像就像一棵树。建立一棵树型结构，使得树叶对应解空间的一个解，而内部结点的一个分支，对应一个决策，这样便可以将解空间组织为一棵解空间树。
• 回溯法可以很容易地被用来搜索一个集合的所有子集合或是排列。
• 当我们要解决的问题是要求一个使问题最优的n个元素的子集，问题的解空间常可以组织成一棵子集树。（如果每个Si的大小是K，对每个xi 属于 Si ，共有 K^n 个子集）
• 当问题是求n个元素一个排列以使问题最优化时，解空间常可以组织成一棵排列树。

6. 剪枝函数：

• 剪枝函数一般分为：约束函数、限界函数
• 利用剪枝函数剪除无效的分支，从而集中搜索最有用的分支
• 为了改进搜索，应用回溯算法至少需要注意一下四点：

1. 怎样选择约束函数
2. 怎样计算上界（对于最大化问题而言）
3. 怎样计算下界（对于最小化问题而言）
4. 怎样利用约束函数和限界函数来进行剪枝

• 通常对于极大值问题，我们对扩展结点（扩展结点：一个正在产生儿子的结点） i 计算下界 B(i)。如果目前保存的最大目标值不比 B(i) 大，那么进行剪枝，否则继续。
• 通常对于极小值问题，我们对扩展结点 i 计算上界 B(i) 。如果目前保存的最小目标值不比 B(i)小，那么进行剪枝，否则继续。