回溯算法
回溯算法
思想
-
以深度优先方式系统搜索解的算法称为回溯算法
- 求问题的所有解时，需要遍历完根节点的所有子树并回溯到根节点。
- 求问题的一个解时，只要搜索到问题的一个解就结束。
-
回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
-
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类
- 使用约束函数，剪去不满足约束条件的路径
- 使用限界函数，剪去不能得到最优解的路径。
-
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。
特点
- 系统性：查看所有结点
- 跳跃性：如果有的结点不满足剪枝函数，就不用查看
零碎知识点
- 回溯法的解通常用向量表示，（x1，x2…xn），x[i]表示第i次选择所做的决策值。
- 回溯法是穷举法的改进。
- 解空间树2种，子集树和排序树，具体参考<<算法设计与分析>>第四版王晓东Page 119。下图种01-背包不用考虑物品的顺序，所以是子集树，而城市旅行有顺序，所以是排列树。
用回溯法解决问题步骤
- 首先判断是否能用回溯法，回溯法一般可用于所有问题，称为“通用解题法”。
- 解可以用向量表示就可以用回溯法。
- 如0-1背包的解（x1,x2…xn）xi∈{0，1} xi=0表示不装
- 判断解空间树的类型。
- 套用算法框架，参考<<算法设计与分析>>第四版王晓东Page 119。
- 描述约束函数C(i)和限界函数B(i)。
- 是否构造最优解，因为可行解，最优解都可能有多个。
子集树
- 解是一个向量(x1,x2,x3…)
- 如图x1的解在S1中，x2的解在所有S2中，以此类推
排列树
（例子）货箱装载问题
问题
- 与0-1背包不同不需要考虑价值，只要考虑重量。
问题描述
- 总重量不超过W（船的载量）
子集树
- 1表示放该物品，0表示不放，一共有2^4=16种解。
- 如最左边的一棵子(集)树，（x1,x2,x3,x4）= (1,1,1,1)，表示x1-4都放。
- 注意此时放没放不看结点，而看结点间的线路值，绿点表示没放，绿点的左孩子结点表示放了x1，因为此时线路值为1。
约束函数
- 判断到一个结点，当该结点之前的结点重量和+自己的重量>W时，就不用判断该结点的子树了。
限界函数
-
用来求最优解
-
如果之前放入的重量+剩下所有还没有放入的重量和 < 前面的可行解的重量，则表示前面可行解就是最优解，就不用判断此子树。