Реферат: Задача коммивояжера

Введение

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

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

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

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

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

В1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую вотыскании такого пути, проходящего через все вершины (города, пунктыназначения) графа, изображенного на рис. 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=∞ (2)

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

Сij= Сji. (3)

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

Сij+ Сjk³Cik (4)

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

Второезамечание касается числа всех возможных туров. В несимметричной ЗК все туры 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, тоон пройдёт по циклу, который включает все вершины по одному разу. Такой циклназывается гамильтоновым циклом. Незамкнутый гамильтонов цикл называетсягамильтоновой цепью (гамильтоновым путём).

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

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

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

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

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

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

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

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

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

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

fA/fB ≥1+ nε, (5)

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

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

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

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

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

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

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

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

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

Вернои обратное утверждение: если все вершины имеют четную степень, то фигуру можнонарисовать одной незамкнутой линией. Действительно, процесс проведения линииможет кончиться, только если линия придет в вершину, откуда уже выхода нет: всеребра, присоединенные к этой вершине (обычно говорят: инцидентные этойвершине), уже прочерчены. Если при этом нарисована вся фигура, то нужноеутверждение доказано; если нет, удалим уже нарисованную часть G’. После этого от графа останется одна или несколькосвязных компонент; пусть G’ – одна изтаких компонент. В силу связности исходного графа G, G’ и G’’ имеют хоть одну общую вершину, скажем,  v. Если в G’’ удаленыкакие-то ребра, то по четному числу от каждой вершины. Поэтому G’’ – связный и все его вершины имеют четную степень. Построимцикл в G’’ (может быть, не нарисовав всего G’’) и через v добавимпрорисованную часть G’’ к G’. Увеличивая таким образом прорисованную часть G’, мы добьемся того, что G’ охватит весь G.

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

Эйлеровцикл в графе существует тогда и только тогда, когда (1) граф связный и (2) всеего вершины имеют четные степени.

1.2.2. Деревянный алгоритм.

Теперьможно обсудить алгоритм решения ЗК через построение кратчайшего остовногодерева. Для краткости будет называть этот алгоритм деревянным.

Вначалеобсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис.5.Если справедливо неравенство треугольника, то d[1,3]£d[1,2]+d[2,3] и d[3,5]£d[3,4]+d[4,5]                                                      Сложив эти два неравенства, получим d[1,3]+d[3,5]£d[1,2]+d[2,3]+d[3,4]+d[4,5]. По неравенству треугольника получим. d[1,5]£d[1,3]+d[3,5]. Окончательно

d[1,5]£ d[1,2]+d[2,3]+d[3,4]+d[4,5]

Итак,если справедливо неравенство треугольника, то для каждой цепи верно, чторасстояние от начала до конца цепи меньше (или равно) суммарной длины всехребер цепи. Это обобщение расхожего убеждения, что прямая короче кривой.

Вернемсяк ЗК и опишем решающий ее деревянный алгоритм.

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

Построимэйлеров цикл G, начиная с вершины 1, цикл задаетсяперечнем вершин.

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

Пример1. Дана полная сеть, показанная на рис.5. Найти тур жадным и деревяннымалгоритмами.

/>

- 1 2 3 4 5 6 1 - 6 4 8 7 14 2 6 - 7 11 7 10 3 4 7 - 4 3 10 4 8 11 4 - 5 11 5 7 7 3 5 - 7 6 14 10 10 11 7 - табл. 1

/>

Решение.Жадный алгоритм (иди в ближайший город из города 1) дает тур1–(4)–3-(3)–5(5)–4–(11)–6–(10)–2–(6)–1, где без скобок показаны номера вершин,а в скобках – длины ребер. Длина тура равна 39, тур показана на рис. 5.

2.Деревянный алгоритм вначале строит остовное дерево, показанное на рис. 6штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рис. 6.

Теорема.Погрешность деревянного алгоритма равна 1.

