资源描述：
《第七讲-分枝限界法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法设计与分析第七讲分枝限界法算法设计与分析第七讲分枝限界法主要内容FIFO宽度优先检索LIFO宽度优先检索LC检索原理LC,FIFO分枝限界算法重点LC检索原理与分枝限界算法的设计思想难点限界函数设计算法设计与分析第七讲分枝限界法回溯法特点回顾2)深度优先的状态空间树扩展3)用规范函数判断不可抵达答案节点的节点4)终止对某节点的扩展时,生成一个兄弟节点或回溯1)用状态空间树的扩展描述解向量的分级求解算法设计与分析第七讲分枝限界法K1312376819182021109112223412142425
2、5161517262728293031KKKKKKKKKKKKKK答案节点1234x2=34134124123x3=x4=4x1=222313242331337.1状态空间树的宽度优先扩展方法例7.14皇后问题的状态空间树宽度优先扩展算法设计与分析第七讲分枝限界法简单分枝限界算法的分类1)FIFO分枝限界法2)LIFO分枝限界法（D检索）FIFO,LIFO分枝限界法的缺陷从活节点表中选择活节点存在盲目性算法设计与分析第七讲分枝限界法7.2最小成本(LC:leastcost)检索一、节点成本函数c(X
3、)表示可能导致抵达答案节点的活节点的成本，定义如下：如果X是答案节点,则c(X)是由根节点到答案节点的成本；如果X不是答案节点,且子树X不包含任何答案节点,则c(X)=∞，否则,c(X)等于子树X中具有最小成本的答案节点的成本。精确计算c(X)的复杂度,等价于求解原问题的复杂度算法设计与分析第七讲分枝限界法二、检索成本的估计用成本估计函数g(x)估计c(x)的值不恰当的g(x)可能导致纵深检索1234567c(x)=0g(x)=0111098109126137145改进的节点成本估计函数:c’(X)
4、=f(X)+g(X)其中，f(X)表示由根节点到X检索的成本的非降函数。算法设计与分析第七讲分枝限界法三、成本估计函数的构造初始状态数:16!≈20.9×1012例7.215迷问题13415251276111489101312345678910111213141512345678910111213141516可达状态数:约为初始状态数的一半初始状态的状态空间算法设计与分析第七讲分枝限界法P(I)：令第I号牌的位置L(I):JP(I)的牌数目标状态判定方法为偶数时,目标状态可由初始状态
5、到达.定理1如图(b)所示,阴影格X=1,否则X=0,当且仅当134152512761114891013(a)(b)算法设计与分析第七讲分枝限界法15迷问题的成本估计函数c’(X)=f(X)+g(X)f(X):根节点到X的路径长度；g(X):不在目标位置的非空白牌数.算法设计与分析第七讲分枝限界法c’(2)=1+4c’(3)=1+4c’(4)=1+2c’(5)=1+4c’(10)=2+1c’(11)=2+3c’(12)=2+3141023算法设计与分析第七讲分枝限界法四、LC检索LC检索定义:…1）
6、g(X)=0,f(X)=X的级数2）f(X)=0,且每当Y是X的儿子时g(X)≥g(Y)两个特例:1）具有启发性且易于计算2）当X为叶节点或答案节点时,要求c’(X)=c(X)成功找到答案节点的必要条件：算法设计与分析第七讲分枝限界法LC(TREET,FUNC(*c)(NODEX)){if(T是答案节点){printf(T);return;}ActiveList=φ;E=T;while(1){for(E的每个儿子X){if(X是答案节点){printf(X到T路径上的节点);return;}(*c)
7、(X);AddToActiveList(X);Parent(X)=E;}if(ActiveList==φ){printf(“无答案节点”);break;}DeleteLeastCost(E)}}检索答案节点的LC算法算法设计与分析第七讲分枝限界法存在的问题：不保证找到有最小成本的答案节点100123564720210420201010∞∞∞∞定理2:在有限状态空间树T中,对每一个节点X,令c’(X)是c(X)的估计值,对每一对节点Y,Z,当且仅当c(Y)8、到达一个最小成本答案节点且终止。算法设计与分析第七讲分枝限界法当c’(X)≤c(X),且答案节点的c(X)=c’(X)——检索最小成本答案节点的LC算法LC1(TREET,FUNC(*c)(NODEX)){ActiveList=φ;E=T;while(1){if(E是答案节点){printf(E到T路径上的节点);return;}for(E的每个儿子X){(*c)(X);AddToActiveList(X);Parent(X)=E;}if(ActiveList==φ)
