分支限界法求解旅行商问题具体实例

旅行商问题（Traveling Salesman Problem，TSP）是一种经典优化问题，其目标是找到一条路径，使得经过所有城市且路径最短。分支限界法是一种求解TSP的经典算法。

以下是一个具体实例：

假设有5个城市，它们的坐标如下：

| 城市 | x坐标 | y坐标 |
| --- | --- | --- |
| A | 1 | 2 |
| B | 2 | 3 |
| C | 4 | 1 |
| D | 5 | 4 |
| E | 3 | 5 |

我们可以建立一个邻接矩阵来表示这些城市之间的距离，其中矩阵中的每个元素表示从一个城市到另一个城市的距离。因为这是一个无向图，所以这个矩阵应该是对称的。

| | A | B | C | D | E |
| --- | --- | --- | --- | --- | --- |
| A | 0 | 1.41 | 3.16 | 4.24 | 3.16 |
| B | 1.41 | 0 | 2.24 | 3.61 | 2.24 |
| C | 3.16 | 2.24 | 0 | 5 | 4.12 |
| D | 4.24 | 3.61 | 5 | 0 | 2.24 |
| E | 3.16 | 2.24 | 4.12 | 2.24 | 0 |

我们可以从任意一个城市开始，假设我们从城市A开始。我们需要求出经过所有城市的最短路径。

1. 从城市A开始，我们可以依次访问城市B、C、D、E，然后回到城市A。这条路径的长度为1.41 + 3.16 + 4.24 + 3.16 + 1.41 = 13.38。

2. 我们可以考虑分支限界法来搜索更优的路径。我们可以将城市A作为根节点，然后扩展节点，将所有与城市A相邻的城市作为子节点。我们可以计算出每个子节点的路径长度，并按照路径长度从小到大排序。

3. 我们选择路径长度最小的子节点，即从城市A到城市B的路径，然后继续扩展该节点。我们将所有与城市B相邻的城市作为子节点，计算出它们到达城市B的路径长度，并按照路径长度从小到大排序。

4. 我们选择路径长度最小的子节点，即从城市A到城市B再到城市E的路径，然后继续扩展该节点。我们将所有与城市E相邻的城市作为子节点，计算出它们到达城市E的路径长度，并按照路径长度从小到大排序。

5. 我们选择路径长度最小的子节点，即从城市A到城市B再到城市E再到城市D的路径，然后继续扩展该节点。我们将所有与城市D相邻的城市作为子节点，计算出它们到达城市D的路径长度，并按照路径长度从小到大排序。

6. 我们选择路径长度最小的子节点，即从城市A到城市B再到城市E再到城市D再到城市C的路径。这是一条经过所有城市的路径，我们可以计算它的长度为1.41 + 2.24 + 2.24 + 4.12 + 3.16 = 13.17。

7. 我们继续扩展节点，但是发现没有比当前路径更短的路径了，因此搜索结束。

这样我们就找到了一条经过所有城市且路径最短的路径，其长度为13.17。