Доказательство.Возьмем минимальный тур длины fB и удалим изнего максимальное ребро. Длина получившейся гамильтоновой цепи LHC меньше fB. Но эту же цепь можно рассматривать как остовное дерево, т. к.эта цепь достигает все вершины и не имеет циклов. Длина кратчайшего остовногодерева  LMT меньше или равна LHC. Имеем цепочку неравенств

fB>LHC³LMT (6)

Ноудвоенное дерево – оно же эйлеров граф – мы свели к туру посредствомспрямлений, следовательно, длина полученного по алгоритму тура удовлетворяетнеравенству

2LMT>fA (7)

Умножая(6) на два и соединяя с (7), получаем цепочку неравенств

2fB>2LHC³2LMT³fA (8)

Т.е. 2fB>fA, т.е. fA/fB>1+e; e=1.

Теоремадоказана.

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

Известноеще несколько простых алгоритмов, гарантирующих в худшем случае e=1. Для того, чтобы найти среди нихалгоритм поточнее, зайдем с другого конца и для начала опишем «brute-force enumeration» — «перебор животной силой»,  как егоназывают в англоязычной литературе. Понятно, что полный перебор практическиприменим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано вследующей таблице, растет удручающе быстро:

5! 10! 15! 20! 25! 30! 35! 40! 45! 50! ~102 ~106 ~1012 ~1018 ~10125 ~1032 ~1040 ~1047 ~1056 ~1064

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

Пустьимеется некоторый алфавит и наборы символов алфавита (букв), называемыесловами. Буквы в алфавите упорядочены: например, в русском алфавите порядокбукв аµбµя (символ µ читается«предшествует)». Если задан порядок букв, можно упорядочить и слова. Скажем,дано слово u=(u1,u2,..,um) – состоящее из букв u1,u2,..,um — и слово v =(v1,v2,..,vb). Тогда если u1µv1, то и uµv, если же u1=v1, тосравнивают вторые буквы и т.д. Этот порядок слов и называетсялексикографическим. Поэтому в русских словарях (лексиконах) слово «абажур»стоит раньше слова «абака». Слово «бур» стоит раньше слова «бура», потому чтопробел считается предшествующим любой букве алфавита.

Рассмотрим,скажем, перестановки из пяти элементов, обозначенных цифрами 1..5.Лексикографически первой перестановкой является 1-2-3-4-5, второй – 1-2-3-5-4,…, последней – 5-4-3-2-1. Нужно осознать общий алгоритм преобразования любойперестановки в непосредственно следующую.

Правилотакое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановкесправа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примереэто 3 после 5). Это число, Pi-1 надоувеличить, поставив вместо него какое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1,несомненно, найдется, так как Pi-1< Pi. Если есть несколько больших чисел, то,очевидно, надо ставить меньшее из них. Пусть это будет Pj,j>i-1. Затем число Pi-1 и все числаот Pi до Pn, не считая Pj нужноупорядочить по возрастанию. В результате получится непосредственно следующаяперестановка, в примере –   1-4-2-3-5. Потом получится 1-4-2-5-3 (тот жеалгоритм, но упрощенный случай) и т.д.

Нужнопонимать, что в ЗК с n городами ненужны все перестановки из n элементов.Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элементсоединен с первым) задают один и тот же тур, считанный сперва с города 1, апотом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединятьк нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК(мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).

Данныйалгоритм описан на языке Паскаль (см. Приложения).

Пример2. Решим ЗК, поставленную в Примере 1 лексикографическим перебором. Приведеннаявыше программа напечатает города, составляющие лучший тур: 1-2-6-5-4-3 и его длину 36.

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

1.2.3. Метод ветвей и границ

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

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

 Изложималгоритм Литтла на примере 1 предыдущего раздела… Повторно запишем матрицу:

