分支定界法求解旅行商问题

给定顶点，问题在于我们必须访问每个顶点恰好一次，然后返回到起点。考虑下面的图

正如我们在上面的图中观察到的，图中给出了5个顶点。我们需要找到一条遍历所有顶点一次并返回到起始顶点的最短路径。我们主要将起始顶点视为1，然后遍历顶点2、3、4和5，最后返回顶点1。

问题的邻接矩阵如下所示

现在我们来看看如何使用分支定界法来解决这个问题。

让我们先理解这个方法，然后再解决上述问题。

下图给出了一个具有四个顶点的图

假设我们从顶点1开始旅行，然后返回顶点1。有多种方法可以遍历所有顶点并返回顶点1。我们需要一些工具来最小化总成本。为了解决这个问题，我们构建了一个状态空间树。从起始顶点1，我们可以去顶点2、3或4，如下图所示。

从顶点2，我们可以去顶点3或4。如果我们考虑顶点3，我们就去剩下的顶点，即4。如果我们考虑下图所示的顶点4

从顶点3，我们可以去剩下的顶点，即2或4。如果我们考虑顶点2，那么我们就去剩下的顶点4，如果我们考虑顶点4，那么我们就去剩下的顶点，即下图所示的3

从顶点4，我们可以去剩下的顶点，即2或3。如果我们考虑顶点2，那么我们就去剩下的顶点，即3，如果我们考虑顶点3，那么我们就去剩下的顶点，即下图所示的2

以上是完整的状态空间树。状态空间树显示了所有可能性。回溯法和分支定界法都使用状态空间树，但它们解决问题的方法不同。分支定界法比回溯法更好，因为它更有效。为了使用分支定界法解决问题，我们使用层序遍历。首先，我们将观察节点的生成顺序。在创建节点时，我们将同时计算节点的成本。如果发现任何节点的成本大于上界，我们将删除该节点。因此，在这种情况下，我们将只生成有用的节点，而不是所有的节点。

让我们考虑上述问题。

正如我们在上面的邻接矩阵中所观察到的，10是第一行的最小值，2是第二行的最小值，2是第三行的最小值，3是第三行的最小值，3是第四行的最小值，4是第五行的最小值。

现在，我们将约简矩阵。我们将用每一行的最小值减去该行的所有元素。首先，我们计算第一行。假设有两个变量，即i和j，其中“i”代表行，“j”代表列。

当 i = 0, j =0

M[0][0] = ∞-10= ∞

当 i = 0, j = 1

M[0][1] = 20 - 10 = 10

当 i = 0, j = 2

M[0][2] = 30 - 10 = 20

当 i = 0, j = 3

M[0][3] = 10 - 10 = 0

当 i = 0, j = 4

M[0][4] = 11 - 10 = 1

计算完第一行后，矩阵如下所示

考虑第二行。

当 i = 1, j =0

M[1][0] = 15-2= 13

当 i = 1, j = 1

M[1][1] = ∞ - 2= ∞

当 i = 1, j = 2

M[1][2] = 16 - 2 = 14

当 i = 1, j = 3

M[1][3] = 4 - 2 = 2

当 i = 1, j = 4

M[1][4] = 2 - 2 = 0

计算完第二行后，矩阵如下所示

考虑第三行

当 i = 2, j =0

M[2][0] = 3-2= 1

当 i = 2, j = 1

M[2][1] = 5 - 2= 3

当 i = 2, j = 2

M[2][2] = ∞ - 2 = ∞

当 i = 2, j = 3

M[2][3] = 2 - 2 = 0

当 i = 2, j = 4

M[2][4] = 4 - 2 = 2

计算完第三行后，矩阵如下所示

考虑第四行

当 i = 3, j =0

M[3][0] = 19-3= 16

当 i = 3, j = 1

M[3][1] = 6 - 3= 3

当 i = 3, j = 2

M[3][2] = 18 - 3 = 15

当 i = 3, j = 3

M[3][3] = ∞ - 3 = ∞

当 i = 3, j = 4

M[3][4] = 3 - 3 = 0

计算完第四行后，矩阵如下所示

考虑第五行

当 i = 4, j =0

M[4][0] = 16-4= 12

当 i = 4, j = 1

M[4][1] = 4 - 4= 0

当 i = 4, j = 2

M[4][2] = 7 - 4 = 3

当 i = 4, j = 3

M[4][3] = 16 - 4 = 12

当 i = 4, j = 4

M[4][4] = ∞ - 4 = ∞

计算完第五行后，矩阵如下所示

上面的矩阵是关于行约简后的矩阵。

现在我们按列约简矩阵。在约简矩阵之前，我们首先找到所有列的最小值。第一列的最小值是1，第二列的最小值是0，第三列的最小值是3，第四列的最小值是0，第五列的最小值是0，如下图所示

