分支定界

什么是分支限界法？

分支限界法是一种用于解决问题的技术。它类似于回溯法，因为它也使用状态空间树。它用于解决优化问题和最小化问题。如果我们给出一个最大化问题，我们可以使用分支限界技术将其转换为一个最大化问题。

让我们通过一个例子来理解。

作业 = {j1, j2, j3, j4}

P = {10, 5, 8, 3}

d = {1, 2, 1, 2}

以上是作业、问题和给出的问题。我们可以用以下两种方式来写解决方案。

假设我们要执行作业 j1 和 j2，那么解决方案可以表示为两种方式。

表示解决方案的第一种方式是作业的子集。

S1 = {j1, j4}

表示解决方案的第二种方式是：第一个作业已完成，第二个和第三个作业未完成，第四个作业已完成。

S2 = {1, 0, 0, 1}

解决方案 s1 是可变大小的解决方案，而解决方案 s2 是固定大小的解决方案。

首先，我们将看到子集方法，其中我们将看到可变大小。

第一种方法

在这种情况下，我们首先考虑第一个作业，然后是第二个作业，然后是第三个作业，最后考虑最后一个作业。

正如我们在上图中观察到的，这里执行的是广度优先搜索，而不是深度优先搜索。我们在这里是广度优先地探索解决方案。在回溯法中，我们深度优先，而在分支限界法中，我们广度优先。

现在一个层已经完成。一旦我做完第一个作业，我们就可以考虑 j2、j3 或 j4。如果我们沿着这条路径，它意味着我们在做作业 j1 和 j4，所以我们不会考虑作业 j2 和 j3。

现在我们将考虑节点 3。在这种情况下，我们在做作业 j2，所以我们可以考虑作业 j3 或 j4。在这里，我们已经放弃了作业 j1。

现在我们将扩展节点 4。因为这里我们在做作业 j3，所以我们只考虑作业 j4。

现在我们将扩展节点 6，这里我们将考虑作业 j3 和 j4。

现在我们将扩展节点 7，这里我们将考虑作业 j4。

现在我们将扩展节点 9，这里我们将考虑作业 j4。

最后一个节点，即节点 12，有待扩展。在这里，我们考虑作业 j4。

以上是解决方案 s1 = {j1, j4} 的状态空间树。

第二种方法

我们将看到另一种解决问题以获得解决方案 s1 的方法。

首先，我们考虑下图中所示的节点 1。

现在，我们将扩展节点 1。扩展后，状态空间树将显示如下：

每次扩展，节点将被推入下图中所示的堆栈。

现在扩展将基于堆栈顶部的节点。由于节点 5 出现在堆栈顶部，我们将扩展节点 5。我们将从堆栈中弹出节点 5。由于节点 5 是最后一个作业，即 j4，所以没有进一步扩展的余地。

堆栈中下一个出现的节点是节点 4。弹出节点 4 并扩展。扩展时，将考虑作业 j4，并将节点 6 添加到下图中所示的堆栈中。

下一个要扩展的节点是 6。弹出节点 6 并扩展。由于节点 6 是最后一个作业，即 j4，所以没有进一步扩展的余地。

下一个要扩展的节点是节点 3。由于节点 3 处理作业 j2，因此节点 3 将被扩展到两个节点，即分别处理作业 3 和 4 的节点 7 和 8。节点 7 和 8 将被推入下图中所示的堆栈。

堆栈顶部出现的下一个节点是节点 8。弹出节点 8 并扩展。由于节点 8 处理作业 j4，因此没有进一步扩展的余地。

堆栈顶部出现的下一个节点是节点 7。弹出节点 7 并扩展。由于节点 7 处理作业 j3，因此节点 7 将被进一步扩展到下图中所示的处理作业 j4 的节点 9，并将节点 9 推入堆栈。

堆栈顶部出现的下一个节点是节点 9。由于节点 9 处理作业 4，因此没有进一步扩展的余地。

堆栈顶部出现的下一个节点是节点 2。由于节点 2 处理作业 j1，这意味着节点 2 可以进一步扩展。它可以扩展到三个节点，分别命名为 10、11、12，处理作业 j2、j3 和 j4。新节点将被推入下图中所示的堆栈。

在上述方法中，我们使用遵循 LIFO 原则的堆栈探索了所有节点。

第三种方法

还有一种方法可以用于找到解决方案，那就是“最小成本分支限界”。在这种技术中，节点是根据节点的成本来探索的。节点的成本可以使用问题来定义，并借助给定的问题，我们可以定义成本函数。一旦定义了成本函数，我们就可以定义节点的成本。

首先，我们考虑成本为无穷大的节点 1，如下所示。

现在我们将扩展节点 1。节点 1 将扩展为下图中所示的四个节点，分别命名为 2、3、4 和 5。

假设节点 2、3、4 和 5 的成本分别为 25、12、19 和 30。

由于这是最小成本分支限界，因此我们将探索成本最低的节点。在上图中，我们可以观察到成本最低的节点是节点 3。因此，我们将探索成本为 12 的节点 3。

由于节点 3 处理作业 j2，因此它将扩展为下图中所示的两个节点，分别命名为 6 和 7。

节点 6 处理作业 j3，而节点 7 处理作业 j4。节点 6 的成本是 8，节点 7 的成本是 7。现在我们必须选择成本最低的节点。节点 7 的成本最低，因此我们将探索节点 7。由于节点 7 已经处理了作业 j4，因此没有进一步扩展的余地。