chp22专题

算法导论复习——CHP22 分支限界法

LIFO和FIFO分枝-限界法                 采用宽度优先策略,在生成当前E-结点全部儿子之后再生成其它活结点的儿子,且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。两种基本设计策略: FIFO检索:活结点表采用队列;LIFO检索:活结点表采用栈。         如采用FIFO分支-限界法检索4-皇后问题的状态空间树: LC-检索(Least Cost