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

Содержание

Введение

1. Задача коммивояжера

1.1. Общее описание

1.2. Методы решения задачикоммивояжера

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

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

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

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

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

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

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

Выводы

Литература

Приложения

Введение

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

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

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

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

<img src="/cache/referats/7132/image002.jpg" align=«left» hspace=«12» v:shapes="_x0000_s1026"> Классические комбинаторныезадачи – это задачи выбора и расположения элементов конечногомножества, имеющие в качестве исходной некоторую формулировку развлекательногосодержания типа головоломок.

В 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. Жадный алгоритм

<img src="/cache/referats/7132/image006.jpg" align=«left» hspace=«12» v:shapes="_x0000_s1029"> Жадный алгоритм – алгоритмнахождения наикратчайшего расстояния путём выбора самого короткого, ещё невыбранного ребра, при условии, что оно не образует цикла с уже выбраннымирёбрами. «Жадным» этот алгоритм назван потому, что на последних шагахприходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя прирешении ЗК жадный алгоритм. Здесь он превратится в стратегию «иди в ближайший(в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этойзадаче. Рассмотрим для примера сеть на рис. 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]

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

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

1.

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

2.

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

3.

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

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

табл. 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-forceenumeration» — «перебор животной силой», как его называют в англоязычной литературе. Понятно, что полный переборпрактически применим только в задачах малого размера. Напомним, что ЗК с nгородами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показанов следующей таблице, растет удручающе быстро:

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. Метод ветвей и границ

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

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

табл. 4

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

табл. 2

табл. 3

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

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

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

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

еще рефераты

Еще работы по математике

Реферат по математике

Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета

20 Июня 2015

Реферат по математике

Теорема Безу

3 Августа 2015

Реферат по математике

Разбиения выпуклого многоугольника

20 Июня 2015

Реферат по математике

Построение решения задачи Гурса для телеграфного уравнения методом Римана

20 Июня 2015