Задача коммивояжера и методы её решения

Содержание

 

 

 

Введение

Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли (работа «Искусство предположений»), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и  Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало  одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций.  

Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.

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

В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 1. Задача коммивояжера и методы её решения

1.1. Задача  коммивояжера. Общее описание.

Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1, 2, 3 .. n). Тур коммивояжера может быть описан циклической перестановкой t=(j1, j2, .., jn, j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал.

Относительно математизированной формулировки ЗК уместно сделать два замечания.

Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

Сij ≥ 0; Cjj = ∞ (1)

(последнее равенство  означает запрет на петли в  туре), симметричными, т.е. для всех i,j:

Сij = Сji. (2)

и удовлетворять неравенству треугольника, т.е. для всех:

Сij + Сjk ≥ Cik (3)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (1)-(3) не удовлетворяют. Особенно часто нарушается условие (2) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (2) выполнено, и несимметричную - в противном случае. Условия (1)-(3) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1, j2, .., jn, j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём). [5]

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки». [1]

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Методы  решения ЗК

1.2.1. Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. [3]

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

В пользу процедуры «иди в ближайший» можно сказать лишь то, что при старте из одного города она не уступит стратегии «иди в дальнейший».

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, чтоfA/fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

fA/fB ≥1+ nе,

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

Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G (V,E) и по нему составим входную матрицу ЗК:

С[i,j]=  {1,если ребро (i,j) принадлежит Е; 1+nе в противном случае

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nе. Но тогда fA((n-1)+(1+nе) так что fA/fB=1+nе, т.е. превосходит погрешность е на заданную неравенством . О величине е в нашем рассуждении мы не договаривались, так что е может быть произвольно велик.

Таким образом доказана следующая теорема.

Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника.

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт? Рис.1 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья – вершинами.

 

Рисунок 1

Когда через точку проводится линия, то используется два ребра – одно для входа в вершину, одно – для выхода. Если степень вершины нечетна – то в ней линия должна начаться или кончиться. Вершин нечетной степени две: в одной линия начинается, в другой – кончается. Однако имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень. [6]

 

 

 

 

 

 

 

1.2.2. Алгоритм Дейкстры

Алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети.

    В процессе  выполнения этого алгоритма при  переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через ui кратчайшее расстояние от исходного узла 1 до узла i, через dij - длину ребра (i, j). Тогда для узла j определим метку [uj, i] следующим образом:

    [uj, i] = [ui + dij, i], dij ≥ 0

    Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.

    Вычислительная  схема алгоритма состоит из  следующих шагов.

    Шаг 0. Исходному  узлу (узел 1) присваивается метка [0, -]. Полагаем i = 1.

    Шаг i. а) Вычисляются временные метки [ui + dij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если ui + dij < uj, тогда метка [uj, k] заменяется на [ui + dij, i].

    b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [ur, s] с наименьшим значением расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i. [4]

 

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

Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес Сij, причем веса дуг строго положительны (Сij≥0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (Сjj=∞).

В случае, если пара вершин i и j не связана между собой (граф не полносвязный), то соответствующему элементу матрицы стоимости приписываем вес, равный длине минимального пути между вершинами i и j. Если в итоге дуга (i, j) войдет в результирующий контур, то ее необходимо заменить соответствующим ей путем. Матрицу оптимальных путей между всеми вершинами графа можно получить применив алгоритм Данцига или Флойда. [7]

Алгоритм Литтла является частным случаем применения метода "ветвей и границ" для конкретной задачи. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

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

1.В каждой строке матрицы  стоимости найдем минимальный  элемент и вычтем его из  всех элементов строки. Сделаем  это и для столбцов, не содержащих  нуля. Получим матрицу стоимости, каждая строка и каждый столбец  которой содержат хотя бы один  нулевой элемент.

2.Для каждого нулевого  элемента матрицы cij  рассчитаем коэффициент Гij, который равен сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Из всех коэффициентов  Гij выберем такой, который является максимальным Гkl=max{Гij}. В гамильтонов контур вносится соответствующая дуга (k, l).

3.Удаляем k-тую строку  и столбец l, поменяем на бесконечность значение элемента Сl,k (поскольку дуга (k,l) включена в контур, то обратный путь из l в k недопустим).

4.Повторяем алгоритм шага 1, пока порядок матрицы не станет  равным двум.

5.Затем в текущий ориентированный  граф вносим две недостающие  дуги, определяющиеся однозначно  матрицей порядка 2. Получаем гамильтонов  контур.

В ходе решения ведется постоянный подсчет текущего значения нижней границы. Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура. [2]