Задача коммивояжёра

Содержание

Введение………………………………………………………….…..…….3

Задача коммивояжёра………………………….……………………………5

Алгоритм локального поиска………………….…………………………..8

Интерфейс программы….……………… …………………………………14

Реализации метода локального поиска на ЭВМ……...………….………16

Заключение………………………..……..…………………………………19

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

 

 

Введение

Первоначально задача коммивояжера возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де–Мере1, которая была решена Паскалем2 и послужила толчком для возникновения одного из основных понятий теории вероятностей - понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бореля3 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных

Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным. Простота постановки задачи о коммивояжере сочетается с чрезвычайной трудностью ее решения, причем трудности не принципиального, а вычислительного характера, так как легко указать прием, прямо ведущий к цели: перебрать все маршруты и взять из них наименьший. Принципиально это возможно, поскольку общее число мыслимых маршрутов является конечным числом. Но все дело в том, что ни одна, даже самая быстродействующая вычислительная машина не в состоянии осуществить этот перебор при сколько-нибудь значительном числе городов.  Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут оказался чрезвычайно трудным. 

О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки. 

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

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

 

 

 

 

 

 

 

 

Задача коммивояжёра

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

Задача коммивояжера может быть сформулирована как задача на графе в следующей постановке: построить граф G(Х, А), вершины которого соответствуют городам в зоне коммивояжера, а дуги отображают коммуникации, соединяющие пары городов. Пусть длина а(х, у)≥0 каждой дуги (х, у) ε А равна расстоянию, стоимости или времени. Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Контур, включающий каждую вершину графа G ровно один раз, называется гамильтоновым контуром (по имени ирландского математика Вильяма Роуана Гамильтона, который в 1859 г. первым начал изучение этих задач).

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

Оптимальный маршрут коммивояжера не обязательно является гамильтоновым контуром. 
ТЕОРЕМА. Если для каждой пары вершин (х, у) графа G выполняется условие а (х, у) ≤а (х, z) + а (z, у) для всех z ≠ х, z ≠ у, то гамильтонов контур является решением общей задачи коммивояжера на графе G (если решение вообще существует).

Условие говорит только о том, что расстояние непосредственно от х до у никогда не превышает расстояния от х до у через любую другую вершину z. Условие называется неравенством треугольника.

ДОКАЗАТЕЛЬСТВО. Предположим, что не существует оптимального решения общей задачи коммивояжера, представляющего собой гамильтонов контур. Пусть С - любой оптимальный маршрут коммивояжера. Так как С не является гамильтоновым контуром, то некоторая вершина, скажем вершина z, повторяется в маршруте С по крайней мере дважды. Предположим, что первый раз коммивояжер в вершину z пришел из вершины х и вышел из нее в направлении вершины у. Изменим маршрут С таким образом, чтобы коммивояжер из вершины х, минуя z, направился прямо к вершине у. Полученный в результате маршрут С' также является маршрутом коммивояжера, поскольку в нем каждая вершина посещается по крайней мере один раз. Кроме того, в соответствии с условием, общая длина С' не превышает длины С. Заменяя С на С' и повторяя эту процедуру, мы получим другой маршрут C'' и т. д. В конце концов этот процесс приведет нас к оптимальному маршруту, являющемуся гамильтоновым контуром, так как каждый последующий маршрут имеет число дуг на единицу меньшее, чем его предшественник. Теорема доказана.

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

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

а' (х, y)= М-а (х, у)≥0 для всех дуг (х, у)                                               (1)

Каждый гамильтонов контур на графе G = (Х, А) содержит ровно |Х| дуг. Оптимальный (в смысле наименьшей длины) гамильтонов контур С включает дуги, преобразованные в соответствии с соотношением (1), и его общая длина равна

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

 

Алгоритм локального поиска

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

1. Начните с произвольного решения.
2. Для улучшения текущего решения примените к нему какое-либо преобразование из некоторой заданной совокупности преобразований. Это улучшенное решение становится новым «текущим» решением.
3. Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной их совокупности не позволит улучшить текущее решение.

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

