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

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，即递归调用的 return 值。但是，整个路径 A>C>B 的成本为 14，而最佳路径 A>B>C 的成本为 11。

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

时考虑它

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

Why is my Shortest Hamiltonian Path algorithm suboptimal?

python

algorithm

greedy

traveling-salesman