DSA 旅行推销员问题

旅行推销员问题

旅行推销员问题是指，你是一名推销员，你需要访问多个城市或城镇。

除了 Held-Karp 算法（非常先进且耗时，（\(O(2^n n^2)\))，这里不作介绍）之外，没有其他方法可以找到最短路线，除了检查所有可能的路线。

这意味着解决这个问题的时间复杂度是 \(O(n!)\)，这意味着对于 6 个城市需要检查 720 条路线，对于 8 个城市需要检查 40,320 条路线，如果你要访问 10 个城市，就需要检查超过 360 万条路线！

旅行推销员问题（TSP）是一个值得研究的问题，因为它非常实用，但解决它非常耗时，以至于即使在只有 20-30 个顶点的图中，也很难找到最短路线。

如果我们有一个有效的算法来解决旅行推销员问题，那么在许多领域将会产生巨大的影响，例如芯片设计、车辆路径规划、电信和城市规划。

检查所有路线以解决旅行推销员问题

要找到旅行推销员问题的最优解，我们将检查所有可能的路线，每当我们找到一条更短的路线，我们就将其存储起来，这样最终我们将得到最短的路线。

优点： 找到总体最短路线。

缺点： 需要大量的计算，特别是对于大量的城市，这意味着非常耗时。

这种找到问题解决方案的方法称为 **暴力法**。

暴力法并不是真正的算法，它只是意味着通过检查所有可能性来找到解决方案，通常是因为缺乏更好的方法。

上面所示的通过检查所有路线（暴力法）来找到最短路线的方法之所以如此耗时，是因为我们正在检查所有路线，而可能的路线数量随着城市数量的增加而快速增加。

from itertools import permutations

def calculate_distance(route, distances):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]
    return total_distance

def brute_force_tsp(distances):
    n = len(distances)
    cities = list(range(1, n))
    shortest_route = None
    min_distance = float('inf')
    
    for perm in permutations(cities):
        current_route = [0] + list(perm)
        current_distance = calculate_distance(current_route, distances)
        
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_route = current_route
    
    shortest_route.append(0)
    return shortest_route, min_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = brute_force_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

使用贪心算法来解决旅行推销员问题

由于检查所有可能的路线来解决旅行推销员问题（如上所示）非常耗时，因此我们可以通过在每一步都前往最近的未访问城市来找到一条较短的路线，这样速度要快得多。

优点： 比检查所有路线快得多，可以找到旅行推销员问题的解决方案。

缺点： 不能找到总体最短路线，它只能找到比平均随机路线短得多的路线。

这种通过在每一步都前往最近的未访问城市来找到旅行推销员问题中最短路线的近似值的方法称为 **贪心算法**。

正如你通过运行此模拟几次可以看出，找到的路线并非完全不合理。除了几条线可能交叉外，尤其是在算法结束时，生成的路线比我们随机选择下一个城市得到的路线要短得多。

def nearest_neighbor_tsp(distances):
    n = len(distances)
    visited = [False] * n
    route = [0]
    visited[0] = True
    total_distance = 0

    for _ in range(1, n):
        last = route[-1]
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and distances[last][i] < min_dist:
                min_dist = distances[last][i]
                nearest = i
        route.append(nearest)
        visited[nearest] = True
        total_distance += min_dist

    total_distance += distances[route[-1]][0]
    route.append(0)
    return route, total_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = nearest_neighbor_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

其他用于找到旅行推销员问题的近似最优解的算法

除了使用贪心算法来解决旅行推销员问题之外，还有其他算法可以找到最短路线的近似值。

这些算法很流行，因为它们比实际检查所有可能的解决方案更有效，但与上面的贪心算法一样，它们不会找到总体最短路线。

用于找到旅行推销员问题的近似最优解的算法包括

