python - 为什么我的最短哈密顿路径算法不是最优的？

Question

我试图从头开始用 Python 编写一个强力算法来解决加权完整图的最短哈密顿路径问题，如下所示:

def min_route(cities, distances):
    """Finds the Shortest Hamiltonian Path for a weighted complete graph.

    Args:
        cities (list of string):
            The vertices of the graph.

        distances (dict):
            The distances between any two cities. Maps each origin city to a
            dictionary that maps destination cities to distances, sort of like
            an adjacency matrix. Type: Dict<string, Dict<string, int>>.

    Returns:
        (list of string, int):
            The list of cities in the optimal route and its length.
    """
    if len(cities) < 2:
        return cities, 0

    best_route, min_dist = None, float('inf')
    for i in range(len(cities)):
        first, rest = cities[i], cities[:i] + cities[i+1:]
        sub_route, sub_dist = min_route(rest, distances)
        route = [first] + sub_route
        dist = sub_dist + distances[first][sub_route[0]]
        if dist < min_dist:
            best_route, min_dist = route, dist

    return best_route, min_dist

事实证明，这个算法不起作用，而且它对初始城市列表的顺序很敏感。这让我感到困惑，因为我认为它会枚举所有 n! 可能的城市排列，其中 n 是城市的数量。看来我过早地修剪了一些路线；相反，我应该做类似的事情:

def min_route_length(cities, distances):
    routes = get_a_list_of_all_permutations_of(cities)
    return min(compute_route_length(route, distances) for route in routes)

Question: What is a simple counterexample that demonstrates why my algorithm is suboptimal?

Follow Up: Is my suboptimal algorithm at least some kind of approximation algorithm that uses some kind of greedy heuristic? Or is it really just a terrible O(n!) algorithm?

Answer 1

假设您的图是有向的(从 A 到 B 以及从 B 到 A 可以有不同的权重)，其中一个反例是

   A  B  C
A  x  1  5
B 30  x 10
C 30  9  x

不从 A 开始的路径的成本至少为 30，因此我们不需要考虑它们。对于以 A 开头的路径，您的代码使用 [B, C] 进行递归调用。他们的最佳安排是 C>B，成本为 9，这是递归调用的返回值。然而，整个路径 A>C>B 的成本为 14，而最佳路径 A>B>C 的成本为 11。

你是对的，它是 O(n!)。您只需要向下传递一个额外的参数 - 起点(第一次调用可能为 None)并在计算 dist 时考虑它。