Алгоритмы неформально. Инструкция для начинающих питонистов - [46]
import math
def howfar(lines):
distance = 0
for j in range(0,len(lines)):
distance += math.sqrt(abs(lines[j][1][0] - lines[j][0][0])**2 + \
abs(lines[j][1][1] - lines[j][0][1])**2)
return(distance)
Функция получает на входе список отрезков и выводит сумму их длин. Имея такие функции, мы можем вызвать их вместе с маршрутом для определения общего расстояния, которое преодолеет наш коммивояжер:
totaldistance = howfar(genlines(cities,itinerary))
print(totaldistance)
При выполнении этого кода оказалось, что значение totaldistance равно приблизительно 16.81. Вы получите те же результаты, если будете использовать то же значение инициализации. Если выбрать другое значение инициализации или набор городов, то результат будет слегка отличаться от приведенного.
Чтобы получить представление о том, что означает этот результат, полезно построить диаграмму маршрута. Для этого мы создадим функцию plotitinerary():
import matplotlib.collections as mc
import matplotlib.pylab as pl
def plotitinerary(cities,itin,plottitle,thename):
lc = mc.LineCollection(genlines(cities,itin), linewidths=2)
fig, ax = pl.subplots()
ax.add_collection(lc)
ax.autoscale()
ax.margins(0.1)
pl.scatter(x, y)
pl.title(plottitle)
pl.xlabel('X Coordinate')
pl.ylabel('Y Coordinate')
pl.savefig(str(thename) + '.png')
pl.close()
Функция plotitinerary() получает аргументы cities, itin, plottitle и thename, где cities — список городов, itin — маршрут, который вы хотите нанести на диаграмму, plottitle — заголовок, который будет выводиться в верхней части диаграммы, а thename — имя, которое присваивается выходному файлу в формате png. Функция использует модуль pylab для построения диаграммы и модуль collections из matplotlib для создания набора отрезков. Затем она выводит точки маршрута и соединяющие их отрезки.
При построении диаграммы маршрута с помощью вызова plotitinerary(cities,itinerary,'TSP-RandomItinerary','figure2') вы получите диаграмму, как на рис. 6.2.
Рис. 6.2. Маршрут, полученный при посещении городов в случайном порядке, в котором они были созданы
По рис. 6.2 нетрудно догадаться, что мы еще не нашли лучшего решения задачи коммивояжера. Бедному коммивояжеру приходится несколько раз метаться по всей стране в отдаленные города; совершенно очевидно, что он мог бы действовать намного эффективнее, если бы остановился в других городах на этом пути. В оставшейся части данной главы мы будем использовать алгоритмы для нахождения маршрута с минимальным расстоянием.
Первое возможное решение, которое мы обсудим, будет самым простым, но оно же оказывается наименее эффективным. После этого рассмотрим решения, которые за счет некоторого усложнения значительно улучшают быстродействие.
Ум против грубой силы
Казалось бы, можно составить список всех возможных маршрутов, соединяющих города, проверить их все и посмотреть, какой из них лучше. Если вы хотите посетить три города, нетрудно составить полный список всех возможных порядков их посещения:
• 1, 2, 3;
• 1, 3, 2;
• 2, 3, 1;
• 2, 1, 3;
• 3, 1, 2;
• 3, 2, 1.
Сравнение длин всех маршрутов и определение лучшего из них не займет много времени. Такое решение называется методом грубой силы. Имеется в виду не физическая сила, а проверка полного списка, основанная на вычислительной мощности процессора вместо интеллекта разработчика алгоритма, который мог бы найти более элегантное решение с меньшим временем выполнения.
Иногда метод грубой силы оказывается именно тем, чем нужно. Такие решения проще программируются и надежно работают. Их главная слабость — время выполнения, которое никогда не бывает лучше, а обычно оказывается намного хуже, чем у алгоритмических решений.
В задаче коммивояжера время выполнения растет слишком быстро, чтобы метод грубой силы можно было реально применить более чем для 20 городов. Чтобы убедиться в этом, подумайте, сколько возможных маршрутов пришлось бы проверить, если вы пытаетесь найти все возможные порядки посещения четырех городов.
1. При выборе первого города возможны четыре варианта, так как ни один из четырех городов еще не был посещен. Таким образом, общее количество вариантов выбора первого города равно 4.
2. При выборе второго города возможны три варианта, так как городов всего четыре и один из них уже был посещен. Таким образом, общее количество вариантов выбора первых двух городов равно 4 × 3 = 12.
3. При выборе третьего города остаются два варианта, так как городов всего четыре и мы уже посетили первые два. Следовательно, общее количество способов выбора первых трех городов равно 4 × 3 × 2 = 24.
4. При выборе четвертого города остается всего один вариант, так как из четырех городов три уже были посещены. Таким образом, общее количество способов выбора всех четырех городов составит 4 × 3 × 2 × 1 = 24.
Нетрудно заметить закономерность: для N городов общее количество возможных маршрутов составит N× (N – 1) × (N – 2) × ... × 3 × 2 × 1, или N факториал (обозначается N!). Факториал растет невероятно быстро: если значение 3! равно всего 6 (что можно легко перебрать даже без компьютера), то для 10! оно превышает 3 миллиона (достаточно просто перебирается методом грубой силы на современном компьютере). Далее значение 18! превышает 6 квадриллионов, 25! превышает 15 септиллионов, а значения 35! и выше выходят за границы того, что можно сделать методом грубой силы при современном уровне технологий и предполагаемого срока жизни Вселенной.