Этот метод имеет смысл лишь в том случае, когда мы может ограничить нашу совокупность преобразований небольшим её подмножеством, что даёт возможность выполнить все преобразования за относительно короткое время: если «размер» задачи равняется n, то мы можем допустить O(n2) или O(n3) преобразований. Если совокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое, за один шаг, как « близкие». Такие преобразования называются «локальными». А соответствующий метод называется локальным поиском.    

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

Рассмотрим, например, граф на рис. 10.16.

 

Мы можем начать с дерева, показанного на рис.а. Одно из преобразований, которые можно было бы выполнить, заключается в добавлении ребра (d,e) и устранении из образовавшегося цикла (e,a,c,d,e) какого-либо другого ребра. Если мы удалим ребро (а,е), то уменьшим стоимость дерева с 20 до 19. Это преобразование можно выполнить, получив в результате дерево  (рис. б), к которому мы опять попытаемся применить улучшающее преобразование. Одно из таких преобразований сводится к вставке ребра (a,d) и удалению из образовавшегося цикла ребра (c,d). Результат этого преобразования показан на рисунке в. Затем можно вставить ребро (a,b) и убрать ребро (b,c), как показано на рис. г, а потом – вставить ребро (b,e) вместо ребра (d,e). Результирующее дерево (рис. д) является минимальным. Мы можем убедиться в том, что каждое ребро, не входящее в состав этого дерева, имеет наивысшую стоимость среди всех ребёр в цикле, который они с этим ребром составляют. Таким образом, к дереву на рис. г преобразования уже не применимы.         

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

Алгоритмы локального поиска проявляют себя с наилучшей стороны как эвристические алгоритмы для решения задач, точные решения которых требуют экспоненциальных затрат времени. Общепринятый метод поиска состоит в следующем. Начать следует с рядя произвольных решений, применяя к каждому из них локальные преобразования до тех пор, пока не будет получено локально-оптимальнае решение, т.е. такое, которое не сможет улучшить ни одно преобразование. Как показано на рис. 10,19, на основе большинства (или даже всех) произвольных начальных решений мы нередко будем получать разные локально-оптимальные решения. Если нам повезет, одно на них окажется глабально-оптимальным, т.е. лучше любого другого решения.

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

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

Методы локального поиска особенно хорошо подходят для решения задачи коммивояжера. Простейшим преобразованием, которым можно в этом случае воспользоваться, является так называемый "двойной выбор". Он заключается в том, что мы выбираем любые два ребра, например ребра (А,B) и (C,D) показанные на рис. 10.20, удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. На рис. 10.20 этот новый маршрут начинается в точке В, продолжается по часовой стрелке до С, проходит по ребру (С,А), затем против часовой стрелки от А к D и наконец по ребру (D,В). Если сумма длин (А,С) и (В,D) оказывается меньше суммы длин (А,В) и (С,D), значит, нам удалось получить улучшенный маршрут. Обратите внимание, что мы не можем соединить точки А и D, В и С, поскольку полученный результат будет являться не маршрутом, а двумя изолированными друг от друга циклами.

 

 

 

 

 

Чтобы найти локально-оптимальный маршрут, мы начинаем с какого-либо произвольного маршрута и рассматриваем все пары несмежных ребер, такие как (А,В)  И (C,D) на рис 10.20. Если данный маршрут можно улучшить путём замены этих рёбер на (А,С) и (В,D), это нужно сделать, а затем продолжить рассмотрение оставшихся пар рёбер.

Вернёмся на рис 10.16 и допустим, что в качестве исходного выбран маршрут, показанный на рис 10.21,а. ребра (а,е) и (с,d) общей стоимостью 12 можно заменить ребрами (a,d) и (c,e) общей стоимостью 10, как показано на рис 10.21,б. Затем ребра  (a,b) и (c,e) можно заменить на ребра (a,c) и (b,e), что обеспечило бы нам оптимальный маршрут, показанный на рис 10.21,в. Легко убедиться, что на этом рисунке нельзя удалить ни одну пару ребер, выгодно заменив её пересекающимися ребрами с теми же конечными точками. Возьмём хотя бы один пример: ребра (b,c) и (d,e) вместе имеют относительно высокую стоимость-10. Но  (c,e) и (b,d) ещё хуже, поскольку их совместная стоимость равна 14.