• 2-opt 启发式算法： 一种逐步改进解决方案的算法，在每一步中，它会删除两条边，并以不同的方式重新连接两条路径，以减少总路径长度。
• 遗传算法： 这是一种受自然选择过程启发的算法类型，它使用选择、变异和交叉等技术来进化解决问题的方法，包括 TSP。
• 模拟退火： 这种方法的灵感来自冶金中的退火过程。它涉及加热材料，然后缓慢冷却材料以减少缺陷。在 TSP 的背景下，它用于通过探索解决方案空间（以一种允许偶尔移动到更差的解决方案的方式）来找到近似最优解，这有助于避免陷入局部最小值。
• 蚁群优化： 这种算法的灵感来自蚂蚁寻找从蚁群到食物来源的路径的行为。它是一种更复杂的概率技术，用于解决可以映射到在图中找到良好路径的计算问题。

解决旅行推销员问题的时间复杂度

为了快速获得近似最优解，我们可以使用贪心算法，在每一步中都前往最近的未访问城市，就像本页的第二个模拟一样。

以这种贪婪的方式解决旅行推销员问题意味着，在每一步中，都会比较当前城市到所有其他未访问城市的距离，这给了我们 \(O(n^2) \) 的时间复杂度。

但是，要找到所有最短路线中的一条需要更多操作，而完成这项操作的时间复杂度是 \(O(n!)\)，如前所述，这意味着对于 4 个城市，有 4! 种可能的路线，这与 \(4 \cdot 3 \cdot 2 \cdot 1 = 24\) 相同。对于 12 个城市，比如 \(12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479,001,600\) 种可能的路线！

在下图中，查看贪心算法 \(O(n^2)\) 的时间复杂度，以及通过比较所有路线 \(O(n!)\) 来找到最短路线的时间复杂度。

但是，我们可以做两件事来减少需要检查的路线数量。

在旅行推销员问题中，路线在同一个地方开始和结束，形成一个循环。这意味着最短路线的长度与我们从哪个城市开始无关。这就是为什么我们在上面的模拟中选择了一个固定的城市作为起点，这将可能的路线数量从 \(n!\) 减少到 \((n-1)!\)。

另外，由于这些路线是循环的，路线的方向相同，距离也相同，因此我们实际上只需要检查一半路线的距离，因为另一半只是相反方向的相同路线，所以我们需要检查的路线数量实际上是 \( \frac{(n-1)!}{2}\)。

但是，即使我们可以将需要检查的路线数量减少到 \( \frac{(n-1)!}{2}\)，时间复杂度仍然是 \( O(n!)\)，因为对于非常大的 \(n\)，将 \(n\) 减少 1 并除以 2 不会显着改变时间复杂度随 \(n\) 增加而增长的方式。

要更好地理解时间复杂度，请访问 此页面。

实际旅行商问题更为复杂

在旅行商问题中，图中的边权告诉我们从一个点到另一个点的难度，而我们要最小化的就是路线的总边权。

到目前为止，在本页中，边权一直是两点之间的直线距离。这使得解释和显示旅行商问题变得容易得多。

但现实世界中，许多其他因素会影响边权。

1. 障碍物：从一个地方移动到另一个地方时，我们通常会避开树木、河流、房屋等障碍物。这意味着从 A 到 B 的距离更长，需要更多时间，并且需要增加边权值以将其考虑在内，因为它不再是直线。
2. 交通网络：旅行时，我们通常会沿着道路行驶或使用公共交通系统，这也影响了从一个地方到另一个地方的难度（或发送包裹）。
3. 交通状况：交通拥堵也会影响旅行时间，因此也应反映在边权值中。
4. 法律和政治边界：例如，跨越边界可能会使一条路线比另一条路线更难选择，这意味着最短的直线路线可能更慢或更昂贵。
5. 经济因素：使用燃料、使用员工时间、维护车辆，所有这些都会花费资金，也应该计入边权中。

正如您所见，仅使用直线距离作为边权，与实际问题相比可能过于简单。并且针对这种简化的问题模型解决旅行商问题，可能会得到在实践意义上并非最佳的解决方案。

当边长不再是两点之间的直线距离，而是计算机能够很好地处理的其他因素时，很难可视化旅行商问题。