回溯和分支算法

状态空间图

“图”——状态空间图

• 例子：农夫过河问题——“图”=状态+操作
• 例子：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）
• 圆排列问题
• 连续邮资问题

明天更新这些问题的解法和思路