Министерствообразования и науки РФ
Государственноеобразовательное учреждение высшего профессионального образования
АМУРСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
(ГОУВПО«АмГУ»)
Факультет математики иинформатики
Кафедра математическогоанализа и моделирования
КУРСОВАЯРАБОТА
на тему: «Задача окоммивояжере и ее обобщения»
по дисциплине«Вариационное исчисление и методы оптимизации»
СОДЕРЖАНИЕ
Введение
1 Постановказадачи
2 Эвристическиеметоды
2.1 АлгоритмБорувки
2.2 АлгоритмКрускала
2.3 АлгоритмПрима
2.4 Вывод
3 Генетическийалгоритм
4 NP-полная задача
5 Методветвей и границ
6 Практическоеприменение задачи коммивояжер
Заключение
Библиографическийсписок
ВВЕДЕНИЕ
В 1859 г. Сэр ВильямГамильтон, знаменитый математик, давший миру теорию комплексного числа икватерниона, предложил детскую головоломку, в которой предлагалось совершить«круговое путешествие» по 20 городам, расположенных в различных частях земногошара.
Гамильтонова задача опутешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер – несвободно путешествующий турист, а деловой человек, ограниченный временными,денежными или какими-либо другими ресурсами. Гамильтонова задача может статьзадачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой.Это может быть километраж, время на дорогу, стоимость билета, расход горючего ит.д. Таким образом, условные характеристики дадут числовой ряд, элементыкоторого могут быть распределены между ребрами как угодно.
Задача о коммивояжере относится к классу NP-трудных задач. Методы решениязадачи о коммивояжере различны. В данной курсовой кратко рассказывается толькоо некоторых наиболее известных.
К эвристическимметодам решения задачи коммивояжёра следует отнести «жадный» алгоритм, накаждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, ненарушающих корректности решения. Эти методы имеют большую погрешность. Хорошоисследована область генетических алгоритмов, показавших свою эффективность дляданной задачи, но они довольно громоздки. Метод перебора прост,но только лишь при небольшом количестве итераций.
И наиболееудобным мне кажется метод ветвей и границ. Его можно применять и при большомколичестве городов.
1.ПОСТАНОВКА ЗАДАЧИ
/>
Рис.1
Предположим, что бродячийторговец должен, покинув город, которому присвоим номер 1, объехать еще N–1 городов и вернутся снова в город номер 1. В его распоряжении есть дороги,соединяющие эти города. Он должен выбрать свой маршрут – порядок посещениягородов так, чтобы путь, который ему придется пройти, был как можно короче.Основное условие этой задачи состоит в том, что коммивояжер не имеет прававозвращаться снова в этот город, в котором он однажды уже побывал. Это условиебудем называть условием (α). Мы считаем, что расстояние между двумягородами – функция f(xi,xj)–определено. Разумеется, функция f(xi,xj)может означать не только расстояние, но, например, время или издержки в пути ит.д. поэтому в общем случае
f(xi,xj)≠ f(xj,xi),
а функции f(xi,xi)естественно приписать значение ∞. Длина lпути Sопределяетсяформулой
/> (1.1)
Сумма в выражении (1)распространена по всем индексам iи j, удовлетворяющим условию(α), т.е. условию, что каждый из индексов iи jвходитв выражение (1) один и только один раз. Функция l= l(x1,…, xN)является, таким образом, аддитивной – она представима в виде суммы слагаемых,однако сама задача – задача отыскания минимума l– в силу ограничения (α) не является аддитивной и не удовлетворяетпринципу оптимальности.
Рассмотрим снова плоскостьt, x,где t – дискретный аргумент,принимающий значения 0,1, 2, …, N,соответствующие этапам путешествия торговца. Значит t= 0 соответствует его начальному положению в городе номер 1, t= 1 – переходу из города номер 1 в город, который он выбрал первым дляпосещения, и т.д., t= N означает последнийэтап его путешествия – возвращение в город номер 1. Аргумент xтеперь также принимает дискретные значения 1,2, …, N(Рисунок1.1). Соединим точку (0, 1) с точками (1,1), (1, 2), …(1, N)и длинам отрезков, соединяющих эти точки, припишем значения f(x1,xj).Далее точки (1, s) – узлы,лежащие на первой вертикали, мы соединим со всеми уздами второй вертикали,длинам отрезков мы припишем значения f(xs,xk)и т.д. точки (N-1, s)соединим с точкой (N,1).
/>
В результате мы построилинекоторый граф, каждая ломанная которого, соединяющая точку (0,1) сточкой (N,1),описывает путь коммивояжера. Нашу задачу мы можем теперь сформулироватьследующим образом. Среди всех ломанных, принадлежащих этому графу и соединяющихточки (0,1) и (N,1) иудовлетворяющих условию (α), найти ломанную кратчайшей длины. Условие(α) состоит теперь в том, что искомая ломанная пересекает (в узле) каждуюиз прямых x= iодин и только один раз. Таким образом, задача о коммивояжере формулируетсяболее привычным для нас языком.
Рассмотримузел P, лежащий на третьейвертикали (Рисунок 1.2). Если бы условие (α) отсутствовало, то выбортраектории, которая соединяет точку Pс точкой (N, 1), не зависел бы от тогопути, который привел нас в точку P.В данном случае ситуация иная, и если два коммивояжера находятся в точке P,но один из них пришел в это состояние, двигаясь вдоль траектории, проходящейчерез точку Q, а второй черезточку R, то их состояния существенноотличаются друг от друга.
Коммивояжер,который двигался по второй траектории, уже побывал в городах номер 2 и номер 5и в будущем он уже не имеет права снова заезжать в эти города. Что касается коммивояжера, который двигался вдоль первой траектории, тоон побывал в городах номер 3 и номер 6; он не имеет права возвращаться в этигорода, но зато он еще обязан посетить города номер 2 и номер 5 и т. Д.
Поскольку функция f(xi, xj) определена на конечноммножестве точек, то и функция l(х1,…,xN) также определена на конечноммножестве точек.
Следовательно, задача определения минимума функции l сводится к переборунекоторого конечного множества значений этой функции, и проблема носит чистовычислительный характер. Однако именно вычислительные трудности здесь огромны.
Легко подсчитать, что число возможных вариантов (число значенийфункции l) равно (N— 1)!. Таким образом,непосредственно перебрать и сравнить между собой все возможные пути, по которымможет следовать бродячий торговец, для достаточно большого количества городовпрактически невозможно.
Возникает проблема построения такого метода последовательногоанализа вариантов, который выделял бы по возможности большое количествонеперспективных вариантов и сводил задачу к перебору относительно небольшогоколичества «подозрительных» вариантов.
2.ЭВРИСТИЧЕСКИЕ МЕТОДЫ
Решить задачукоммивояжера можно с помощью алгоритма Крускала. Также нам могут помочьалгоритмы Борувки и Прима, так называемые «жадные алгоритмы» Эти методыускоряют разработку алгоритма по сравнению с методом полного перебора, однаконе всегда дают оптимальное решение. Но немного расскажем о них.
Итак,имеется n городов, которые нужно обойти. Для этого достаточнопроложить (n-1) путей между городами. Как соединить города так,чтобы суммарная стоимость путешествия была минимальна?
Вобщем случае, задачу можно сформулировать так. Пусть дан связный,неориентированный граф с весами на ребрах G(V, E),в котором V — множество вершин (городов), а E — множествоих возможных попарных соединений (дороги). Пусть для каждого ребра (u,v)однозначно определено некоторое вещественное число w(u,v)— его вес (длина или стоимость пути). W(u,v) называетсявесовой функцией. Задачасостоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес егоребер будет минимален.
Таккак T связен и не содержит циклов, он является деревом и называется остовнымили покрывающим деревом. Остовное дерево T,у которого суммарный вес его ребер w(T) = ∑(u,v)∈T w(u,v)минимален, называется минимальнымостовным или минимальнымпокрывающим деревом.
Так какрассматриваются только деревья, можно считать все ребра положительными(достаточно добавить к весу всех ребер некоторую относительно большуюположительную константу). В противном случае, если стоимость соединения междудвумя вершинами равна отрицательному числу, можно несколько раз параллельносоединить их для уменьшения суммарного веса остовного подграфа.
Такжесчитаем, что для любой пары ребер их весовые характеристики будут различны. Этогарантирует уникальность построенного минимального остовного дерева. Дляпримера, если все ребра имеют единичный вес, то любое остовное дерево будетминимальным (с суммарным весом v-1, где v – количествовершин в графе).
Искомыйостов строится постепенно. Алгоритм использует некоторый ациклический подграф Аисходного графа G, который называется промежуточным остовным лесом. Изначально Gсостоит из n вершин-компонент, не соединенных друг с другом (nдеревьев из одной вершины). На каждом шаге в A добавляется одноновое ребро. Граф A всегда является подграфом некоторогоминимального остова. Очередное добавляемое ребро e=(u,v)выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должнобыть подграфом минимального. Такое ребро называется безопасным.
Поопределению A, он должен оставаться подграфом некоторогоминимального остова после любого числа итераций. Конечно, главный вопроссостоит в том, как искать безопасное ребро. Понятно, что такое ребро всегдасуществует, если A еще не является минимальным остовом (любое реброостова, не входящее в A). Заметим, что так как A не можетсодержать циклов, то на каждом шаге ребром соединяются различные компонентысвязности (изначально все вершины в отдельных компонентах, в конце A– одна компонента). Таким образом анализ графа выполняется (n-1)раз.
Далееприводится общее правило отыскания безопасных ребер. Для этого есть теорема,которая поможет находить безопасные ребра.
Теорема: Пусть G(V;E) –связный неориентированный граф и на множестве Е определена весоваяфункция w. Пусть А – некоторый подграфG, являющийся в тоже время подграфом некоторого минимального остовного дерева T.Рассмотрим компоненту связности К изА. Рассмотрим множество E(K)ребер графа G, только один конец которых лежит в К. Тогда реброминимального веса из E(K) будет безопасным.
Всвязи с приведенной теоремой введем следующее: безопасным ребром e относительно некоторойкомпоненты связности К из А назовем ребро с минимальным весом,ровно один конец которого лежит в К.
2.1 АЛГОРИТМ БОРУВКИ
Напервом шаге A состоит из всех вершин G и пустого множестваребер. В начале очередной фазы алгоритма Борувки, для каждой компонентысвязности промежуточного остовного леса выбирается лидер или корень– вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшемслучае с помощью обхода A в глубину: вершина, с которой начинаетсяобход очередной компоненты, и будет ее лидером.
После того,как лидеры выбраны, для каждой компоненты связности находится безопасное длянее ребро, по существу методом грубой силы. Как только все такие ребраотобраны, они добавляются к A. Процесс продолжается до тех пор, покав A присутствует больше одной компоненты связности.
2.2 АЛГОРИТМ КРУСКАЛА
АлгоритмКрускала объединяет вершины графа в несколько связных компонент, каждая изкоторых является деревом. На каждом шаге из всех ребер, соединяющих вершины изразличных компонент связности, выбирается ребро с наименьшим весом. Необходимопроверить, что оно является безопасным. Безопасность ребра гарантируется ранеепоказанной теоремой о безопасных ребрах. Так как ребро является самым легким извсех ребер, выходящих из данной компоненты, оно будет безопасным.
Остаетсяпонять, как реализовать выбор безопасного ребра на каждом шаге. Для этого валгоритме Крускала все ребра графа G перебираются по возрастанию веса. Дляочередного ребра проверяется, не лежат ли концы ребра в разных компонентахсвязности, и если это так, ребро добавляется, и компоненты объединяются.
Удобноиспользовать для хранения компонент структуры данных для непересекающихсямножеств, как, например, списки или, что лучше, лес непересекающихся множествсо сжатием путей и объединением по рангу (один из самых быстрых известныхметодов). Элементами множеств являются вершины графа, каждое множество содержитвершины одной связной компоненты.2.3 АЛГОРИТМ ПРИМА
Каки алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построенияминимального остовного дерева: на каждом шаге мы добавляем к строящемуся остовубезопасное ребро. Алгоритм Прима относится к группе алгоритмов наращиванияминимального остова: на каждом шаге существует не более одной нетривиальной (несостоящей из одной вершины) компоненты связности, и каждый к ней добавляетсяребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами.По теореме такое ребро является безопасным.
Приреализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Дляэтого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получаетна вход граф G и его корень r – вершина, на которой будетнаращиваться минимальный остов. Все вершины G, еще не попавшие вдерево, хранятся в очереди с приоритетом Ω. Приоритет вершины vопределяется значением key[v],которое равно минимальному весу ребер, соединяющих v с вершинамиминимального остова. Поле p[v]для вершин дерева указывает на родителя, а для вершин из очереди, указывает наостов дерева, в которою ведет ребро с весом key[v](одно из таких ребер, если их несколько).
2.4 ВЫВОД
Взавершение рассказа о жадных алгоритмах приведу пример. Рассмотрим небольшую «детскую»задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуемэту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты поодной копейке. Нам не только удалось быстро определить перечень монет нуясногодостоинства, но и, по сути, мы составили самый короткий список монет требуемогодостоинства.
Алгоритм,которым мы в этом случае воспользовались, заключался в выборе монеты самогобольшого достоинства (25 копеек), но не больще 63 копеек, добавлению ее всписок сдачи и вычитанию ее стоимости из 63 (получается 38 копеек). Затем сновавыбираем монету самого больщого достоинства, но не больще остатка (38 копеек):этой монетой опять оказывается монета в 25 копеек. Эту монету мы опятьдобавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.
Этот методвнесения изменений называется «жадным» алгоритмом. На каждой отдельной стадии«жадный» алгоритм выбирает тот вариант, который является локально оптимальным втом или ином смысле. Обратите внимание, что алгоритм для определения сдачиобеспечивает в целом оптимальное рещение лищь вследствие особых свойств монет.Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и нужно было быдать сдачу 15 копеек, то «жадный» алгоритм выбрал бы сначала монетудостоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пятьмонет. Однако в данном случае можно было бы обойтись тремя монетами по 5копеек.
И всеприведенные выше алгоритмы являются «жадными».
Следуетподчеркнуть, что не каждый «жадный» алгоритм позволяет получить оптимальныйрезультат в целом. Как нередко бывает в жизни, «жадная стратегия» подчасобеспечивает лишь сиюминутную выгоду, в то время как в целом результат можетоказаться неблагоприятным.
Существуютзадачи, для которых ни один из известных «жадных» алгоритмов не позволяетполучить оптимального решения; тем не менее имеются «жадные» алгоритмы, которыес большой вероятностью позволяют получать «хорошие» решения. Нередко вполнеудовлетворительным можно считать «почти оптимальное» решение.
3.ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
Генетический алгоритм —это алгоритм, который позволяет найти удовлетворительное решение к аналитическинеразрешимым проблемам через последовательный подбор и комбинирование искомыхпараметров с использованием механизмов, напоминающих биологическую эволюцию.Является разновидностью эволюционных вычислений. Отличительной особенностьюгенетического алгоритма является акцент на использование оператора«кроссовера», который производит операцию, роль которой аналогична ролискрещивания в живой природе. «Отцом-основателем» генетических алгоритмовсчитается Джон Холланд, книга которого «Адаптация в естественных иискусственных системах» является основополагающим трудом в этой областиисследований.
Задача кодируется такимобразом, чтобы её решение могло быть представлено в виде вектора («хромосома»).Случайным образом создаётся некоторое количество начальных векторов («начальнаяпопуляция»). Они оцениваются с использованием «функции приспособленности», врезультате чего каждому вектору присваивается определённое значение(«приспособленность»), которое определяет вероятность выживания организма,представленного данным вектором. После этого с использованием полученныхзначений приспособленности выбираются вектора (селекция), допущенные к«скрещиванию». К этим векторам применяются «генетические операторы» (вбольшинстве случаев «скрещивание» — crossover и «мутация» — mutation), создаваятаким образом следующее «поколение». Особи следующего поколения такжеоцениваются, затем производится селекция, применяются генетические операторы ит. Д. Так моделируется «эволюционный процесс», продолжающийся несколькожизненных циклов (поколений), пока не будет выполнен критерий остановаалгоритма. Таким критерием может быть: нахождение глобального, либо субоптимальногорешения; исчерпание числа поколений, отпущенных на эволюцию; исчерпаниевремени, отпущенного на эволюцию. Генетические алгоритмы служат, главнымобразом, для поиска решений в очень больших, сложных пространствах поиска.
Таким образом, можновыделить следующие этапы генетического алгоритма:
создание начальнойпопуляции;
вычисление функцийполезности для особей популяции (оценивание);
выбор индивидов изтекущей популяции (селекция);
скрещивание и\илимутация;
вычисление функцийполезности для всех особей;
формирование новогопоколения;
если условия совпали,то решение найдено (конец цикла), если нет, то цикл повторяется.
Применяютсягенетические алгоритмы для решения следующих задач:
оптимизация функций,разнообразные задачи на графах (задача коммивояжера, раскраска, нахождениепаросочетаний), настройка и обучение искусственной нейронной сети, задачикомпоновки, составление расписаний, игровые стратегии, аппроксимация функций, искусственнаяжизнь, биоинформатика (свёртывание белков).
4. NP-ПОЛНАЯ ЗАДАЧА
Всеэффективные (сокращающие полный перебор) методы решения задачи коммивояжёра —методы эвристические («жадные алгоритмы»). В большинстве эвристических методовнаходится не самый эффективный маршрут, а приближённое решение. Зачастуювостребованы так называемые any-time алгоритмы, то есть постепенно улучшающиенекоторое текущее приближенное решение.
Задачакоммивояжёра есть NP-полная задача. Часто на ней проводят обкатку новыхподходов к эвристическому сокращению полного перебора.
Втеории алгоритмов NP-полные задачи — это класс задач, лежащих в классе NP (тоесть для которых пока не найдено быстрых алгоритмов решения, но проверка того,является ли данное решение правильным, проходит быстро), к которым сводятся всезадачи класса NP.
Назовёмязыком множество слов над алфавитом Σ. Задачей здесь является определениетого, принадлежит данное слово языку или нет. Язык L1 называетсясводимым (по Карпу) к языку L2, если существует функция, вычислимаяза полиномиальное время, обладающая следующим свойством: f(x)принадлежит L2 тогда и только тогда, когда x принадлежит L1.Язык L2 называется NP-трудным, если любой язык из класса NP сводитсяк нему. Язык называют NP-полным, если он NP-труден и при этом сам лежит вклассе NP. Таким образом, если будет найден алгоритм, решающий хоть однуNP-полную задачу за полиномиальное время, все NP-задачи будут лежать в классеP.
Равенствоклассов P и NP уже более 30 лет является открытой проблемой. Научное сообществосклоняется к отрицательному решению этого вопроса — в этом случае заполиномиальное время решать NP-полные задачи не удастся.
5. МЕТОД ВЕТВЕЙ И ГРАНИЦ
/>
Существуетметод решения задачи коммивояжера, который дает оптимальное решение. Этот методназывается методом ветвей и границ.
Основаэтого, ныне широко распространенного метода состоит в построении нижних оценокрешения, которые затем используются для отбраковки неконкурентоспособныхвариантов.
Функция f(xi, xj) принимает конечное числозначений сij, которые мы можем представитьв виде таблицы (Рисунок 5.1).Предположим, что мы выбрали некоторый путь Ss. Его длина будет равна
/> (5.1)
причем сумма (5.1) распространена по i, jтак, что каждый из индексов встречается в ней один и только одинраз. Величины сijс двумя одинаковыми индексамимы приняли равными ∞.
Так как в каждый из вариантов s входит только один элемент из каждойстроки и столбца, то мы можем проделать следующую операцию, которая здесьназывается приведением матрицы. Обозначим через hiнаименьший элемент из строки номера iи построим новую матрицу С(1)сэлементами
/>
Матрица С(1) определяет новую задачукоммивояжера, которая, однако, в качестве оптимальной будет иметь ту жепоследовательность городов. Между величинами lsи ls(1)будет существовать, очевидно, следующая связь:
/>
Заметим, что в каждой из строк матрицы С(1)будет теперь, по крайней мере, один нулевой элемент. Далее обозначим через gjнаименьший элемент матрицы С(1), лежащий встолбце номераj, и построим новую матрицу С(2) сэлементами
/>
Величины hiи gjназываются константами приведения. Оптимальная последовательность городовдля задачи коммивояжера с матрицей С(2) будет, очевидно,такой же, как и для исходной задачи, а длины пути для варианта номера sв обоих задачах будут связаны между собой равенством
/> (5.2)
где
/> (5. 3)
т. Е. dравна сумме констант приведения.
Обозначим через l* решение задачи коммивояжера, т.е.
/>
где минимумберется по всем вариантам s, удовлетворяющим условию (α) Тогда величина dбудет простейшей нижнейоценкой решения:
/> (5.4)
Будем рассматривать теперь задачу коммивояжера с матрицей С(2)которую мы будем называть приведенной матрицей.
Рассмотрим путь, содержащий непосредственный переход из городаномера iв город номера j, тогда для путиs, содержащего этот переход,мы будем иметь, очевидно, следующую нижнюю оценку:
/>
Следовательно, для тех переходов, для которых /> = 0, мы будем иметь снова оценку (5.4). Естественно ожидать, чтократчайший путь содержит один из таких переходов — примем это соображение вкачестве рабочей гипотезы. Рассмотрим один из переходов, для которого /> =0, и обозначим через /> множество всех тех путей, которые не содержат перехода из iв j.
Так как из города iмы должны куда-то выйти, томножество /> содержит один из переходов i→k, где k≠ j; так как в город номера j мы должны прийти, томножество /> содержит переход m→j, где т ≠ i.
Следовательно, некоторый путь lsиз множества (ij), содержащий переходы i→kи m→j, будет иметь следующуюнижнюю оценку:
/>
Обозначим через
/>
Тогда очевидно, что длялюбого lsиз множества путей /> мы будем иметь оценку
/> (5.5)
Мы предполагаем исключить некоторое множество вариантов />,поэтому мы заинтересованы выбрать такой переход i→ j, для которого оценка (5.5) была бы самой высокой. Другимисловами, среди нулевых элементов матрицы С(2)выберемтот, для которого />максимально.Это число обозначим через /> Такимобразом, все множество возможных вариантов мы разбили на два множества I1 и I2. Для путей из множества I1, мы имеем оценку (5.4). Дляпутей из множества I2 оценка будет следующей:
/> (5.6)
Рассмотрим теперь множество I1и матрицу С(2).Так как все пути, принадлежащие этому множеству, содержат переход i→ j, то для егоисследования нам достаточно рассмотреть задачу коммивояжера, вкоторой города номеров iи jсовпадают. Размерность этойзадачи будет уже равна N– 1, а ее матрица получится из матрицы С(2)вычеркиваниемстолбца номера j и строки но мера i.
Поскольку i→ j невозможен, то элемент /> принимаем равным бесконечности.
/>
Рассмотрим случай N=3 (Рисунок 5.2, а), ипредположим, что мы рассматриваем тот вариант, который содержит переход 3 →2. Тогда задача коммивояжера после вычеркивания третьей строки и второгостолбца вырождается в тривиальную. Ее матрица изображена на рисунке 5.2, в. Вэтом случае мы имеем единственный путь, и его длина будет, очевидно, равнасумме
/>
Итак, если в результате вычеркивания строки номера iи столбца номера jмы получим матрицу второгопорядка, то задачу можно считать решенной.
Пусть теперь N>3. После вычеркивания мы получим матрицу порядок
N -1 > 2.
С этой матрицей (N— 1)-гопорядка совершим процеурруприведения. Матрицу, которую таким образом получим, обозначим через С(3),а через d(1) – сумму ее константприведения. Тогда для ls/> I1, мы будем иметь оценку
/> (5.7)
На этомпервый шаг алгоритма закончен. В результате одного шага мы разбили множествовсех возможных вариантов на два множества I1 и I2 и для путей, принадлежащих этиммножествам, мы получили оценки (5.7) и (5.6) (Рисунок 5.3)
/>
Рис.5.3
Введем понятие стандартной операции, которую мы будем обозначатьсимволом /> Этимтермином мы назовем процедуру разбиения произвольного множества вариантов Ωс приведенной матрицей N – п-гопорядка С(n+ 2) и оценкой dωна два множества. Одно изэтих множеств состоит из всех тех путей, которые содержат переход из городаномер s в город номер l и имеют нижнюю оценку d. Другое множество состоит из всех путей, не содержащих этогоперехода и имеющих в качестве нижней оценки число dk. Стандартную операцию можно представить в форме следующейблок-схемы (см. Рисунок 5.4).
задача коммивояжер решение алгоритм обобщение
/>
Рисунок5.4
Итак,первый шаг метода ветвей и границ состоит в проведении стандартной операции надисходным множеством Ω. На следующем шаге мы продолжаем развивать деревовозможных вариантов. Сначала мы сравниваем две оценки d1 и d2 и для последующего анализавыбираем то из множеств I1 или I2, для которого соответствующая оценка меньше.
Предположим, что
d1d2;
тогда над множеством I1 с матрицей С(3)мы совершим стандартную операцию. В результате мы разобьем множество возможныхвариантов I1на два подмножества II11 и II12, первое из которых содержит некоторый переход i1→ j1а другое содержит все пути,не имеющие непосредственною перехода из города i1в город j1. Еще раз повторим рассмотреннуювыше процедуру: для каждого из нулевых элементов матрицы С(3)построим число
/>
Определимзначение
/>
и элемент матрицы С(3),для которого достигается это значение. Если ls/> II12, то
/> (5.8)
Затем в матрице С(3) вычеркиваем строку номера i1и столбец номера j1, полагаем /> инад полученной матрицей совершаем операцию приведения. В результате мы найдемновые константы приведения. Их сумму обозначим через d(II)и в заключение находимоценку d11для элементов множества II11.
Если ls /> II11, то
/> (5.9)
На этом второй шаг алгоритма ветвей и границ закончен. Мы разбилимножество вариантов I1 на два множества, II11 и II12, и для элементов этихмножеств получили нижние оценки (5.9) и (5.8), соответственно.
Теперь мы должны сравнить оценку (5.9) с оценкой (5.6) дляэлементов множества I2, которое мы исключили израссмотрения на предыдущем шаге. Если окажется, что d2> d11,
то мы переходим к третьему шагу, который состоит в применениистандартной операции к множествуII11. (Если размерность матрицыпри этом равна двум, то, как мы видели выше, процесс заканчивается.)
Если окажется, что d11> d2, то множеством вариантов соптимальной нижней оценкой будет множество I2. Другими словами, теперь будем предполагать, что наиболеекороткий путь содержится среди элементов множества I2 — множества всех вариантов, не содержащих перехода i→ j. Следовательно, матрица,характеризующая это множество, получается из матрицы С(2)заменой величины /> на ∞.Над этим множеством мы производим стандартную операцию и разбиваем его на двамножества II21 и II22 с оценками d21и d22, соответственно. Одновременно мы выделяем переход k→l, который содержит все варианты множества II21. Затем мы снова сравниваем все оценки d11, d12, d21и d22 и выбираем то из множеств, для которого оценка будет наименьшей.Над выбранным множеством совершаем стандартную операцию и т. Д. Так мыпродолжаем до тех пор, пока очередная матрица не будет иметь порядок (2x2). Вэтом случае, как мы видели, расчет заканчивается — мы получаем задачукоммивояжера для двух городов (Рисунок 5.5), и длина единственного маршрутабудет />
Итак, мы получили некоторую цепочку (ветвь) переходов, длинукоторой мы вычислили. Сам порядок построения этой цепочки показывает, что еедлина — наименьшая среди всех ветвей дерева, изображенного на рисунке 5.3.
/>
Рисунок5.5
6.ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА
Задачакоммивояжера имеет ряд практических применений. Как следует из самого названиязадачи, ее можно использовать для составления маршрута человека, который долженпосетить ряд пунктов и, в конце концов, вернуться в исходный пункт. Например,задача коммивояжера использовалась для составления маршрутов лиц, занимающихсявыемкой монет из таксофонов. В этом случае вершинами являются места установкитаксофонов и «базовый пункт». Стоимостью каждого ребра (отрезкамаршрута) является время в пути между двумя точками (вершинами) на маршруте.
Задачао производстве красок. Имеется производственная линия для производстваnкрасок разного цвета; обозначим эти краски номерами 1,2… n. Всюпроизводственную линию будем считать одним процессором… Будем считать также,что единовременно процессор производит только одну краску, поэтому краски нужнопроизводить в некотором порядке. Поскольку производство циклическое, то краскинадо производить в циклическом порядке (j1,j2,..,jn,j1).После окончания производства краски i и перед началом производствакраски j надо отмыть оборудование от краски i. Для этого требуетсявремя C[i,j]. Очевидно, что C[i,j] зависит как отi, так и от j, и что, вообще говоря,C[i,j] ≠ C[j,i].При некотором выбранном порядке придется на цикл производства красок потратитьвремя, гдеtk — чистое время производства k-ой краски(не считая переналадок). Однако вторая сумма в правой части постоянна, поэтомуполное время на цикл производства минимизируется вместе с общим временем на переналадку.
Такимобразом, задачи коммивояжера и задача о минимизации времени переналадки – это простоодна задача, только варианты ее описаны разными словами.
Задачао дыропробивном прессе. Дыропробивной пресс производит большое число одинаковыхпанелей – металлических листов, в которых последовательно по одному пробиваютсяотверстия разной формы и величины. Схематически пресс можно представить в видестола, двигающегося независимо по координатам 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);
2.Проделать то же самое по оси y, затратив время ti,j(y);
3.Повернуть головку по кратчайшей из двух дуг из положения zi вположение zj, затратив время ti,j(z);
4.Пробить j-тое отверстие, затратив времяtj.
Конкретныйвид функций t(x), t(y), t(z) зависит от механических свойств пресса идостаточно громоздок. Явно выписывать эти функции нет необходимости. Действия1-3 (переналадка сi-того отверстия j-тое) происходит одновременно,и пробивка происходит немедленно после завершения самого длительного из этихдействий. Поэтому С[i,j] = max(t(x), t(y), t(z)). Теперь,как и в предыдущем случае, задача составления оптимальной программы длядыропробивного пресса сводится к задачи коммивояжера (здесь — симметричной).
Еще одним применениемзадачи коммивояжера является задача обхода доски шахматным конем: надо найтипоследовательность ходов, которые позволят коню обойти все поля шахматнойдоски, попадая на каждое поле лишь один раз, и вернуться, в конце концов, наисходное поле. В этом случае роль вершин графа выполняют поля шахматной доски.Предполагается также, что ребра между двумя полями, которые являются«составными частями» хода коня, имеют нулевой вес; все остальныеребра имеют вес, равный бесконечности. Оптимальный маршрут имеет нулевой вес идолжен быть маршрутом коня. Читатель, возможно, удивится, узнав, что поискмаршрутов коня с помощью хороших эвристических алгоритмов для задачикоммивояжера вообще не составляет проблемы, в то время как поиск«вручную» является весьма непростой задачей.
ЗАКЛЮЧЕНИЕ
Задача коммивояжераявляется частичным случаем гамильтоновой задачи о путешественнике. Суть задачикоммивояжера состоит в нахождении суммарной минимальной характеристики(расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все nгородов по одному разу, вернувшись в тот город, с которого начал.
Существуют несколькометодов решения задачи коммивояжера: метод полного перебора, «жадные» методы(Крускала, Прима, и т.п.), генетические алгоритмы и еще множество их обобщений.Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение.
В основе метода ветвейи границ лежит следующая идея если нижняя граница для подобласти Aдерева поиска больше, чем верхняя граница какой-либо ранее просмотреннойподобласти B, то A может быть исключена из дальнейшегорассмотрения (правило отсева).
Задача о коммивояжереимеет множество обобщений и методы её решения в различных проявленияхиспользуются на практике.
БИБЛИОГРАФИЧЕСКИЙСПИСОК
1 МоисеевН.Н. Методы оптимизации: Моисеев Н.Н., Иванилова Ю.П., Столярова Е.М.-М., 1978,352 с;
2 ЧерноуськоФ.Л. Вариационные задачи механики и управления: Численные методы/ ЧерноуськоФ.Л., Баничук Н.В.-М.,1973;
3 http://dic.academic.ru/;
4 http://www.lobanov-logist.ru/index.php?newsid=470;
5 http://swsys.ru/index.php?page=article&id=827;
6 http://e-maxx.ru/algo/mst_prim;
7 http://www.dissercat.com/content/nekotorye-zadachi-marshrutizatsii-i-raspredeleniya-zadanii-metod-dinamicheskogo-programmirov;
8 www.vecon.ru.