现在我们约简矩阵。

考虑第一列。

当 i = 0, j =0

M[0][0] = ∞-1= ∞

当 i = 1, j = 0

M[1][0] = 13 - 1= 12

当 i = 2, j = 0

M[2][0] = 1 - 1 = 0

当 i = 3, j = 0

M[3][0] = 16 - 1 = 15

当 i = 4, j = 0

M[4][0] = 12 - 1 = 11

计算完第一列后，矩阵如下所示

由于第一列和第三列的最小值为非零，我们只计算第一列和第三列。我们已经计算了第一列。现在我们将计算第三列。

考虑第三列。

当 i = 0, j =2

M[0][2] = 20-3= 17

当 i = 1, j = 2

M[1][2] = 13 - 1= 12

当 i = 2, j = 2

M[2][2] = 1 - 1 = 0

当 i = 3, j = 2

M[3][2] = 16 - 1 = 15

当 i = 4, j = 2

M[4][2] = 12 - 1 = 11

计算完第三列后，矩阵如下所示

上面是约简后的矩阵。行的最小值为21，列的最小值为4。因此，总最小值为（21 + 4）等于25。

让我们借助状态空间树来理解如何使用分支定界法解决这个问题。

为了构建状态空间树，我们首先考虑节点1。从节点1，我们可以前往节点2、3、4或5，如下图所示。节点1的成本将是我们上面约简矩阵中获得的成本，即25。在这里，我们还将维护上界。最初，上界将是无穷大。

现在，考虑节点2。这意味着我们从节点1移动到节点2。将第一行和第二列设置为无穷大，如下图所示

一旦我们从节点1移动到节点2，我们就不能再返回到节点1。因此，我们必须将2到1设置为无穷大，如下图所示

由于每一行和每一列至少包含一个零值；因此，我们可以说上面的矩阵已经被约简了。节点2的约简成本是c(1, 2) + r + r` = 10 + 25 + 0 = 35。

现在我们将找到新约简矩阵中每一列的最小值。第一列的最小值为11，其他三列的最小值为0。

现在，考虑节点3。这意味着我们从节点1移动到节点3。将第一行和第三列设置为无穷大，如下图所示

一旦我们从节点1移动到节点3，我们就不能再返回到节点1。因此，我们将3到1设置为无穷大，如下图所示

由于每一行和每一列至少包含一个零值；因此，我们可以说上面的矩阵已经被约简了。节点3的约简成本是c(1, 3) + r + r` = 17 + 25 + 11= 53。

现在，考虑节点4。这意味着我们从节点1移动到节点4。将第一行和第四列设置为无穷大，如下图所示

一旦我们从节点1移动到节点4，我们就不能再返回到节点1。因此，我们将4到1设置为无穷大，如下图所示

由于每一行和每一列至少包含一个零值；因此，我们可以说上面的矩阵已经被约简了。节点4的约简成本是c(1, 4) + r + r` = 0 + 25 + 0 = 25。

现在，考虑节点5。这意味着我们从节点1移动到节点5。将第一行和第五列设置为无穷大，如下图所示

一旦我们从节点1移动到节点5，我们就不能再返回到节点1。因此，我们将5到1设置为无穷大，如下图所示

由于每一行和每一列至少包含一个零值；因此，我们可以说上面的矩阵已经被约简了。在这种情况下，第二行和第三行是非零的。因此，我们首先找到这两行的最小值。第二行的最小值为2；因此，我们将2减去第二行的所有元素。第二行的元素将是

A[1][0] = 12-2 = 10

A[1][1] = ∞

A[1][2] = 11 - 2 = 9

A[1][3] = 2 - 2 = 0

A[1][4] = ∞ - 2 = ∞

现在我们可以看到第二行包含一个零值。

节点5的约简成本是c(1, 5) + r + r` = 1 + 25 + 5 = 31

由于节点4的成本最低，即25。所以我们首先探索节点4。从顶点4，我们可以去顶点2、3或5，如下图所示

现在我们需要计算从顶点4到2、从顶点4到3以及从顶点4到5的路径成本。在这里，我们将使用节点4的矩阵来找到所有节点的成本。

首先，我们考虑从顶点4到顶点2的路径。我们将第四行设置为∞，第二列设置为∞。由于我们不能从2返回到1，所以1到2也设置为无穷大，如下图所示

