回溯法的本质
-
具有限界函数的深度优先搜索法
-
扩展结点：一个正在产生儿子的结点称为扩展结点
-
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
-
死结点：一个所有儿子已经产生的结点称做死结点
回溯法的例子
0-1背包问题：
一个0-1背包问题定义如下： n=3, c=7, w={4,3,2}, v={3,4,3} （这个问题可以用回溯法解决，可以用约束函数和限界函数剪枝以提高搜索效率。）
给出： 搜索该解空间树时，扩展结点访问过程 最优值和最优解
剪枝的条件：
- 目前已有的重量加下个节点的重量超过背包容量，则剪去
- 剩余的物品的价值补比bestv大，则剪去
更新bestv的条件：
- 当前拓展节点为叶子节点，则更新bestv和bestx
答案：
扩展结点访问过程如下：初始bestv=0，下表中的 r 表示剩余的物品的价值，若剩余的价值不比bestv大，则剪去改节点。
| t | 扩展结点 | sw | sv | 剪枝函数 |
|---|---|---|---|---|
| 1 | A | 0 | 0 | sw+w[t]=0+4<=C |
| 2 | B | 4 | 3 | sw+w[t]=4+3<=C |
| 3 | D | 7 | 7 | sw+w[t]=7+2>C，剪去H,r=0,r+sv=0+7>bestv |
| 4 | I | 7 | 7 | 叶子结点，sv>bestv，更新bestv,bestv=sv=7, bestx=[1,1,0] |
| 2 | B | 4 | 3 | r=3,r+sv=3+4<=bestv，剪去E |
| 1 | A | 0 | 0 | r=7,r+sv=7<=bestv，剪去C |
最优值为7，即背包中物品最大价值为7 最优解为[1,1,0]，即物品1，物品2放入背包中
5皇后问题：
使用回溯法解决5皇后问题时，x=[5, 3, 1, 4, 2]是该问题的一个解
问题： 假设搜索从t=1, x[t]=5开始，直到找到x =[5, 3, 1, 4, 2]时结束 按照算法的搜索顺序，给出满足约束条件时，搜索深度t和x[t]的所有值
答案： 简写成(t, x[t])的形式： (1,5), (2,1), (3,4), (2,2), (3,4), (4,1), (5,3), (2,3), (3,1), (4,4), (5,2)
