分支定界 vs 回溯

在理解分支限界法和回溯法的区别之前，我们应该分别了解分支限界法和回溯法。

什么是回溯法？

回溯法本质上是蛮力法的改进过程。它是一种技术，当一个问题有多种解决方案时，它会在所有可用选项中搜索问题的解决方案。让我们以蛮力搜索为例，因为回溯法遵循蛮力搜索的方法。

考虑一个盒子，我们有三种不同颜色的三个物体。一个物体是红色的，第二个是绿色的，第三个是蓝色的。现在，我们必须将这些物体放入盒子中，我们有多种选择。根据蛮力法，我们必须考虑所有选项，并从所有可能的选项中找出最佳选项。

让我们考虑这个问题的所有可能解决方案。

假设我们先装红色物体，然后是绿色物体，最后是蓝色物体。这是此问题的第一个解决方案。可能的解决方案是红色、绿色和蓝色。

第二个解决方案是将红色物体放入，然后是蓝色物体，最后是绿色物体。可能的解决方案是红色、蓝色和绿色。

第三个解决方案可以是先放入绿色物体，然后是红色物体，最后是蓝色物体。可能的解决方案是绿色、红色和蓝色。

第四个解决方案可以是先放入绿色物体，然后是蓝色物体，最后是红色物体。可能的解决方案是绿色、蓝色和红色。

第五个解决方案是将蓝色物体放入，然后是绿色物体，最后是红色物体。可能的解决方案是蓝色、绿色和红色。

第六个解决方案是将蓝色物体放入，然后是红色物体，最后是绿色物体。可能的解决方案是蓝色、红色和绿色。

以上是可能的解决方案，我们必须从所有可能的解决方案中找出最佳解决方案。这种方法称为蛮力法。回溯法与蛮力法类似，但它是蛮力法的改进过程。

让我们看看回溯法与蛮力法的区别。

上面是显示上述问题可能解决方案的图。现在我们将看到回溯法如何表示这些解决方案。

在回溯法中，解决方案以树的形式表示，该树称为状态空间树。由于回溯法遵循深度优先搜索 (DFS)，因此树将使用 DFS 构建，称为状态空间树。

让我们创建这棵树。

考虑第一个解决方案，即红色、绿色、蓝色，它可以表示为如下所示的树。

考虑第二个解决方案，即红色、蓝色、绿色。由于蓝色之后没有其他物体了，我们将回溯并移至绿色。不是先取绿色，而是先取蓝色，然后是绿色，如下所示。

下一个解决方案是绿色、红色和蓝色。由于我们无法探索绿色物体，因此我们向后移动并到达蓝色物体。我们无法探索蓝色物体，因此我们再次向后移动并回到红色物体。不是使用红色物体，而是使用绿色物体。在绿色物体之后，我们使用红色物体，然后我们使用蓝色物体。我们无法进一步探索蓝色物体。现在形成的序列是绿色、红色和蓝色，如下所示。

下一个解决方案是绿色、蓝色和红色。由于我们无法探索蓝色物体，我们向后移动并到达红色物体。不是使用红色物体，而是使用蓝色物体，然后使用红色物体。现在形成了绿色、蓝色和红色的序列。

下一个解决方案是蓝色、绿色和红色。由于我们无法探索红色物体，因此我们回溯并到达蓝色物体。我们无法探索蓝色物体，因此我们回溯并到达绿色物体。不是使用绿色物体，而是使用蓝色物体，然后使用绿色物体，最后使用红色物体。形成的序列是蓝色、绿色和红色，如下所示。

下一个解决方案是蓝色、红色和绿色。由于我们无法探索红色物体，因此我们回溯并到达绿色物体。不是使用绿色物体，而是使用红色物体，然后使用绿色物体。

以上是显示与问题相关的所有可能解决方案的状态空间树。因此，我们可以说状态空间树可用于表示回溯法中的所有解决方案。使用回溯法，我们可以解决具有某些约束条件的问题，并根据这些约束条件找到解决方案。假设在上面的例子中，约束条件是蓝色物体不能放在中间（界定函数）。

第一个解决方案是红色、绿色和蓝色。由于蓝色物体不在中间，因此我们不需要进行任何修改。

第二个解决方案是红色、蓝色和绿色。由于蓝色物体在中间，因此我们将移除绿色物体，如下所示。

下一个解决方案是绿色、红色和蓝色。由于蓝色物体不在中间，因此我们不需要进行任何修改。

下一个解决方案是绿色、蓝色和红色。由于蓝色物体在中间，因此我们将移除红色物体，如下所示。

上面是状态空间树，其中解决方案中不包含蓝色物体。

分支定界

它与回溯法类似。分支限界法和回溯法的概念都遵循蛮力法并生成状态空间树。但它们都遵循不同的方法。生成树的方式是不同的。

回溯法遵循 DFS，而分支限界法则遵循 BFS 来生成树。现在我们将通过一个例子来理解分支限界法。由于它遵循 BFS，因此首先会添加同一级别的所有节点，然后我们移至下一个级别。

让我们考虑在回溯法中讨论过的同一个例子。

首先，我们取根节点。

现在我们有三种可能性，即选择红色、绿色或蓝色物体，如下所示。在这种情况下，我们已完成第一层。

现在我们移至下一级别。

在红色物体的情况下，我们有两种可能性，即选择绿色或蓝色物体，如下所示。

在绿色物体的情况下，我们有两种可能性，即选择红色或蓝色物体，如下所示。

在蓝色物体的情况下，我们有两种可能性，即选择红色或绿色物体，如下所示。

我们移至第三级别。

在绿色物体的情况下，只能添加一个物体，即蓝色。

在蓝色物体的情况下，只能添加一个物体，即绿色。

在红色物体的情况下，只能添加一个物体，即蓝色。

在蓝色物体的情况下，只能添加一个物体，即红色。

在绿色物体的情况下，只能添加一个物体，即红色。

在红色物体的情况下，只能添加一个物体，即绿色。

示例

可以使用回溯法解决的问题有：

• 8 皇后问题
• 回溯法解决的背包问题

可以使用分支限界法解决的问题有：

• Travelling Salesman Problem

分支限界法与回溯法的区别