分枝-限界法

分枝(Branching)

  • 分枝:一个节点成为E-节点后,它要展开它的所有子节点;并将这些子节点放在一个称为活节点表的数据结构中;在活节点表中的节点可以展开所有状态空间树的节点,即广度优先遍历状态空间树;

  • 按一定的规则从活节点表中取出一个节点作为E-节点进行展开;

  • 活节点表可以是FIFO,LIFO和优先级队列;

  • 当使用优先级队列时必须对活节点表中的节点赋以一个权值;

  • 下文将结合求解优化为题介绍一种使用优先级队列的分枝-限界法。

最小成本优化问题

  • 设x=(x1,x2,…,xn)为可行解的元组;
  • 对每一个可行解有一个成本值,cost(x);
  • 求使cost(x)达到最小的可行解x;
  • 使用搜索算法求解最小成本优化问题。

任意节点的成本函数c(x)

  • 定义状态空间树上任一节点x的成本函数c(x)如下;
  • 如x为可行叶节点,则c(x)=cost(x);
  • 否则,定义c(x)=从x展开状态空间树能得到的最小成本值(状态空间树上以x为根的子树中可行解成本的最小值);
  • 如其子树中无可行解,则c(x)=∞。

LC-检索

  • 如果活节点表中每个节点以c(x)为权值,每次从活节点表中取出最小权值节点作为E-节点,则算法能很快找到优化解;
  • 但在展开x前不可能知道c(x)的值。但是有可能从历史信息获得c(x)的某一下界c^(x);
  • 以c(x)的下界估值c(x)作为活节点表中节点的权值,每次取出有最小c(x)的节点进行展开;
  • 要求设计的c(x)满足:c(x)=cost(x),当x为可行叶节点时。

限界

  • 令U为当前获得的最优成本值;
  • 设x=(x1,x2,…,xn),如果c^(x)>=U,则停止展开子节点x,即,不将其放入活节点表;
  • U初始值为∞,其后每一次的到一个新的可行解,用其成本值对U加以修改:U⬅min{U,cost(x)}。

Example:带截止期的作业调度问题

  • n个作业,1台处理机,每个作业i对应一个三元组(pi,di,ti);
  • pi:罚款额;
  • di:截止期;
  • ti:需要的处理机时间;
  • 求可行的作业子集J,使得罚款额最小,其中j为不在J中的作业;
  • 定长元组表示可行作业子集:(x1,x2,…,xn);
  • 设X=(x1,x2,…,xk)为状态空间树的节点;
  • 下界c^(x)可估计为展开到x时已得到的罚款额:Σ(1-xj)pj,求和范围为1<=j<=k。

例题

带截止期的作业调度问题实例

LC-分枝-限界产生的部分状态空间树

调度问题的另一种状态空间树

  • 可行条件(截止期)作为一种限界方法;
  • c^(x)>=U为另一限界方法;
  • 下图中每个节点标注了2个数,上边的数为c^(x),下边的数为该节点对应的可行解的罚款额,作为u(x);
  • 方框节点是非可行节点;
  • 打叉的节点是被限界掉的节点。