[已解决]有序最短路径问题求助，具体问题如下

TSwangming

小明在一家网络科技服务公司工作，公司在n个城市有网络安全技术巡检维护服务业务，小明所在的公司位于其中的一个城市，公司根据业务需要，计划派小明到其中m城市分别去为客户做相应的服务工作。小明计划每完成一个城市客户的服务工作后，直接从该城市去往下一个城市，完成公司指派的所有城市的服务工作后，返回公司所在城市。出发前小明按照客户服务约定顺序，列出了前往各城市的次序，按照公司规定的出差旅途费用按照每公里1元计算，公司希望小明提交一个最少的差旅费用清单。请你设计一个算法并编写程序帮助小明列出到每一个计划前去的城市的费用及总费用清单，并通过程序验证该方案的正确性，分析算法的时间复杂度。

最佳答案

月排行榜 / 总排行榜

小甲鱼

2022-5-20 22:08:49

import sys

def tsp(distances):
    n = len(distances)
    all_points_set = set(range(n))

    # memo keys: tuple(sorted_points_in_path, last_point_in_path)
    # memo values: tuple(cost_thus_far, next_to_last_point_in_path)
    memo = {(tuple([i]), i): tuple([0, None]) for i in range(n)}
    queue = [(tuple([i]), i) for i in range(n)]

    while queue:
        prev_visited, prev_last_point = queue.pop(0)
        prev_dist, _ = memo[(prev_visited, prev_last_point)]

        to_visit = all_points_set.difference(set(prev_visited))
        for new_last_point in to_visit:
            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))
            new_dist = prev_dist + distances[prev_last_point][new_last_point]

            if (new_visited, new_last_point) not in memo:
                queue += [(new_visited, new_last_point)]
            memo[(new_visited, new_last_point)] = min(
                memo.get((new_visited, new_last_point), (float('inf'), None)),
                (new_dist, prev_last_point))

    optimal_path, optimal_cost = retrace_optimal_path(memo, n)

    return optimal_path, optimal_cost

def retrace_optimal_path(memo: dict, n: int) -> [[int], float]:
    points_to_retrace = tuple(range(n))

    full_path_memo = dict((k, v) for k, v in memo.items() if k[0] == points_to_retrace)
    path_key = min(full_path_memo.keys(), key=lambda x: full_path_memo[x][0])

    last_point = path_key[1]
    optimal_cost, next_to_last_point = memo[path_key]

    optimal_path = [last_point]
    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))

    while next_to_last_point is not None:
        path_key = (points_to_retrace, next_to_last_point)
        _, next_to_last_point = memo[path_key]

        optimal_path = [path_key[1]] + optimal_path
        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({path_key[1]})))

    return optimal_path, optimal_cost

在这段代码中，distances是一个二维数组，表示每两个城市之间的距离。tsp函数返回一个元组，第一个元素是一个列表，表示最优路径（城市的顺序），第二个元素是这个路径的总成本。

这个算法的时间复杂度是O(n^2 * 2^n)，空间复杂度是O(n * 2^n)。这是因为算法需要枚举所有可能的路径，并且需要记住之前计算过的路径的成本。其中，n是城市的数量。

请注意，这个算法假设距离矩阵是对称的，也就是说，从城市A到城市B的距离和从城市B到城市A的距离是相同的。如果这个假设不成立，那么你需要修改这个算法，使其可以处理这种情况。

跳转到最佳答案楼层

小甲鱼

import sys

def tsp(distances):
    n = len(distances)
    all_points_set = set(range(n))

    # memo keys: tuple(sorted_points_in_path, last_point_in_path)
    # memo values: tuple(cost_thus_far, next_to_last_point_in_path)
    memo = {(tuple([i]), i): tuple([0, None]) for i in range(n)}
    queue = [(tuple([i]), i) for i in range(n)]

    while queue:
        prev_visited, prev_last_point = queue.pop(0)
        prev_dist, _ = memo[(prev_visited, prev_last_point)]

        to_visit = all_points_set.difference(set(prev_visited))
        for new_last_point in to_visit:
            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))
            new_dist = prev_dist + distances[prev_last_point][new_last_point]

            if (new_visited, new_last_point) not in memo:
                queue += [(new_visited, new_last_point)]
            memo[(new_visited, new_last_point)] = min(
                memo.get((new_visited, new_last_point), (float('inf'), None)),
                (new_dist, prev_last_point))

    optimal_path, optimal_cost = retrace_optimal_path(memo, n)

    return optimal_path, optimal_cost

def retrace_optimal_path(memo: dict, n: int) -> [[int], float]:
    points_to_retrace = tuple(range(n))

    full_path_memo = dict((k, v) for k, v in memo.items() if k[0] == points_to_retrace)
    path_key = min(full_path_memo.keys(), key=lambda x: full_path_memo[x][0])

    last_point = path_key[1]
    optimal_cost, next_to_last_point = memo[path_key]

    optimal_path = [last_point]
    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))

    while next_to_last_point is not None:
        path_key = (points_to_retrace, next_to_last_point)
        _, next_to_last_point = memo[path_key]

        optimal_path = [path_key[1]] + optimal_path
        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({path_key[1]})))

    return optimal_path, optimal_cost

在这段代码中，distances是一个二维数组，表示每两个城市之间的距离。tsp函数返回一个元组，第一个元素是一个列表，表示最优路径（城市的顺序），第二个元素是这个路径的总成本。

这个算法的时间复杂度是O(n^2 * 2^n)，空间复杂度是O(n * 2^n)。这是因为算法需要枚举所有可能的路径，并且需要记住之前计算过的路径的成本。其中，n是城市的数量。

请注意，这个算法假设距离矩阵是对称的，也就是说，从城市A到城市B的距离和从城市B到城市A的距离是相同的。如果这个假设不成立，那么你需要修改这个算法，使其可以处理这种情况。

923131053

。

volcano666

题目是不是不全呀

小甲鱼

旅行商问题噢~