第16章回溯(简化).pptVIP

第16章 回溯 16.1 有哪些信誉好的足球投注网站问题的形式化-解空间 假定问题的解能用n-元组(X1,…,Xn),表示,其中Xi取自某个有穷集Si. 这些n-元组构成的集合称为问题的解空间. 假设|Si|=mi, 则解空间的大小为m=m1m2…mn. 我们考虑两类问题: 存在性问题是: 求满足某些条件的一个或全部元组. 如果找到了这样的元组算法返回Yes,否则返回No. 优化问题: 给定一组约束条件, 在满足约束条件的元组中求使某目标函数达到最大（小）值的元组. 满足约束条件的元组称为问题的可行（feasible）解. 16.1 有哪些信誉好的足球投注网站问题的形式化 解决这类问题的最一般方法是使用有哪些信誉好的足球投注网站技术,即系统化的有哪些信誉好的足球投注网站解空间的技术.回溯法和分支限界法就是这样的有哪些信誉好的足球投注网站技术,本章介绍回溯法,下章介绍分支限界法. 16.2 解空间的状态空间树 任何有哪些信誉好的足球投注网站算法都可以用建立在解空间上的状态空间树加以描述. 状态空间树是我们尝试选择解空间元组的各个分量时产生的树结构. 有哪些信誉好的足球投注网站算法建立在遍历状态空间树的算法基础上. 但有哪些信誉好的足球投注网站算法并非事先将状态空间树存在计算机内再进行遍历,而是通过展开状态空间树来找所求的解. 展开过程中通过使用启发式的限界方法(剪去状态空间树上的某些分枝) 使有哪些信誉好的足球投注网站算法只展开状态空间树的一部分, 从而降低有哪些信誉好的足球投注网站算法的时间和空间复杂度. 有关状态空间树的术语 状态空间树的每个结点代表问题求解过程中的一个中间状态,根节点到它的路径代表元组的部分分量已作出的选择. 状态空间树的所有节点构成求解该问题的状态空间. 根节点到状态空间树的一个节点X的路径可以表示为(x(1),…,x(k)), 其中x(i), 1≤i≤k,为有哪些信誉好的足球投注网站过程中已经选择的分量. 今后我们也用这个元组标识该节点: X= (x(1),…,x(k)). (x(1),…,x(k))也对应一个子问题:在后面n-k个元组的分量所对应的子空间里找满足要求的解. 该子空间是状态空间树中以X为根的子树. 所以也称节点X为问题节点. 如果X为叶节点,则根到X的路径完全确定了解空间的一个元组, 称叶结点为状态空间树的一个解节点. 如果一个解节点满足约束条件称其为答案节点,对应一个可行解. 16.3 状态空间树的展开方法 每个有哪些信誉好的足球投注网站算法都是一种系统化地展开状态空间树的方法. 我们借助以下术语描述展开状态空间树的不同方法. 活结点: 已展开了部分子节点, 但所有子结点尚未全部展开的结点. 死结点:被限界或已展开了所有子结点的结点. E-结点: 当前正在展开子结点的活结点. 状态空间树的展开方法 深度优先展开方法: 一个E-结点展开自己的一个子结点后, 就让该子结点成为E-结点的展开方法. 广度优先展开方法:一个结点一旦成为E-结点就展开自己的全部子节点的展开方法. 限界(Bounding) 设X=(x(1),x(2),…,x(i-1))是状态空间树中一个节点, T(x(1),x(2),…,x(i-1))表示x(i)所有可能的取值的集合. 设x(i)∈T(x(1),x(2),…,x(i-1))则Y=(x(1),…,x(i))是状态空间树上X的一个子节点. 限界函数Bi(x(1),…,x(i)) 表示一个条件: Bi(x(1),…,x(i)) 为true当且仅当从Y展开的子树不包含答案结点. 这时有哪些信誉好的足球投注网站算法停止展开结点Y及其子树, 称为限界或“kill”这个节点. 限界函数从分析约束条件或优化的要求得到. 要求计算限界函数的算法有多项式的时间复杂度. 回溯法: 加限界的深度优先展开状态空间树的方法称为回溯法. 分枝－限界法: 加限界的广度优先展开状态空间树的方法称为分枝－限界法. 在分枝－限界法中要维护一个称为活结点表的结构, 存放已展开的但还未成为E结点的那些结点. 回溯法只需存储状态空间树的一条路径;分枝－限界法在最坏情形可能要存储整个状态空间树. 16.2 应用 货箱装船 0/1背包问题 1 货箱装船问题 装船问题：给定载重量c的货船和n个集装箱,其重量为w(1),…,w(n)找一种装船的方法,使得装载的货箱重量最大. 等价的优化问题 装船问题：给定载重量c的货船和n个集装箱,其重量为w(1),…,w(n)找一种装船的方法,使得装载的货箱重量最大 装船问题的形式化描述如下： Maxmize ∑w(i)x(i) Subject to ∑w(i)x(i)≤c 这是特殊的一类背包问题：pi=wi.可用动态规划求解 下面用回溯法求解： 例题 假定n= 4,w= [ 8 , 6 , 2 , 3 ],c1 = 12.状态空间树 在节点X=(x(1),…,x(i-1))处 限界方法1：令cw为当前已装