分支限界法

[TOC]

分支限界法(Branch and bound)类似于回溯法,都是在解空间树T上搜索问题解的算法。但一般两者求解目标不同,回溯法求解目标是找出T上满足约束条件的所有解,而分支限界法是找出满足条件的一个解,或是满足约束条件的解中使得目标函数值极大或极小的解(即最优解)。

分支限界法采用BFS策略搜索解空间树,在扩展节点处,先一次性生成其所有子节点(分支);然后,对这些子节点,计算一个函数值(限界),根据该值舍弃那些导致不可行解或非最优解的子节点,剩余子节点加入活节点表;此后,从活节点表中取下一节点成为扩展节点,重复上述步骤。这使得搜索朝解空间树上有最优解的分支快速推进,尽快找到最优解。

从活节点表中选择下一扩展节点的不同方法导致不同的分支限界方法,常见有两种:

  • FIFO分支限界法
  • 优先队列分支限界法

常见问题

旅行商问题

0-1背包问题