04-朴素解法

9.2.1　朴素解法

旅行商问题的朴素解法就是尝试所有可能的城市组合。尝试朴素解法能将该问题的难度呈现出来，说明朴素解法不适合大规模的蛮力求解。

1．示例数据

在本旅行商问题中，推销商想要访问佛蒙特州（Vermont）的5个主要城市。这里不指定起点（也就是终点）城市。图9-2显示了5个城市及其相互之间的行驶距离。请注意，每一对城市之间的路线上都标上了距离。

或许大家之前已经见过表格形式的行驶距离数据。在行驶距离表中，我们可以轻松找出任意两个城市之间的距离。表9-2列出了本问题中5个城市间的行驶距离。

| Rutland | Burlington | White River Junction | Bennington | Brattleboro | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | Rutland | 0 | 67 | 46 | 55 | 75 | | Burlington | 67 | 0 | 91 | 122 | 153 | | White River Junction | 46 | 91 | 0 | 98 | 65 | | Bennington | 55 | 122 | 98 | 0 | 40 | | Brattleboro | 75 | 153 | 65 | 40 | 0 |

这里需要为各个城市及其相互之间的距离编写数据结构。为了让城市之间的距离便于查找，我们将采用字典的字典，外部键代表一对城市中的第1个，内部键代表第2个。类型将是 Dict[str, Dict[str, int]] ，使其能执行 vt_distances["Rutland"]["Burlington"] 之类的检索并应返回67。具体代码如代码清单9-4所示。

代码清单9-4　tsp.py

from typing import Dict, List, Iterable, Tuple
from itertools import permutations
vt_distances: Dict[str, Dict[str, int]] = {
    "Rutland":
       {"Burlington": 67,
        "White River Junction": 46,
        "Bennington": 55,
        "Brattleboro": 75},
    "Burlington":
        {"Rutland": 67,
         "White River Junction": 91,
         "Bennington": 122,
         "Brattleboro": 153},
    "White River Junction":
        {"Rutland": 46,
         "Burlington": 91,
         "Bennington": 98,
         "Brattleboro": 65},
    "Bennington":
        {"Rutland": 55,
         "Burlington": 122,
         "White River Junction": 98,
         "Brattleboro": 40},
    "Brattleboro":
        {"Rutland": 75,
         "Burlington": 153,
         "White River Junction": 65,
         "Bennington": 40}
}

2．查找所有排列

旅行商问题的朴素解法需要生成所有城市每一种可能的排列（permutation）。排列生成算法有许多种，而且都很简单，读者自己一定能想出一种来。

有一种常见的排列生成算法是回溯（backtrack）。我们第一次介绍回溯是在第3章，其背景是求解约束满足问题。在求解约束满足问题过程中，当发现不满足问题约束的部分解后会用到回溯。这时将恢复到较早的状态，并沿着不同于出错部分解的路径继续搜索。

为了查找列表内数据项的所有排列方案（例如本例中的城市），我们也可以采用回溯。在交换列表元素进入后续排列方案的路径之后，我们可以回溯到交换之前的状态，以便再做其他的交换以沿着别的路径前进。

幸运的是，轮子没有必要重新发明，排列生成算法不需要重写，因为Python标准库在其 itertools 模块中包含了 permutations() 函数。在代码清单9-5中，我们生成了旅行商要访问的佛蒙特州城市的全部排列。因为有5个城市，所以就有5!（5的阶乘，即120）个排列值。

代码清单9-5　tsp.py（续）

vt_cities: Iterable[str] = vt_distances.keys()
city_permutations: Iterable[Tuple[str, ...]] = permutations(vt_cities)

3．蛮力搜索法

现在我们可以为城市列表生成全部排列了，但这与旅行商问题的路径不完全相同。还记得吧，在旅行商问题中，推销商最终必须回到起点城市。我们用列表推导式就能轻松地将排列中的第一个城市添加到排列的末尾。具体代码如代码清单9-6所示。

代码清单9-6　tsp.py（续）

tsp_paths: List[Tuple[str, ...]] = [c + (c[0],) for c in city_permutations]

现在我们可以尝试对已经排列出的路径进行测试了。蛮力搜索法费尽力气地查看路径列表中的每条路径，并用两个城市间距离的查找表（ vt_distances ）计算出每条路径的总距离。然后打印出最短路径及其总距离。具体代码如代码清单9-7所示。

代码清单9-7　tsp.py（续）

if __name__ == "__main__":
    best_path: Tuple[str, ...]
    min_distance: int = 99999999999 # arbitrarily high number
    for path in tsp_paths:
        distance: int = 0
        last: str = path[0]
        for next in path[1:]:
            distance += vt_distances[last][next]
            last = next
        if distance < min_distance:
            min_distance = distance
            best_path = path
     print(f"The shortest path is {best_path} in {min_distance} miles.")

现在我们终于可以对佛蒙特州的城市进行蛮力探索了，找出到达全部5个城市的最短途径。输出应该类似于如下所示，最佳路径呈现在图9-3上。

The shortest path is ('Rutland', 'Burlington', 'White River Junction', 'Brattleboro',
  'Bennington', 'Rutland') in 318 miles.