Я пытался написать код грубой алгоритм силы в Python с нуля, который решает проблему Path Кратчайших гамильтон взвешенного полного графа следующим образом:Почему мой самый короткий алгоритм Гамильтонова пути субоптимальный?
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 - количество городов. Кажется, я слишком рано обрезаю некоторые маршруты; вместо этого, я должен сделать что-то вроде:
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)
Вопрос: Что такое простой контрпример, который демонстрирует, почему мой алгоритм не является оптимальным?
Следующий: Является ли мой субоптимальный алгоритм хотя бы некоторым алгоритмом приближения, который использует какую-то жадную эвристику? Или это действительно просто ужасный алгоритм
O(n!)?