回溯法 - 回溯法-课件（PPT精）.ppt

1
第5章回溯法
2
算法回顾
递归 recursion
两个步骤:定边界条件,调用自身
分治法 divide and conquer
三个步骤:分,治,合
动态规划dynamic programing
确定最优解性质,递归定义最有值,自底向上计算。
3
动态规划 dynamic programing
之二备忘录方式(与分治法的区别在于有子问题有重叠。)
分,查,治,存,合
贪心算法 greedy algorithm
选择目前最优的情况
4
回溯法简介
有“通用解题法”之称,将所有的解(问题的解空间)按照一定结构排列,再进行搜索。
一般解空间构造成为为树状结构,用深度优先的策略搜索
两种方式:
只需要一个解的话,找到解就停止
需要求所有解,则需做“树的遍历”找到所有解。
通常用排除法,减少搜索空间
5
回溯法
用处:有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
6
引子:0/1背包问题
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
7
回溯法解0/1背包问题
例子: n=3
w=[16,15,15]
p=[45,25,25], c=30
1)思考所有可能的解
2)将解组织成一个结构,以便搜索。(树状结构)
此结构为解空间
8
n=3时的0-1背包问题用完全二叉树表示的解空间
9
求解过程:
也就是树的遍历的过程。
深度优先搜索DFS。
排除不符合条件的子树。
从根到叶节点为一个解。
回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法
10
生成问题状态的基本方法
扩展结点:当前正在处理的节点
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法:如果对一个扩展结点R,一旦产生了它的一个儿子C,就把C当做新的扩展结点。在完成对子树C(以C为根的子树)的穷尽搜索之后,将R重新变成扩展结点,继续生成R的下一个儿子(如果存在)