文档介绍：搜索算法——分支限界法*回溯搜索过程简单说就是:能进则进,不能进则换,不能换则退*分支限界法的搜索策略在扩展结点处,先生成其所有子结点(分支),然后从当前的活结点表中选下一个扩展结点为了有效地选择下一扩展结点,以加速搜索的进程,在每一结点处,计算一个函数值(限界),并根据这些已计算的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点*分支限界法基本思想以广度优先或以最小耗费(最大效益)优先的方式搜索;每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。*从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。*常见的两种分支限界法队列式(FIFO)分支限界法 -按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。优先队列式分支限界法 -按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。*(1)0-1背包问题n=3,C=30,w=[16,15,15],p=[45,25,25]n=3的解空间树——子集树*(1)0-1背包问题①FIFO分支限界法②优先队列式分支限界法③剪枝函数*①FIFO分支限界法n=3的解空间树——子集树n=3,C=30,w=[16,15,15],p=[45,25,25]*队列式分支限界法搜索与广度优先遍历区别:队列式分支限界法不搜索以不可行结点为根的子树.