回溯算法的设计与实现

几个回溯算法的例子

4后问题

0-1背包问题

问题：
有n种物品，每种物品只有 1个. 第i 种物品价值为 $v_i$vi​ , 重量为 $w_i$wi​ , i =1,2,…, n.问如何选择放入背包的物品，使得总重量不超过 B, 而价值达到最大？
实例：
V={12,11,9,8}, W={8,6,4,3}, B=13
最优解：
<0,1,1,1>，价值: 28，重量: 13

算法设计

解：n维0-1向量$<x_1, x_2, ..., x_n>$<x1​,x2​,...,xn​>，
xi =1⇔物品 i 选入背包

结点：$<x_1, x_2,..., x_k>$<x1​,x2​,...,xk​>（部分向量）
搜索空间：0-1取值的二叉树, 称为
子集树，有$2^n$2n片树叶.
可行解:满足约束条件 $\sum_{i=1}^n w_ix_i \leq B$∑i=1n​wi​xi​≤B的解
最优解:可行解中价值达到最大的解

实例

输入：
V={12,11,9,8}, W={8,6,4,3}, B=13

2个可行解：
<0,1,1,1>, 选入物品2,3,4，价值为28，重量为13
<1,0,1,0>，选入物品1,3，价值为21，重量为12
最优解： <0,1,1,1>

小结
• 回朔算法的例子：n后问题，0-1背包问题，货郎问题
• 解：向量

• 搜索空间：树，可能是n叉树、子集树、排列树等等，树的结点对应于部分向量，可行解在叶结点

• 搜索方法：深度优先, 宽度优先, …
跳越式遍历搜索树，找到解

回溯算法的设计思想和适用条件

回溯算法基本思想

(1) 适用：求解搜索问题和优化问题.
(2) 搜索空间：树，结点对应部分解向量，可行解在树叶上.
(3) 搜索过程：采用系统的方法隐含遍历搜索树.
(4) 搜索策略：深度优先，宽度优先，函数优先，宽深结合等.
(5) 结点分支判定条件：
满足约束条件—分支扩张解向量不满足约束条件，回溯到该结点的父结点.
(6) 结点状态：动态生成
白结点(尚未访问)
灰结点(正在访问该结点为根的子树)
黑结点(该结点为根的子树遍历完成)
(7) 存储：当前路径

小结

• 回溯算法的适用条件：
多米诺性质

• 回溯算法的设计步骤
(1) 定义解向量和每个分量的取值范围
解向量 为 $< x_1, x_2, …,x_n>$<x1​,x2​,…,xn​>
确定 $x_i$xi​ 的取值集合为 $X_i$Xi​ , i =1,2,…, n.
(2) 在$<x_1,x_2,…,x_{k-1}>$<x1​,x2​,…,xk−1​>确定如何计算 xk取值
集合$S_k, S_k ⊆ X_k$Sk​,Sk​⊆Xk​
(3) 确定结点儿子的排列规则
(4) 判断是否满足多米诺性质
(5) 确定每个结点分支的约束条件
(6) 确定搜索策略: 深度优先,宽度优先等
(7) 确定存储搜索路径的数据结构

回溯算法的实现及实例

回溯算法递归实现

小结

• 回溯算法的实现：
递归实现、迭代实现
• 装载问题
问题描述
算法伪码
最坏情况下时间复杂度O($2^n$2n)