分支界限法

来自计算思维百科
跳转至: 导航搜索
分支界限法1.png

如果我们要求解一个最优问题,例如怎么做能达到最好,同时这个问题还能用树状结构表示,那么分支界限法就是一种在问题的解空间树上搜索问题解的算法。

基本概念

对于在求解过程中产生的部分解,我们寻找一种方法来确定一个界限,如果下面要产生的解超过了这个界限,就不用考虑了;只有在这个边界内的解,才有希望成为最后的解。这样可以大量减少需要搜索的解,提高求解效率。

应用范围

分支界限法作为经典方法之一,被广泛用于游戏设计,线路设计及分配管理方面。

使用方法及步骤

  1. 对于在已构造的解空间树上的每个部分解,计算出可能产生的任何解对应的最佳边界值
  2. 与目前已有的最佳解的值比较,抛弃那些比现有最佳解差的解。
  3. 重复2和3,找出最优解。

应用案例

应用1-背包问题

案例:小明参加游戏寻宝游戏,谁最后带回的宝藏总价值最高誰就获胜,小明一共找到了四件宝藏,价值分别为40、42、25、12,重量分别为4、7、5、3,可是小明的背包只能装下重量为10的东西,问如何装才能够使得装进的宝藏总价值最大?

解决步骤:

根据题意有下表:

背包承重为10

物品

重量

价值

价值比=价值/重量

1

4

40

10

2

7

42

6

3

5

25

5

4

3

12

4

按照分支界限法的解决步骤,我们首先寻找最优的边界;背包可能的最大价值为10X10=100,边界值的估计方法是:

已放入宝藏的价值+下一个宝藏的价值比*剩余的空间大小

先来看装入宝藏1和不装对应的最优边界值;

分支界限法2.png

此时,选择边界更大的76分支,继续宝藏2的舍留;

分支界限法3.png

发现,在加入1的前提下再加入宝藏2是不可行的,那么就需要在(含1,不含2)和(不含1)的两个分支选择希望更大的,故选择(含1,不含2)的分支;

分支界限法4.png

选择边界值最大的即价值为69的分支,继续看宝藏4是舍还是留;

分支界限法5.png

由此,我们可以得到最优解为装入宝藏1和宝藏3,可使总价值最大为65.

应用2-分配问题

案例:我们以4个人分配4个人为例,如下表格,对应着每个人分配不同任务时的成本;

 

任务A

任务B

任务C

任务D

人员1

9

2

7

8

人员2

6

4

3

7

人员3

5

8

1

8

人员4

7

6

9

4

解法:

对于此例来说,我们可以求出最小的成本(不考虑约束条件时),那我们可以得到2+3+1+4=10,这个解不是合法的(3和1在同一列),可以肯定的一点是产生的所有合法解都不可能小于这个值。我们从人员1开始,计算出人员1选择不同任务时对应方案的最优边界值,按照类似于案例一的过程来求解。

可以体现的计算思维

分支界限法通过边界值在状态树中不考虑没有希望的解,寻找最优解的过程体现了计算思维中的优化特点。