第六章分支界限法.ppt

*计算机算法设计与分析1第六章分支限界法稠蹭措密廉组迹廊澳腻爵适办搓腕辙掂沛越惹旋捎斩型变楷舞怀顿司算栽第六章分支界限法第六章分支界限法*计算机算法设计与分析2分支限界法分支限界法也是在问题的解空间树T上搜索问题解的算法。防塑绵勉为漳宫碾踪汀庙勇坷蔷冉泰博劫挪置膏距氧证出渐瞩材驴***潮此第六章分支界限法第六章分支界限法*计算机算法设计与分析3分支限界法的基本思想构造问题的解空间树。以广度优先或以最小耗费优先方式搜索解空间树。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。不能产生可行解或肯定不能产生最优解的儿子被删除,其余的被加入活结点表中。从活结点表中取下一结点成为当前扩展结点,重复上述过程,直至找到所需的解或活结点表为空。怎么取?从下一扩展结点的不同方式导致不同的分支限界法。FIFO分支限界法将活结点表组织成为一个队列,按先进先出原则选择下一个结点。优先队列分支限界法将活结点表组织成为一个优先队列,并按队列中规定的优先级来选取优先级最高的下一个结点。通常,用一个与结点相关的数值p来表示。在算法实现时,通常采用堆结构实现。匡籍霄弘誓项碌南空搞总窗丙档猪互砌弧琼翰视控捶苑墟弦制裸坍错韦佯第六章分支界限法第六章分支界限法*计算机算法设计与分析4分支限界法与回溯法的比较相同点:都是在解空间树上搜索问题解不同点:搜索方式不同:前者用的是深度优先搜索,后者用的是广度优先搜索或以最小耗费优先的方式搜索。扩展结点的方式不同:前者扩展结点有多次机会成为扩展结点,后者只有一次机会。虫河砸灾激笔挥察滨来辫潮霖皇淌累嗽妹酌蓟汛个荆敛尘悟溶欣扫纯固荫第六章分支界限法第六章分支界限法*计算机算法设计与分析5S110-1背包问题的状态空间树下面是n=3的0-1背包问题的状态空间树,其中:w=[16,15,15],p=[45,25,25],c=30。采取队列式分支限界法。SI1S10S010S101S010S001S1110S1101S1010S1001S0110S0101S0010S000S1S10S0SIS10SIS1S100S01S00S0S100缮五贬修黔绢疟星丢脚试抓童迢箕蹦矫圾衡登毛晃狐型横董赐法菱罪嘱孔第六章分支界限法第六章分支界限法*计算机算法设计与分析6搜索路径的构造在回溯法中,每次仅考察一条路径,因而只需要构造这一条路径即可:前进时记下相应结点,回溯时删去最末尾结点的记录。这比较容易实现。在分支限界法中,是同时考察若干条路径,那么又该如何构造搜索的路径呢?对每一个扩展的结点,建立三个信息:(1)该结点的名称;(2)它的评价函数值;(3)指向其前驱的指针;这样一旦找到目标,即可逆向构造其路径。楚帽郁低著诱貉翔礁韶仰后反弥坦仑豌亢密悄柒侗栖绪远陪宏尾挖纵恐毋第六章分支界限法第六章分支界限法*计算机算法设计与分析7分支限界法的一般算法计算初始结点s的f(s);[s,f(s),nil]插入队列;while(队列≠Φ){从队列中取出[p,f(p),x]。(根据具体方式,可以选择下一结点或f(p)为最小(大));若p是目标,则成功返回;否则产生p的后继,并将后继结点插入队列中(可以按照一定规则淘汰一些结点)将[p,f(p),x]从队列中删除;}媒性囱轰撕碑通辉孔释嚏晋执鹏婶坐蕴撕泻掀诸炳乌赁***混约租醉泅茁酬第六章分支界限法第六章分支界限法*计算机算法设计与分析8装载问题有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量为wi,且。要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。可证明,采用如下策略可以得到一个最优装载方案:先尽可能的将第一艘船装满,其次将剩余的集装箱装到第二艘船上。这样我们要想办法尽可能的将第一艘船装满,即该问题等价于一个特殊的0-1背包问题:*计算机算法设计与分析9用分支限界法解装载问题可以用回溯法解装载问题,。我们同样可以用分支限界法来解装载问题。首先来看看用队列式分支限界法解该问题。样锻刃遮冉缕度遗哲蝗涂像糙添金批维酗沼卑揭眯岭终倘毛芒缎督俐犀洪第六章分支界限法第六章分支界限法*计算机算法设计与分析10设置初始值,EW=0,bestw=0,i=(-1);//同层结点尾部标志While(true){if(左儿子结点是活结点)将该结点插入队列中;将右儿子结点插入队列中;取下一个扩展结点。if(同层结点尾部){if(队列空)return最优值;插入同层结点尾部标记;取下一扩展结点;i++;}}队列式分支限界法解装载问题数据结构:Q:活结点队列EW:扩展结点对应的载重量Bestw:当前最优载重量。X[]:对应的最优解。计算初始结点s的f(s