分支限界法

梗概

• 带剪枝操作的广度优先遍历算法
  • 对当前节点的所有子分支进行判断
• Branch（分支） and Bound（上届）
  • Bound指的是：
  • 剪枝操作时，估算当前节点的价值上届（往往接近且大于于最优解的价值），以该估算上届作为该结点的剪枝判断条件

实例

child::01背包问题

图解

动画

child::

视频讲解

分支限界法求解0/1背包问题动画演示(Implementation of 0/1 Knapsack using Branch and Bound)_哔哩哔哩_bilibili