На этом шаге мы рассмотрим организацию такого перебора.
Наивный подход к решению задачи коммивояжера требует сгенерировать все возможные варианты перестановок городов. Существует множество алгоритмов генерации перестановок, они довольно просты, так что вы почти наверняка сможете придумать такой алгоритм самостоятельно.
Один из типичных подходов - поиск с возвратом. Впервые он встретился нам в 41 шаге в контексте решения задачи с ограничениями. При решении такой задачи поиск с возвратом используется после того, как найдено частичное решение, которое не удовлетворяет ограничениям задачи. В таком случае вы возвращаетесь к более раннему состоянию и продолжаете поиск по пути, отличному от того, который привел к частично неверному решению.
Найти все перестановки элементов списка (в частности, наших городов), также можно с помощью поиска с возвратом. Чтобы после перестановки элементов перейти к последующим перестановкам, можно вернуться к состоянию, предшествовавшему тому, при котором была выполнена перестановка, и выбрать другую комбинацию для перехода по другому пути.
К счастью, нет необходимости изобретать колесо и писать алгоритм генерации перестановок, потому что в стандартной библиотеке Python в модуле itertools есть функция permutations(). В следующем фрагменте кода генерируются все перестановки городов штата Вермонт, которые должен будет посетить наш коммивояжер. Поскольку городов всего пять, то это будет 5! (5 факториал), или 120 перестановок.
vt_cities: Iterable[str] = vt_distances.keys() city_permutations: Iterable[Tuple[str, ...]] = permutations(vt_cities)
На следующем шаге мы рассмотрим поиск методом грубой силы.
