Обратите внимание, что мы используем функцию tsp() для создания маршру­ та по 10 городам. Поскольку n = 10, то мы получим (10-1)! = 362 880 возможных перестановок. Если n увеличивается, количество перестановок резко возрас­ тает и стратегию полного перебора использовать уже нельзя.

Использование жадного алгоритма

Если для решения TSP мы используем жадный алгоритм, то на каждом шаге можем выбрать город, который выглядит приемлемым вариантом, вместо того чтобы искать идеальное решение. Поэтому всякий раз, когда нам нужно выбрать город, мы просто выбираем ближайший, не утруждая себя проверкой того, яв­ ляется ли этот выбор глобально оптимальным.

Стратегия жадного алгоритма проста:

1.Начать с любого города.

2.На каждом этапе продолжать строить маршрут, перемещаясь в следующий ближайший непосещенный город.

3.Повторить шаг 2.

Определим функцию с именем greedy_algorithm, которая реализует эту логику:

def greedy_algorithm(cities, start=None): C = start or first(cities)

tour = [C]

unvisited = set(cities - {C}) while unvisited:

C = nearest_neighbor(C, unvisited) tour.append(C) unvisited.remove(C)

return tour

def first(collection): return next(iter(collection))

def nearest_neighbor(A, cities):

return min(cities, key=lambda C: distance_points(C, A))

Теперь используем greedy_algorithm для создания маршрута по 2000 городам (рис. 4.8).

Обратите внимание, что для создания маршрута по 2000 городам потребовалось всего 0,514 секунды. Если бы мы использовали стратегию полного перебора, мы получили бы (2000 – 1)! перестановок, то есть почти бесконечное количество.