9算法第九章分枝限界法.ppt

证明： 已知若T有限且存在答案结点，LC一定能找到一个答案结点。下面证明满足已知条件时，LC能找到最小成本答案结点。 定理9.2 在有限状态空间树T中，对于每一个结点X，令?(X)是c(X)的估计值且具有以下性质：对于每一对结点Y、Z，当且仅当c(Y)c(Z)时有?(Y) ?(Z)。那么在使?作为c的估计值时，算法LC到达一个最小的成本答案结点且终止。 * 假设LC在G处终止，c(G)c(G’)。 找到距离G和G’最近的共同祖先R。 R到G’的路径为R、 α1、… αk、G’。 R到G的路径为R、β1、… βj、G。 若能检索到G，则R必在某时间成为E-结点。 子结点α1和β1成为活结点。 … … αk βj G’ G 最小成本答案结点 答案结点 E R α1 β1 α2 β2 c(R)=c(α1)=…=c(αk)= c(G’) c(β1)=…=c(βk)=c(G)c(G’) ?(β1)? (G’), ?(αk),…, ?(α1) 在αi(1≤i ≤k)变成E结点并到达G’之前，β1不能变成E-结点，与假设矛盾，命题得证。 * 对定理9.2的使用 该定理易于推广到每个结点的度都是有限的无限状态空间树的情况。 得到满足定理9.2的要求，又易于计算的?(.)通常是不可能的。 一般只可能找到一个易于计算且具有如下特性的?(.)：对于每一个结点X，有?(X) ? c(X)且对于答案结点X有?(X) = c(X)。这显然不能保证算法LC找到最小成本答案结点。 因此将算法LC修改为LC1 * 算法9.2 找最小成本答案结点的LC-检索 line procedure LC1(T, ?) E←T 将活结点表初始化为空 loop if E是答案结点 then 输出从E到T的那条路径; return endif for E的每个儿子X do call ADD(X)；PARENT(X)←E repeat if 不再有活结点 then print(“no answer node”); stop endif call LEAST(E) repeat end LC1 //为找出最小成本答案结点检索T E由LEAST方法筛选，从活结点表里选择?最小的 算法9.1可能选到第一个合适的儿子结点，算法9.2选中成本最小的儿子结点。 例子 * 定理9.3 令?是满足如下条件的函数，在状态空间树T中，对于每一个结点X，有?(X)≤c(X) ，而对于T中的每一个答案结点X，有?(X)=c(X)。如果算法在第5行终止，则所找到的答案结点是具有最小成本的答案结点。 证明：在第4步，结点E是答案结点，对于活结点表中的每一个结点L，一定有?(E)≤?(L)。由假设?(E)=c(E)且对于每一个活结点L，?(L)≤c(L) ，从而c(E)≤c(L)，E是一个最小成本答案结点，证毕。 * 9.1.5 分枝-限界算法 基本思想：在生成当前E-结点的所有儿子结点之后再选择另一个结点变成E-结点。 分支-限界法怎样找最小成本的答案节点? 智能优化：设置一个成本估算函数?(X)，给出经由结点X到达答案结点的成本下界，?(X)≤c(X)。 进一步加速：还可以设置一个最小成本上界U，U也可能恰好就是成本值。 * 最小成本上界U U的初始值： 启发性方法得到，或∞； U的初始值≥最小成本答案结点的成本； U的更改: 每找到一个新的答案结点就可以修改U的值。 U的使用: 若U是最小成本的上界,则具有?(X)U的所有活结点X可以被杀死; 若U是一个成本值, ?(X)=U的所有活结点X可以被杀死. * 1) 改变极大化问题的目标函数，使问题转化为极小化问题 2) 把目标函数作为成本函数c 3) 约束条件作为限界函数 4) 问题转化为寻找状态空间树中使成本函数c取极小值的答案结点 5) 设计成本估计函数?(X)，?(X)≤c(X)(,还设计最小成本的上界U) 6) 基于?(X)(和U)进行LC分枝-限界法有哪些信誉好的足球投注网站 如何用分枝-限界法求解最优化问题？ * 带期限的作业排序问题 一个最优化问题的例子 假设有n个作业和一台处理机，每个作业i由一个三元组(pi,di,ti)表示，表示作业需要ti个时间处理完毕，如果在期限di之前没有完成则要交付pi的罚款。 问题目标：从这n个作业中选取一个子集合J，使J中作业都能在相应的期限内完成且不在J中的作业罚款总数最小。 * 一个作业实例 n=4;(p1,d1,t1)=(5,1,1);(p2,d2,t2)=(10,3,2); (p3,d3,t3)=(6,2,1);(p4,d4,t4)=(3,1,1); 解空间的表示