- 1 2 3 4 5 6 1 - 6 4 8 7 14 2 6 - 7 11 7 10 3 4 7 - 4 3 10 4 8 11 4 - 5 11 5 7 7 3 5 - 7 6 14 10 10 11 7 - табл. 2 - 1 2 3 4 5 6 1 - 2 4 3 10 2 - 1 5 1 4 3 1 4 - 1 7 4 4 7 - 1 7 5 4 4 2 - 4 6 7 3 3 4 - табл. 3 - 1 2 3 4 5 6 1 - 3 3 6 2 - 1 4 1 3 1 2 - 3 4 4 5 - 1 3 5 4 2 1 - 6 7 1 3 3 - 2 1 4 табл. 4 /> /> /> /> /> /> /> /> /> />

Намбудет удобнее трактовать Сij как стоимостьпроезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку влюбом туре нужно въехать в город j. Но посколькувсе туры равномерно подешевели, то прежний минимальный тур будет и теперьстоить меньше всех. Добрый же поступок мэра можно представить как уменьшениевсех чисел j-го столбца матрицы С на 5. Если бы мэрхотел спровадить коммивояжеров из  j-гогорода и установил награду за выезд в размере 10 долларов, это можно было бывыразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, номинимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитаялюбую константу из всех элементов любой строки или столбца матрицы С, мыоставляем минимальный тур минимальным.

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

Прочеркипо диагонали означают, что из города i в городi ходить нельзя. Заметим, что суммаконстант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна34.

 Тур можно задать системой из шести подчеркнутых (выделенных другим цветом)элементов матрицы С, например, такой, как показано на табл. 2. Подчеркиваниеэлемента       означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно бытьшесть, так как в туре из шести городов есть шесть ребер. Каждый столбец долженсодержать ровно один подчеркнутый элемент  (в каждый город коммивояжер въехалодин раз), в каждой строке должен быть ровно один подчеркнутый элемент (изкаждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементыдолжны описывать один тур, а не несколько меньших циклов. Сумма чиселподчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, этотот минимальный тур, который получен лексикографическим перебором.

Теперьбудем рассуждать от приведенной матрицы на табл. 2. Если в ней удастсяпостроить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющуютрем вышеописанным требованиям, и этими подчеркнутыми элементами будут тольконули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будетминимальным и для исходной матрицы С, только для того, чтобы получитьправильную стоимость тура, нужно будет обратно прибавить все константыприведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальныйтур не может быть меньше 34. Мы получили оценку снизу для всех туров.

Теперьприступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль вклетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 вгород 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равнонужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену,указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти дваминимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надозаплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены натабл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выбереммаксимальную из этих оценок (в примере есть несколько оценок, равных единице,выберем первую из них, в клетке (1,2)).

Итак,выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро(1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придетсяприплатить еще 1, так что туры этого класса стоят 35 или больше.

Чтокасается первого класса, то в нем надо рассмотреть матрицу на табл. 6 свычеркнутой первой строкой и вторым столбцом.

1 2 3 4 5 6 1 - 01 3 3 6 2 01 - 1 4 1 3 1 2 - 01 3 4 4 5 01 - 1 3 5 4 2 1 - 6 7 1 3 3 01 - табл. 5

 

1 3 4 5 6 2 01 1 4 1 3 1 - 01 3 4 4 01 - 1 3 5 4 1 - 6 7 3 3 01 - табл. 6 1 3 4 5 6 2 01 1 4 1 3 03 - 01 3 4 3 01 - 1 3 5 3 1 - 6 6 3 3 01 - табл. 7 3 4 5 6

 

2 1 4 1

 

4 01 - 1 3

 

5 1 -

 

6 3 3 01 -

 

табл. 8

Дополнительнов уменьшенной матрице поставлен запрет в клетке (2,1), т. к. выбрано ребро(1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицуможно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий,стоит не меньше 35. Результат наших ветвлений и получения оценок показан нарис.6.

/>Кружки представляют классы: верхний кружок– класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2);нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками– оценки снизу.

/> Продолжим ветвление в положительнуюсторону: влево — вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на табл. 7. Максимальная оценка в клетке (3,1) равна3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Дляоценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] на табл. 8. В эту матрицу нужно поставитьзапрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и(3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3). Этаматрица приводится по столбцу на 1 (табл. 9), таким образом, каждый турсоответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 иболее.

3 4 5 6 2 1 3 1 4 01 - 1 3 5 02 - 6 3 2 03 - табл. 9 3 4 6 2 1 3 03 4 03 - 3 5 03 табл. 10 3 4 4 - 5 табл. 11

Оцениваемтеперь нули в приведенной матрице C[(1,2),(3,1)]нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариантимеет оценку 38+3=41. Для получения оценки положительного варианта убираемстрочку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрицанеприводима. Следовательно, оценка положительного варианта не увеличивается(рис.8).

Оцениваянули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6),отрицательный вариант получает оценку 36+3=39, а для получения оценкиположительного варианта вычеркиваем вторую строку и шестой столбец, получаяматрицу на табл. 11.

Вматрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура[3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когдаосталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и(5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1стоимостью в 36. При достижении низа по дереву перебора класс туров сузился доодного тура, а оценка снизу превратилась в точную стоимость.

Итак,все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтомусоответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомкакоторой вычеркнуты. Мы колоссально сократили полный перебор. Осталосьпроверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С сзапретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35).Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательноговарианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательныйвариант отсекается.

/> Для получения оценки положительноговарианта исключаем из матрицы первую строку и третий столбец, ставим запрет(3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1,оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все»убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мыполучили тот же минимальный тур, который показан подчеркиванием на табл. 2.

Удовлетворительныхтеоретических оценок быстродействия алгоритма Литтла и родственных алгоритмовнет, но практика показывает, что на современных ЭВМ они часто позволяют решитьЗК с n = 100. Это огромный прогресс по сравнениюс полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, еслинет возможности доводить их до конца, эффективными эвристическими процедурами.

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

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

Можнопредложить много процедур решения этой задачи, например, физическоемоделирование. На плоской доске рисуется карта местности, в города, лежащие наразвилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дорогиукладываются верёвками, которые привязываются к соответствующим кольцам. Чтобынайти кратчайшее расстояние между i и k, нужно взять I в однуруку и k в другую и растянуть. Те верёвки, которыенатянутся и не дадут разводить руки шире и образуют кратчайший путь между i и k. Однакоматематическая процедура, которая промоделирует эту физическую, выглядит оченьсложно. Известны алгоритмы попроще. Один из них – алгоритм Дейкстры,предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую задачу:

Вориентированной, неориентированной или смешанной (т. е. такой, где часть дорогимеет одностороннее движение) сети найти кратчайший путь между двумя заданнымивершинами.

Алгоритмиспользует три массива из n (= числувершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена)и 1 (вершина уже рассмотрена); второй массив b содержит расстояния – текущие кратчайшие расстояния от vi до соответствующей вершины; третий массивc содержит номера вершин – k-й элемент ck есть номерпредпоследней вершины на текущем кратчайшем пути из vi в vk. Матрица расстояний Dik задаёт длины дуг dik; если такой дуги нет, то dik присваивается большое число Б, равное «машинной бесконечности».

Теперьможно описать:

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

1(инициализация).

Вцикле от одного до n заполнить нулями массив а; заполнитьчислом i массив с: перенести i-тую строку матрицы D в массив b;

a[i]:=1; c[i]:=0; {i-номерстартовой вершины}

2(общийшаг).

Найтиминимум среди неотмеченных (т. е. тех k, длякоторых a[k]=0);пусть минимум достигается на индексе j, т. е. bj£bk; a[j]:=1;

23 12 ∞ ∞ ∞ ∞ ∞ 23 25 ∞ 22 ∞ ∞ 35 12 25 18 ∞ ∞ ∞ ∞ ∞ ∞ 18 ∞ 20 ∞ ∞ ∞ 22 ∞ ∞ 23 14 ∞ ∞ ∞ ∞ 20 23 24 ∞ ∞ ∞ ∞ ∞ 14 24 16 ∞ 35 ∞ ∞ ∞ ∞ 16 табл. 12

еслиbk>bj+djk то (bk:=bj+djk; ck:=j) {Условие означает, что путь vi..vk длиннее, чем путь  vi..vj,vk. Если все a[k] отмечены, то длина пути vi..vk равна b[k]. Теперьнадо перечислить вершины, входящие в кратчайший путь}

3(выдачаответа).

{Путьvi..vk выдаётся в обратном порядке следующей процедурой:}

3.1. z:=c[k];

3.2.Выдать z;

3.3.z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.

Длявыполнения алгоритма нужно n  разпросмотреть массив b из n элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность.Проиллюстрируем работу алгоритма Дейкстры численным примером (для большейсложности, считаем, что некоторые города (вершины)  i,j не соединены между собой, т. е. D[i,j]=∞). Пусть, например, i=3. Требуется найти кратчайшие пути из вершины 3. Содержимоемассивов a,b,c после выполнения первого пункта показано на табл. 12:

/>

1 2 3 4 5 6 7 8 a 1 b 12 25 18 ∞ ∞ ∞ ∞ c 3 3 3 3 3 3 3 табл. 13

 

/> /> /> /> /> /> /> /> /> />

Очевидно,содержимое таблицы меняется по мере выполнения общего шага. Это видно изследующей таблицы:

1 2 3 4 5 6 7 8 min bk=12 a 1 1 b 12 25 18 ∞ ∞ ∞ ∞ c 3 3 3 3 3 3 3 min bk=18 a 1 1 1 b 12 25 18 ∞ 38 ∞ ∞ c 3 3 3 3 4 3 3 min bk=25 a 1 1 1 1 b 12 25 18 47 38 ∞ 60 c 3 3 3 2 4 3 2 min bk=38 a 1 1 1 1 1 b 12 25 18 47 38 62 60 c 3 3 3 2 4 6 2 min bk=47 a 1 1 1 1 1 1 b 12 25 18 47 38 61 60 c 3 3 3 2 4 5 2 min bk=60 a 1 1 1 1 1 1 1 b 12 25 18 47 38 61 60 c 3 3 3 2 4 5 2

Такимобразом, для решения ЗК нужно n раз применитьалгоритм Дейкстры следующим образом.

Возьмёмпроизвольную пару вершин

j,k. Исключим непосредственное ребро C[j,k]. Спомощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторыйгород m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере– для j,m и m,k) удалимсоответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшеерасстояние не должен входить уже использованный город.

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

1.2.5. Мой метод (метод Анищенко) решениязадачи коммивояжера

/>

/>

Япредложу свой метод решения задачи коммивояжера.

 Рассмотримрис. 9-10 и попытаемся найти в них кратчайшие туры. Очевидно, что кратчайшийтур не должен содержать пересекающихся ребёр (в противном случае, поменяввершины при пересекающихся рёбрах местами, получим более короткий тур). Впервом случае кратчайшим является тур 1-2-4-5-3-1, а во втором – тур1-2-3-4-5-1. Анализируя множество других аналогичных расположений пяти и болеегородов, можно сделать следующее общее предположение:

1.Если можно построить выпуклый многоугольник, по периметру которого лежат всегорода, то такой выпуклый многоугольник является кратчайшим туром.

Однаконе всегда можно построить выпуклый многоугольник, по периметру которого лежалибы все города. Велика вероятность того, что некоторые города не войдут ввыпуклый многоугольник. Такие города будем называть «центральными». Так какпостроить выпуклый многоугольник довольно легко, то задача сводится к тому,чтобы включить в тур в виде выпуклого многоугольника все центральные города сминимальными потерями. Пусть имеется массив T[n+1], содержащий в себе номера городов попорядку, которые должен посетить коммивояжер, т. е. вначале коммивояжер долженпосетить город T[1], затем T[2], потом T[3] и т. д,,причём T[n+1]=T[1] (коммивояжер должен вернуться в начальный город).Тогда, если выполняется равенство «i∈[1,2..n];C[T[i],p]+C[p,T[i+1]] – C[T[I],T[i+1]]=min, тоцентральный город с номером p нужно включитьв тур между городами T[i] и T[i+1]. Проделав эту операцию для всех центральных городов, врезультате получим кратчайший тур. Данный алгоритм можно реализовать на языкеПаскаль и проверить верность предположения 1. Для задачи, решённой нами методомветвей и границ, мой алгоритм даёт правильное решение.

Попробуемрешить данным алгоритмом ЗК для восьми городов. Пусть имеем восемь городов,расположение которых показано на рис. 11. Матрица расстояний приведена рядом натабл. 13. Промежуточные построения кратчайшего тура показаны пунктирнымилиниями, цифры – порядок удаления рёбер. Таким образом, имеем для данногослучая кратчайший тур 1-3-7-5-4-8-6-2-1. Длина этого тура: D=6+7+5+2+6+5+13+13=57. Этот результат является правильным,т. к. алгоритм лексического перебора, который никогда не ошибается, даёт точнотакой же тур. (Следует также отметить, что жадный алгоритм для этого случаяошибается всего на 1 и даёт тур 1-3-4-5-7-8-6-2-1 длиной в 58).

1 2 3 4 5 6 7 8 1 13 6 13 14 15 14 16 2 13 11 11 8 13 17 14 3 6 11 5 6 11 7 11 4 13 11 5 2 6 7 6 5 14 8 6 2 6 5 6 6 15 13 11 6 6 13 5 7 14 17 7 7 5 13 9 8 16 14 11 6 6 5 9 табл. 13

/>Одним из возможных недостатков такогоалгоритма является необходимость знать не матрицу расстояний, а координатыкаждого города на плоскости. Если нам известна матрица расстояний междугородами, но неизвестны их координаты, то для их нахождения нужно будет решить n систем квадратных уравнений с n неизвестными для каждой координаты. Уже для 6 городов это сделатьочень сложно. Если же, наоборот, имеются координаты всех городов, но нетматрицы расстояний между ними, то создать эту матрицу несложно. Это можно легкосделать в уме для 5-6 городов. Для большего количества городов можновоспользоваться возможностями компьютера, в то время как промоделироватьрешение системы квадратных уравнений на компьютере довольно сложно.

Наоснове вышеизложенного можно сделать вывод, что мой алгоритм, наряду сдеревянным алгоритмом и алгоритмом Дейкстры, можно отнести к приближённым (хотяза этим алгоритмом ни разу не было замечено выдачи неправильного варианта).

1.2.6. Анализ методов решения задачикоммивояжера

Дляподведения итогов в изучении методов решения ЗК протестируем наиболееоптимальные алгоритмы на компьютере по следующим показателям: количествогородов, время обработки, вероятность неправильного ответа. Данные занесём втаблицу.

Алгоритм лексического перебора Кол-во городов Время обработки, c Вероятность неправильного ответа, % Тип алгоритма 10 41 точный 12 12000=3ч.20мин 32 -* 100 -* Метод ветвей и границ 10 ~0 точный 32 ~0.0001 100 1.2 Мой алгоритм решения ЗК 10 0.001 приближенный 32 2.5 100 6

*-ЗК с таким количеством городов методом лексического перебора современныйкомпьютер не смог бы решить даже за всё время существования Вселенной.

Каквидим по результатам этой таблицы, алгоритм лексического перебора можноприменять лишь в случае с количеством городов 5..12. Метод ветвей и границ,наряду с моим методом, можно применять всегда. Хотя мой метод я отнёс кприближённым алгоритмам, он фактически является точным, так как доказатьобратное ещё не удалось.

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

Кромеочевидного применения ЗК на практике, существует ещё ряд задач, сводимых крешению ЗК.

Задачао производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать однимпроцессором… Будем считать также, что единовременно процессор производиттолько одну краску, поэтому краски нужно производить в некотором порядкеПоскольку производство циклическое, то краски надо производить в циклическомпорядке p=(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j      надо отмыть оборудование от краски i. Для этого требуется время C[i,j].Очевидно, что C[i,j] зависит как от i, так иот j, и что, вообще говоря,C[i,j]≠C[j,i]. Принекотором выбранном порядке придется на цикл производства красок потратитьвремя.

Такимобразом, ЗК и задача о минимизации времени переналадки – это просто одназадача, только варианты ее описаны разными словами.

Задачао дыропробивном прессе. Дыропробивной пресс производит большое число одинаковыхпанелей – металлических листов, в которых последовательно по одному пробиваютсяотверстия разной формы и величины. Схематически пресс можно представить в видестола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, попериметру которого расположены дыропробивные инструменты разной формы ивеличины. Каждый инструмент присутствует в одном экземпляре. Диск можетвращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает наподвешенный под него инструмент тогда, когда под инструмент подведена нужнаяточка листа.

Операцияпробивки j-того отверстия характеризуется четверкойчисел (xj,yj,zj,tj),, гдеxj,yj-координаты нужного положения стола, zj — координата нужного положения диска и tj — время пробивки j-того отверстия.

Производствопанелей носит циклический характер: в начале и конце обработки каждого листастол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается. Это начальноесостояние системы можно считать пробивкой фиктивного нулевого отверстия. Спараметрами (x0,y0,z0,0).

Чтобыпробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:

1.Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)   

Проделатьто же самое по оси y, затратив время ti,j(y)   

Повернутьголовку по кратчайшей из двух дуг из положения zi в положение zj, затративвремя ti,j(z) .  

Пробитьj-тое отверстие, затратив время tj.

Конкретныйвид функций t(x), t(y), t(z) зависит отмеханических свойств пресса  и достаточно громоздок. Явно выписывать этифункции нет необходимости

Действия1-3 (переналадка с  i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленнопосле завершения самого длительного из этих действий. Поэтому

С[i,j] = max(t(x), t(y), t(z))

Теперь,как и в предыдущем случае, задача составления оптимальной программы длядыропробивного пресса сводится к ЗК (здесь — симметричной).

Выводы

Изученыэвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмырешения ЗК – это полный перебор или усовершенствованный перебор. Оба они,особенно первый, не эффективны при большом числе вершин графа.

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

Проведёнанализ наиболее рациональных методов решения ЗК и определены области ихэффективного действия: для малого числа вершин можно использовать точный методлексического перебора;  для большого числа вершин рациональнее применять методветвей и границ или метод автора работы (Анищенко Сергея Александровича).

Изученыпрактические применения ЗК и задачи с переналадками, сводимые к ЗК.

Приведенытексты программ, позволяющие решить ЗК различными методами.

Список литературы

О.Оре  Графы и их применение. Пер. с англ. под ред. И.М. Яглома. — М., «Мир»,1965, 174 с.

В.П. Сигорский. Математический аппарат инженера. — К., «Техніка», 1975, 768 с.

Ю.Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование:учебное пособие. 2-е изд. перераб. и доп. — М.; Высшая школа, 1980, 300 с., ил.

Е.В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторногоэксперимента. – М., Наука, 1979, 345 с.

Е.П. Липатов. Теория графов и её применения. — М., Знание, 1986, 32 с.

В.М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. –Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.

Ф.А. Новиков Дискретная математика для программистов. — Санкт-Петербург, Питер,2001, 304 с., ил.