Практическое применение — решение задачи коммивояжера

Жадный алгоритм — это быстрая и простая стратегия поиска глобального оптимального значения для многоступенчатых задач. Мы выбираем локаль­ ные оптимальные значения, но не проверяем, являются ли они при этом глобально оптимальными. Обычно жадный алгоритм не приводит к значе­ нию, которое можно считать глобально оптимальным (если только нам не повезет). Однако поиск глобального оптимального значения — непростая задача. Следовательно, жадный алгоритм работает быстрее по сравнению с алгоритмами «разделяй и властвуй» и алгоритмами динамического про­ граммирования.

Как правило, жадный алгоритм состоит из следующих шагов:

1.Предположим, что у нас есть набор данных D‚ из которого мы выберем эле­ мент k.

2.Предположим, что вариантом решения (или сертификатом) выступает S. Рассмотрим возможность включения k в решение S. Если включение воз­ можно, то решением будет Union (S, e).

3.Повторяем процесс до тех пор, пока S не заполнится или D не окажется ис­ черпанным.

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ — РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА

Давайте рассмотрим упоминаемую ранее задачу коммивояжера (TSP — travelling salesman problem). Это хорошо известная задача, придуманная в качестве своего рода вызова в 1930-х годах. Она относится к классу NPтрудных задач. Для начала мы можем случайным образом сгенерировать маршрут, отвечающий условию посещения всех городов, не заботясь об оп­ тимальном решении. Затем будем работать над улучшением решения на каждой итерации. Каждый маршрут, сгенерированный в итерации, называет­ ся вариантом решения (или сертификатом). Доказательство того, что серти­ фикат является оптимальным, требует экспоненциально возрастающего ко­ личества времени. Вместо этого будем использовать различные решения на основе эвристики, которые генерируют маршруты, близкие к оптимальным, но не оптимальные.

Чтобы выполнить работу, коммивояжеру необходимо посетить определенный список городов (табл. 4.1).

Таблица 4.1

ВВОД Список из n городов (обозначается как V) и расстояний между каждой парой городов, d ij (1 ≤ i, j ≤ n)

ВЫВОД Кратчайший маршрут, который включает в себя каждый город ровно один раз и завершается в исходном городе

Обратите внимание:

zz Расстояния между городами в списке известны.

zzКаждый город в данном списке необходимо посетить только один раз.

Получится ли у нас составить план поездки? Каким будет оптимальное решение, позволяющее свести к минимуму общее расстояние, пройденное коммивояже­ ром?

В табл. 4.2 приведены расстояния между пятью канадскими городами, которые мы можем использовать для TSP.

Таблица 4.2

Обратите внимание, что цель состоит в разработке маршрута, который начи­ нается и заканчивается в исходном городе. Например, типичным маршрутом может быть Оттава — Садбери — Монреаль — Кингстон — Торонто — Оттава с общей длиной пути 484 + 680 + 287 + 263 + 450 = 2164. Является ли он маршрутом‚ при котором продавец преодолеет минимальное расстояние? Каким будет оптимальное решение, позволяющее свести к минимуму общее расстояние, пройденное коммивояжером? Я предлагаю вам подумать над этим и подсчитать.

Использование стратегии полного перебора

Первое решение, которое приходит на ум для задачи TSP, — это использовать полный перебор (brute force, иначе называемый «метод грубой силы») и по­ пытаться найти кратчайший путь, при котором коммивояжер посетит каждый город ровно один раз и вернется в исходный город. Итак, стратегия полного перебора работает следующим образом:

1.Рассчитать все возможные маршруты.

2.Выбрать среди них кратчайший маршрут.

Проблема в том, что для n числа городов существует (n – 1)! возможных марш­ рутов. Это означает, что пять городов дадут 4! = 24 маршрута и мы выберем самый короткий из них. Очевидно, что такой метод сработает лишь потому, что у нас не так много городов. По мере увеличения числа городов полный перебор превращается в неустойчивую стратегию из-за большого количества переста­ новок, генерируемых этим методом.

Давайте посмотрим, как можно реализовать стратегию полного перебора в Python.

Прежде всего обратим внимание, что маршрут {1, 2, 3} представляет собой маршрут из города 1 в город 2 и город 3. Общее расстояние — это все расстояние, пройденное за маршрут. Мы будем считать, что расстояние между городами является кратчайшим, то есть евклидовым.

Определим три служебные функции:

zz distance_points. Вычисляет абсолютное расстояние между двумя точками;

zz distance_tour. Вычисляет общее расстояние, которое коммивояжер должен преодолеть на данном маршруте;

zzgenerate_cities. Случайным образом генерирует набор из n городов, рас­ положенных в прямоугольнике шириной 500 и высотой 300.

Давайте рассмотрим следующий код:

import random

from itertools import permutations alltours = permutations

def distance_tour(aTour):

return sum(distance_points(aTour[i - 1], aTour[i]) for i in range(len(aTour)))

aCity = complex

def distance_points(first, second): return abs(first - second)

def generate_cities (number_of_cities): seed=111;width=500;height=300 random.seed((number_of_cities, seed))

return frozenset(aCity(random.randint(1, width), random.randint(1, height))

for c in range(number_of_cities))

В предыдущем коде мы применили alltours из функции permutations пакета itertools. Мы также представили расстояние комплексным числом. Это озна­ чает следующее:

zz вычисление расстояния между двумя городами a и b сводится к distance (a,b);

zz мы можем создать n-число городов, просто вызвав generate_cities(n).

Теперь давайте определим функцию brute_force, которая генерирует все воз­ можные маршруты через эти города.

Как только она их сгенерирует, будет выбран маршрут с наименьшим расстоя­ нием:

def brute_force(cities):

"Создать все возможные маршруты по городам и выбрать самый короткий." return shortest_tour(alltours(cities))

def shortest_tour(tours): return min(tours, key=distance_tour)

Далее определим служебные функции для визуализации:

zz visualize_tour. Отображает все города и связи на конкретном маршруте. Она также показывает город, с которого начался маршрут.

zzvisualize_segment. Используется функцией visualize_tourдля отображения городов и связей в сегменте.

Взгляните на код:

%matplotlib inline

import matplotlib.pyplot as plt

def visualize_tour(tour, style='bo-'):

if len(tour) > 1000: plt.figure(figsize=(15, 10)) start = tour[0:1]

visualize_segment(tour + start, style)