Задача коммивояжера (развозчика продукции или бродячего торговца).

Решенеие.

Чтобы решить данную задачу, сначала сформулируем следующую теорему, которую примем без доказательства.

Теорема. Если связный граф содержит ровно 2 n вершин нечетной степени, то минимальное число реберно-непересекающихся цепей, на которые можно разбить его ребра, равно n.

Практическое занятие №9

Пути и циклы Гамильтона. Алгоритм Литтла.

 

Основные теоретические сведения

Пути и циклы Гамильтона

В 1857 году математик Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек. В любом случае она включала додекаэдр, т.е. правильный многогранник, 12 граней которых представляли собой равные правильные пятиугольники. В каждом из 20 углов, или вершин тела, просверливалась дырочка, в которую вставлялся колышек, изображавший город. Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.

Проблема в таком случае сводилась к нахождению цикла в графе, проходящего через каждую вершину только один раз, исключая начальную. Отсюда любой цикл, обладающий таким свойством, называется гамильтоновым циклом. Этот цикл в некотором смысле противоположен эйлерову циклу, который проходит через все ребра только один раз. До определенного момента оба цикла могут показаться похожими, но на самом деле цикл Гамильтона намного сложнее.

Определение. Пусть G (V, E) – граф. Гамильтонов путь – это простой путь, который проходит через каждую вершину графа G. Гамильтонов цикл – это простой цикл, который проходит через каждую вершину графа G.

 

Задача коммивояжера (развозчика продукции или бродячего торговца).

1.2.1.Формулировка задачи: коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

1.2.2. Математическая модель задачи.

Пусть C =[ c_ij ] – матрица расстояний между городами. Для составления математической модели задачи обозначим через x_ij факт переезда коммивояжером из города i в город j. Поскольку переезд из одного города в другой может осуществляться только один раз, то x_ij должны принимать только два значения: 1 или 0, т.е. булевы значения. Таким образом:

Математическая модель задачи примет следующий вид:

(1)

(2)

(3)

Система ограничений (2) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз, а система (3) – маршрута, когда он выезжает из каждого города только один раз. К сожалению, эти ограничения недостаточны, так как среди допустимых ими решений имеются маршруты, не образующие полный цикл, включающий все города. Устранение подциклов достигается при добавлении системы ограничений:

, (4)

где переменные u могут принимать произвольные действительные значения.

 

1.2.3.Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла).

Если считать города вершинами графа, а коммуникации – его дугами, то нахождение минимального пути, проходящего один и только один раз через каждый город с возвращением в исходную точку можно рассматривать как нахождение на графе гамильтонова цикла минимальной длины.

Рассмотрим алгоритм поиска гамильтонова цикла минимальной длины на графе с вершинами (алгоритм Литтла). Если между вершинами и нет дуги, то ставится символ . Этот же символ ставится на главной диагонали, что означает запрет на возвращение в вершину, через которую уже проходил цикл. Основная идея метода состоит в том, что сначала строят нижнюю границу длин множества гамильтоновых циклов . Затем множество циклов разбивается на два подмножества таким образом, что первое подмножество состояло из гамильтоновых циклов, содержащих некоторую дугу , а другое подмножество не содержало эту дугу. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества гамильтоновых циклов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы для всего множества гамильтоновых циклов, то есть

, .

Сравнивая нижние границы и подмножеств и , можно выделить среди них то, которое с большей вероятностью содержит гамильтонов цикл минимальной длины. Затем одно из подмножеств или по аналогичному правилу разбивается на два новых и . Для них снова отыскиваются нижние границы и и т.д.

 

Процесс ветвления продолжается до тех пор, пока не отыщется единственный гамильтонов цикл. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергают дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего гамильтонова цикла. Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины цикла. Его называют вторым рекордом. Процесс решения заканчивается тогда, когда будут проанализированы все подмножества.

С помощью метода ветвей и границ с использование современных ЭВМ можно решать задачи коммивояжера для . В связи с малой эффективностью точных методов получили широкое применение эвристические. В настоящее время существует более ста приближенных методов решения задачи коммивояжера, среди которых наиболее прост метод ближайшего соседа. Он реализует требование включать в искомый замкнутый цикл вершину, ближайшую к только что найденной. Алгоритм «ближайшего соседа» состоит в последовательном добавлении к начальной вершине следующей ближайшей к ней и т.д. Метод очень прост, однако степень приближения к оптимальному решению существенно зависит от выбора начальной вершины. Поэтому алгоритм целесообразно применять, начиная с каждой вершины, и затем выбрать замкнутый цикл наименьшей длины. При этом, если ближайший сосед для некоторой вершины уже вошел в цикл, то берется следующая по близости вершина и т.д. Например, используя данный метод для полного взвешенного графа с n вершинами, потребуется рассмотреть n! гамильтоновых циклов, из которых выбирается цикл наименьшей длины.

 

Алгоритм Литтла.

Пусть известна матрица весов некоторого орграфа, вершины которого занумеруем числами от 1 до :

,

где – вес дуги, соединяющей вершины и j, где .

Символ ставится для блокировки дуг графа, которые явно не включаются в гамильтонов цикл, т.е. в расчет не берутся дуги и . Можно показать, что оптимальность решения не меняется от прибавления некоторого числа к строке или столбцу матрицы W.

Алгоритм Литтла разбивается на несколько шагов.

Шаг 1. Приведение исходной матрицы.

В каждом столбце и в каждой строке матрицы W нужно получить хотя бы один нуль. Для этого, например, в первом столбце выбираем минимальный элемент и вычитаем его из всех элементов первого столбца. Аналогично поступаем с остальными столбцами. Если при этом в некоторых строках не появляются нули, то для них осуществляем ту же процедуру.

После этого вычисляем константу приведения – сумму минимальных элементов столбцов и строк, которые вычитались. Получаем приведенную матрицу с константой приведения .

Шаг 2. Определение степеней нулей.

Находим степени каждого нуля – сумму минимальных элементов строки и столбца , в которых стоит этот нуль, без учета самого нуля. Нуль с максимальной степенью определяет дугу , которая вероятнее всего войдет в гамильтонов цикл. Например, если нуль с максимальной степенью находится на пересечении второй строки и третьего столбца, то дуга , вероятнее всего, войдет в гамильтонов цикл.

Шаг 3. Ветвление.

На самом деле, дуга, соответствующая максимальной степени нуля, может, как входить в гамильтонов цикл, так и не входить в него. Поэтому дальше нужно рассмотреть сразу два случая.

Первый случай. Возможно, дуга вошла в гамильтонов цикл. Блокируем ее, полагая . Строку и столбец вычеркиваем. Если требуется, приводим полученную матрицу меньшего порядка с константой приведения .

Второй случай. Дуга не вошла в гамильтонов цикл. Полагаем . Если требуется, приводим полученную матрицу с константой приведения .

Если , то шаги 2, 3 повторяем с матрицей .

Если , то шаги 2, 3 повторяем с матрицей . И так до тех пор, пока не дойдем до матрицы второго порядка, содержащей два нуля:

,

где и – некоторые числа или . Эти нули соответствуют двум последним дугам гамильтонова цикла: , . При этом .

Если , где , то задача решена. Если же для некоторого получается , то всю процедуру следует провести с матрицей . На последнем этапе получим новое значение функции : . Это значение сравниваем с , то есть новый процесс продолжается до тех пор, пока новые .