第11讲分支限界法详解.ppt

FIFO限界有哪些信誉好的足球投注网站过程为： 大连海事大学 1）? 初始队列中只有结点A； 2）? 结点A变为E-结点扩充B入队，bestw=10； 结点C的装载上界为30+50=80 bestw，也入队； 3）? 结点B变为E-结点扩充D入队，bestw=40； 结点E的装载上界为60 bestw，也入队； 4）? 结点C变为E-结点扩充F入队，bestw仍为40； 结点G的装载上界为50 bestw，也入队； 5）? 结点D变为E-结点，叶结点H超过容量， 叶结点I的装载为40，bestw仍为40； 6）? 结点E变为E-结点，叶结点J装载量为60，bestw为60； 叶结点K被剪掉； 7）? 结点F变为E-结点，叶结点L超过容量，bestw为60； 叶结点M被剪掉； 8）? 结点G变为E-结点，叶结点N、O都被剪掉； 此时队列空算法结束。 LC-有哪些信誉好的足球投注网站的过程如下： 大连海事大学 1）? 初始队列中只有结点A； 2）? 结点A变为E-结点扩充B入堆，bestw=10； 结点C的装载上界为30+50=80 bestw，也入堆；堆中B上界为90在优先队列首。 3）? 结点B变为E-结点扩充D入堆，bestw=40； 结点E的装载上界为60 bestw，也入堆；此时堆中D上界为90为优先队列首。 4）? 结点D变为E-结点，叶结点H超过容量，叶结点I的装载为40入堆， bestw仍为40；此时堆中C上界为80为优先队列首。 5）? 结点C变为E-结点扩充F入堆，bestw仍为40； 结点G的装载上界为50 bestw，也入堆；此时堆中E上界为60为优先队列首。 6）? 结点E变为E-结点，叶结点J装载量为60入堆，bestw变为60； 叶结点K上界为10bestw被剪掉；此时堆中J上界为60为优先队列首。 7）? 结点J变为E-结点，扩展的层次为4算法结束。 虽然此时堆并不空，但可以确定已找到了最优解。 大连海事大学 FIFO限界算法有哪些信誉好的足球投注网站解空间的过程是按图5-26子集树中字母序进行的，而优先队列限界有哪些信誉好的足球投注网站解空间的过程是： A-B-D-C-E-J 看了上面的例子大家会发现，优先队列法扩展结点的过程，一开始实际是在进行类似“深度优先”的有哪些信誉好的足球投注网站。 5．5．3 算法框架 上一小节的例子是求最大值的最优化问题，下面我们以求找最小成本的最优化问题，给出FIFO分支有哪些信誉好的足球投注网站算法框架。 假定问题解空间树为T，T至少包含一个解结点（即答案结点）。u为当前的最优解，初值为一个较大的数;E表示当前扩展的活结点，x为E的儿子，s(x)为结点x下界函数，当其值比u大时，不可能为最优解，不继续有哪些信誉好的足球投注网站此分支，该结点不入队；当其值比u小时，可能达到最优解，继续有哪些信誉好的足球投注网站此分支，该结点入队；cost（X）为当前叶结点所在分支的解。 算法框架如下： 大连海事大学 2）： 大连海事大学 search（T） //为找出最小成本答案结点检索T。?{leaf=0;  初始化队； ADDQ（T）； //根结点入队 parent（E）=0； //记录扩展路径，当前结点的父结点 while （队不空） {DELETEQ(E) //队首结点出队为新的E结点； for （E的每个儿子 X）????? if (s（X）u) //当是可能的最优解时入队 {ADD Q（X）； parent（X）=E;  ??? ??? if (X是解结点 ) //x为叶结点 ?????? ?{U=min（cost（X），u）;?????????? ?leaf=x;} //方案的叶结点存储在leaf中 } } 3）： 大连海事大学 ?print（”least cost=’，u）；???while （leaf0） //输出最优解方案?????? {print（leaf）；??????? leaf=parent（leaf）；}} 大连海事大学 找最小成本的LC分支-限界算法框架与?FIFO分支-限界算法框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点的数据结构不同。?FIFO分支-限界算法用队存储活结点，LC分支-限界算法用堆存储活结点，以保证比较优良的结点先被扩展。且对于LC分支-限界算法，一当扩展到叶结点就已经找到最优解，可以停止有哪些信誉好的足球投注网站。 5．6 图的有哪些信誉好的足球投注网站算法小结 大连海事大学 1．深度优先有哪些信誉好的足球投注网站与广度优先有哪些信誉好的足球投注网站算法有何区别 通常深度优先有哪些信誉好的足球投注网站法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存