На этом шаге мы рассмотрим реализацию такого поиска.
Теперь мы можем сгенерировать все перестановки для списка городов, но это не совсем то же самое, что путь для задачи коммивояжера. Напомню, что в задаче о коммивояжере продавец должен в конце вернуться в тот город, с которого начал. Мы можем легко добавить первый город в перестановке в ее конец, используя генератор списков.
tsp_paths: List[Tuple[str, ...]] = [c + (c[0],) for c in city_permutations]
Теперь мы готовы проверить все сгенерированные пути. Поиск методом грубой силы просматривает каждый путь в списке и, используя расстояние между двумя городами в таблице поиска (vt_distances), вычисляет суммарное расстояние для каждого пути. Функция выводит кратчайший путь и суммарное расстояние для него.
if __name__ == "__main__": best_path: Tuple[str, ...] min_distance: int = 99999999999 # произвольное большое число for path in tsp_paths: distance: int = 0 last: str = path[0] for next in path[1:]: distance += vt_distances[last][next] last = next if distance < min_distance: min_distance = distance best_path = path print(f"Самый короткий путь между {best_path} составляет {min_distance} миль.")
Наконец, мы можем перебрать методом грубой силы все города Вермонта и найти кратчайший путь через заданные пять городов. Результат работы программы должен выглядеть примерно так, а лучший путь показан на рисунке 1.
Самый короткий путь между
('Ратленд', 'Берлингтон', 'Уайт-Ривер', 'Браттлборо', 'Беннингтон', 'Ратленд')
составляет 318 миль.
Рис.1. Кратчайший путь для коммивояжера, позволяющий посетить все пять городов в штате Вермонт
На следующем шаге мы рассмотрим переход на следующий уровень.
