回溯和分支算法
状态空间图
“图”——状态空间图
- 例子：农夫过河问题——“图”=状态+操作
- 例子：n后问题、0-1背包问题、货郎问题(TSP)
用向量表示解，“图”由解向量扩张得到的解空间树。 ——三种图：n叉树、子集树、排序树
剪枝 不满住条件的进行裁剪
优化 剪枝！ 回溯：DFS+剪枝；分支限界：BFS+剪枝
实例
-
0-1背包问题的一个实例
- 给定n=3种物品和一背包。物品W=<16,15,15>，其价值为V=<45,25,25>， 背包的容量为B=30。问应如何选择装入背包的物品，使得装入背包中物品的 总价值最大?
每一层代表第几件物品装不装，来进行剪纸
-
货郎问题(TSP)
- 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一 条从驻地出发，经过每个城市一遍，最后回到住地的路线。目标是使总的 路程最短。
* 解释：先1 2 3 4 得到BestV = 14 然后在选完2的时候可以选4 但其值加起来大于14 直接舍弃，同理1，3也一样 - 可以用对称性来做
- 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一 条从驻地出发，经过每个城市一遍，最后回到住地的路线。目标是使总的 路程最短。
-
回溯法小结
- 1.针对所给问题，定义问题的状态空间图
- 2.深度优先搜索，并用剪枝策略避免无效搜索
——剪枝策略包括约束函数和限界函数。
——对背包问题，左孩子结点扩张需要检查约束函数，右孩子扩张需要检 查限界函数
➢分支限界
- 以0-1背包问题例
- 广度优先，注意剪枝策略
步骤总结
- 1.针对所给问题，定义问题的状态空间图
- 2.广度优先搜索，并用剪枝策略避免无效搜索 ——扩展结点，一次性生成她的所有孩子结点。
——需要判断孩子结点是舍弃还是保留，舍弃不可行、不能能最优的孩子 结点，其余的结点进入队列中。这样可以避免不必要的搜索。 ——剪枝策略包括约束函数和限界函数
回溯与分支限界
- 适用条件——多米诺性质 *
- 必要条件：多米诺性质
* 理解：**p（x1，x2,x3,…xn）满足>10 即p（x1，x2,x3,…xn-1）也满足>10 **
- 必要条件：多米诺性质
- 主要步骤及递归和迭代的实现
- 一种效率分析方法——Monte Calo方法
- 剪枝的进一步细化——以0-1背包问题为例
主要步骤及递归和迭代的实现
-
子集树
-
排列树
➢ 0-1背包问题的一个实例 -
给定n种物品的重量价值和一背包，背包的容量为B，每种物品只能装入一次。
-
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
-
记录：已有重量（约束）、已有价值（目标、界）
-
现在的要点是，继续优化剪枝策略。
-
还有没有其他的？
-
引入界函数和代价函数。
➢ 界函数
- 代表当时已经得到的可行解的目标函数的最大值
- 界的设定初值可以设为 0
- 可行解的目标函数值大于当时的界，进行更新
➢ 代价函数
- 函数值以该结点为根的搜索树中的所有可行解的目标函数值的上界
- 父结点的代价不小于子结点的代价
➢ 搜索中停止分支的依据
- 不满足约束条件或者其代价函数小于当时的界
- 已有价值==已有界
- 代价函数 === 可能的最大的已有价值 代价函数 得变
典型例子
- 装载问题
* 实例
- 图的m着色问题
- 背包问题
- 最大团问题
- 货郎问题（TSP）
- 圆排列问题
- 连续邮资问题
明天更新这些问题的解法和思路