由于所有行和列至少包含一个零值。因此，我们可以说这个矩阵已经被约简了。所以，没有约简成本。节点2的约简成本是c(4, 2) + r + r` = 3 + 25 + 0 = 28

现在我们需要计算从顶点4到顶点3的路径成本。我们将第四行和第三列设置为无穷大，如下图所示。由于我们不能从顶点3返回到1，所以我们将3到1设置为无穷大，如下图所示

现在我们将检查每一行和每一列是否至少包含一个零值。首先，我们观察所有行。由于第三行不包含零值，所以我们首先找到第三行的最小值。第三行的最小值为2，所以我们将2减去第三行的所有元素。第三行的元素将是

A[2][0] = ∞ - 2 = ∞

A[2][1] = 3 - 2 = 1

A[2][2] = ∞ - 2 = ∞

A[2][3] = ∞ - 2 = ∞

A[2][4] = 2 - 2 = 0

现在我们可以看到第三行包含一个零值。

第一列不包含零值。第一列的最小值为11。我们将11减去第一列的所有元素。第一列的元素将是

A[0][0] = ∞ - 11 = ∞

A[1][0] = 12 - 11 = 1

A[2][0] = ∞ - 11= ∞

A[3][0] = ∞ - 11= ∞

A[4][0] = 11 - 11 = 0

现在我们可以看到第一列包含一个零值。总最小成本是11 + 2 = 13。节点3的约简成本是c(4, 3) + r + r` = 12 + 25 + 13 = 50。

现在我们将计算从顶点4到5的路径成本。我们将第四行和第五列设置为无穷大。由于我们不能从节点5返回到1，所以也将1到5设置为无穷大，如下图所示

现在我们将检查每一行和每一列是否至少包含一个零值。首先，我们观察所有行。第二行不包含零值，所以我们找到第二行的最小值。最小值为11，所以我们将11减去第二行的所有元素。第二行的元素将是

A[1][0] = 12 - 11 = 1

A[1][1] = ∞ - 11 = ∞

A[1][2] = 11 - 11 = 0

A[1][3] = ∞ - 11 = ∞

A[1][4] = ∞ - 11 = ∞

现在我们可以看到第二行包含一个零值。节点5的约简成本是c(4, 5) + r + r` = 0 + 25 + 11 = 36。

现在我们将比较所有叶节点的成本。成本为28的节点成本最低，所以我们首先探索这个节点。成本为28的节点可以进一步扩展到节点3和5，如下图所示

现在我们需要计算这两个节点，即3和5的成本。首先我们考虑从节点2到节点3的路径。考虑节点2的矩阵，如下所示

我们将第二行和第三列设置为无穷大。此外，我们不能从节点3返回到节点1，所以我们将3到1也设置为无穷大，如下图所示

现在我们将检查是否有任何行包含零值。由于第三行不包含任何零值，所以我们将找到第三行的最小值。第三行的最小值为2，所以我们将2减去第三行的所有元素。第三行的元素将是

A[2][0] = ∞ - 2 = ∞

A[2][1] = ∞ - 2 = ∞

A[2][2] = ∞ - 2 = ∞

A[2][3] = ∞ - 2 = ∞

A[2][4] = 2 - 2 = 0

由于第五行不包含任何零值，所以我们将找到第五行的最小值。第五行的最小值为11，所以我们将11减去第五行的所有元素。

A[4][0] = 11 - 11 = 0

A[4][1] = ∞ - 11 = ∞

A[4][2] = ∞ - 11 = ∞

A[4][3] = ∞ - 11 = ∞

A[4][4] = ∞ - 11 = ∞

总最小成本是（11 + 2）等于13。节点3的约简成本是c(2, 3) + r + r` = 11 + 28 + 13 = 52。

考虑从节点2到节点5的路径。将第四行和第三列设置为无穷大。由于我们不能从节点5返回到节点1，所以也将1到5设置为无穷大，如下图所示

现在我们将检查是否有任何行包含零值。由于每一行和每一列都包含零值；因此，上面的矩阵是约简后的矩阵。

节点5的约简成本是c(2, 5) + r + r` = 0 + 28 + 0 = 28

现在我们将找出成本最低的叶节点。成本为28的节点5是最低的，所以我们选择节点5进行进一步的探索。节点5可以进一步扩展到节点3，如下图所示

在这里，我们将使用成本为28的节点5的矩阵，如下所示

考虑从节点5到节点3的路径。将第五行和第三列设置为无穷大。由于我们不能从节点3返回到节点1，所以也将1到5设置为无穷大，如下图所示

现在我们将检查是否有任何行包含零值。由于每一行和每一列都包含零值；因此，上面的矩阵是约简后的矩阵。

节点3的约简成本是c(5, 3) + r + r` = 0 + 28 + 0 = 28。

最后，我们遍历所有节点。上界从无穷大更新为28。我们将检查是否有任何叶节点的价值小于28。由于没有叶节点的值小于28，所以我们从树中丢弃所有叶节点，如下图所示

旅行路径将是1->4->2->5->3。