最新第6章-限界剪枝法教学讲义PPT课件.ppt

《最新第6章-限界剪枝法教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章-限界剪枝法第六章分支限界法本章主要知识点6.1分支限界法的基本思想6.2单源最短路径问题6.3装载问题6.4布线问题6.50－1背包问题6.6最大团问题6.7旅行售货员问题6.8电路板排列问题6.9批处理作业调度2一限界剪枝法的基本思想1.限界剪枝法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。二最小耗费搜索法xxy2y1D

2、(y2)C(x)=min{D(y)

3、y∈Tx∩A}D(y1)C(x)=∞最小耗费搜索法10512714917最小耗费搜索法1051271491755∞1499∞145∞1010∞∞5∞∞∞最小耗费搜索法下界估值函数~C(x)~C(x)是C(x)的下界估值~C(x)可即时计算当x为解结点时，~C(x)=C(x)=D(x)下界估值越小，分枝含有最优解的可能越大。优先搜索下界估值最小的结点，则第一个待扩展的解结点为最优解。最小耗费搜索法最小耗费搜索法最小耗费搜索法的算法描述设T为状态空间树的根结点；~C(x)为耗费估计函数；初始化优先队列Q；计算~C(T)，并将T入队；循环，直到队列Q空（无

4、解）：结点e出队；若e是回答结点，则输出解或求解路径，求解结束；否则检查e的所有子结点x：若x满足约束条件，则计算~C(x)，并将x入队；记录搜索路径；当~C(x)满足：~C(x)≤C(x)，C(x)单调，解结点的~C(x)=C(x)时，上述算法可以正确找到C(x)的最小耗费解；对活结点表中的任一结点x，有~C(e)≤~C(x)，对x分枝中的任一解结点y，有~C(x)≤C(y)=D(y)，又知：~C(e)=C(e)=D(e)，则D(e)≤D(y)。最小耗费搜索法最小耗费搜索法15迷问题用布局作为问题状态，用空格的移动来表述状态的演化；用根结点到解结点的路径长度作为耗费函数；而用根到当前

5、结点的路径长度加上当前结点与目标解的差异量作为耗费估计函数；131098141167125215431151413121110987654321最小耗费搜索法最小耗费搜索法15迷问题布局结构描述布局结点不仅包括数字位的分布情况，还包括已经推演的步数和与目标布局的差异，以及指向父结点的指针。算法描述初始化集合S={}，记录曾经出现过的布局；初始化优先队列Q，以布局的~C(x)作为权值；起始布局入队，并记入S；循环，直至队列空布局T出队；若T为目标布局，则从T倒推出移动步骤，求解结束；将T的所有未处理的可推演布局入队，并记入S；procedureLC(T,C)(EMPTY(Q)在Q为空时返

6、回true，否则返回false。)beginifT的根是一个回答结点then输出T的根elsebeginMAKENULL(Q);计算C（T）’;INSERT(T,Q);whilenotEMPTY(Q)dobegine:=DELETEMIN(Q)；fore的每个儿子结点xdoifx满足约束条件thenbeginifx是回答结点thenbegin输出从T到x的逆路径;return;end；计算C(x)＇；INSERT(x,Q);x↑.parent=e;end;end；print“没有回答结点”end;end；在找到一个回答结点或当整个状态空间树被搜索完，算法LC(T，C)才终止。对算法LC

7、作适当修改，可以使算法在找到一个最小C(x)回答结点时结束。下面的算法LCl(T，C)是经过修改后的算法，它的终止条件改为当前扩展结点是一个回答结点。procedureLC1(T,C’)beginMAKENULL(Q)；计算C(T)’；INSERT(T,Q)；whilenotEMPTY(Q)dobegine:=DELETEMIN(Q)；ife是回答结点thenbegin输出从T到e的逆路径；return；end；fore的每一个儿子结点doifx满足约束条件thenbegin计算C(x)‘；INSERT(x,Q)；x↑.parent:=e；end；end；print“没有回答结点”；e

8、nd；三限界剪枝法限界与剪枝在解结点集合上定义目标函数F(x)，求解解结点集上的离散最优化问题；类似最小耗费搜索法，定义耗费函数C(x)：C(x)=min{D(y)

9、y∈Tx∩A}Tx∩A≠{}C(x)=∞Tx∩A={}C(x)为单调非减函数；同样地，由于C(x)无法做即时计算，引入估值函数~C(x)，满足条件：~C(x)≤C(x)；对解结点x，~C(x)=C(x)；限界剪枝法限界与剪枝为了进一步避免无效搜索，若能找到最优解的耗费上界U，即