694

Решение задачи коммивояжера

Курсовая

Информатика, кибернетика и программирование

Описание реализация метода ветвей и границ и метода Монте-Карло при помощи средств объектно-ориентированного языка Java. Задача поиска кратчайшего гамильтонова цикла в полном графе. Процесс разбиения множеств на подмножества.

Русский

2013-01-06

163.5 KB

349 чел.

Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра прикладной математики

Научный руководитель,

С. А . Жуков

__________________________

КУРСОВАЯ РАБОТА

                     Решение задачи коммивояжера

Работу выполнила студентка 3-го курса факультета компьютерных технологий и прикладной математики спец. 010501 – Прикладная математика и информатика

           Перхун Я. В.

Краснодар – 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………………………………………………3

  1.  Метод ветвей и границ..………………………………………………………………………….4
  2.  Метод Монте-Карло…………………………………………………………………………………7
  3.  Описание программной части……………………..…………………………………………10

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ………………………………………………13

1.Введение

В 1859 г. Вильям Гамильтон, знаменитый математик, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара.

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

Существует несколько методов решения задачи Коммивояжера, например, «жадный алгоритм», «деревянный алгоритм», «алгоритм Дейкстры», «метод ветвей и границ». В данной курсовой работе был реализован метод Монте-Карло, основанный на получении большого числа реализаций стохастического (случайного) процесса с попыткой формирования его таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи.

Ниже приведено описание реализация метода ветвей и границ и метода Монте-Карло при помощи средств объектно-ориентированного языка Java[1], [2].

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

Рассмотрим задачу о коммивояжере.

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

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

Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все n! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать кратчайший. Однако, n! с ростом n растет быстрее, чем любой полином от n, и даже быстрее, чем . Таким образом, решение задачи коммивояжера методом полного перебора оказывается практически неосуществимым, даже при достаточно небольших n.

Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.

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

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

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

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «».

Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил[2]:

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

.

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

,

каждая строка и столбец которой содержат хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.

3. Суммируем элементы и , получим константу приведения

,

которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть

.

4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

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

.

6. Разбиваем множество всех гамильтоновых контуров  на два подмножества  и . Подмножество гамильтоновых контуров содержит дугу ,  ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице  строку  и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «».

7. Приводим матрицу гамильтоновых контуров . Пусть  - константа ее приведения. Тогда нижняя граница множества определится так:

.

8. Находим множество гамильтоновых контуров , не включающих дугу . Исключение дуги  достигается заменой элемента  в матрице  на ∞.

9. Делаем приведение матрицы гамильтоновых контуров . Пусть  - константа ее приведения. Нижняя граница множества  определится так:

.

10. Сравниваем нижние границы подмножества гамильтоновых контуров  и . Если , то дальнейшему ветвлению в первую очередь подлежит множество . Если же , то разбиению подлежит множество .

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

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

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

3. Метод Менте-Карло.

Ниже описан  метод Монте-Карло для решения задачи коммивояжера. Случайные величины использовались для решения различных прикладных задач достаточно давно. Пример этого может служить способ определения числа Пи Бюффоном в 1777 году. Решение  задачи коммивояжера  основывается на случайном выборе каждого последующего города. Данный алгоритм можно сформулировать так:

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

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

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

Так как для количества вершин от 3 до 45 метод ветвей и границ дает оптимальное решение, то его результаты можно использовать для оценки погрешности ответа, полученного с помощью метода Монте – Карло.  Для подведения итогов в применении метода Монте- Карло протестирован  алгоритм по следующим показателям: количество городов, количество найденных путей, количество правильных ответов за время 100 испытаний. Данные занесены в таблицу:

Количество городов

Количество путей

Количество правильных ответов, %

5

5

73 %

6

91 %

10

100 %

         7

20

5 %

70

37 %

100

89 %

         

        10

1 000

0 %

5  000

10 %

10 000

46 %

На основе данных таблице можно сделать вывод  о том, что применение метода Монте – Карло дает оптимальное решение в большинстве случаев если количество городов, через которые следует проложить маршрут 3..10.  


4.Описание программной части.

Программа является клиент-серверным приложением, то есть состоит из двух взаимосвязанных частей: клиентской и серверной.

В роли клиента выступает Java-апплет, реализующий следующие функции:

  1.  Создание и обработка GUI;
  2.  Прием данных от пользователя;
  3.  Обмен данными с сервлетом.

Апплет отображается на странице index.html, поэтому может быть открыт в окне любого современного интернет-браузера, на который установлен плагин Java.

На стороне сервера расположены Java-сервлеты. Посредством них реализован следующий функционал:

  1.  Хранение необходимых для решения задачи данных;
  2.  Проведение всех математических расчетов;
  3.  Обмен данными с клиентской частью приложения.

Сервлеты помещены в сервлет-контейнер Tomcat v.7.0.21 от Apache Software Foundation, который также используется как самостоятельный веб-сервер. Выбор именно этого веб-сервера обусловлен сразу несколькими преимуществами:

  1.  Простота развертывания;
  2.  Легкость использования;
  3.  Небольшой размер приложения;
  4.  Бесплатность.

Выбор версии 7.0.21, а не более новой 7.0.22 связан с тем, что последняя еще не отмечена разработчиком как стабильная, а, значит, несмотря на более продвинутый функционал, может работать некорректно, в то время как 7.0.21 является последней версией в стабильной ветке.

В качестве среды разработки приложения была выбрана известная IDE NetBeans 7.1.2 от NetBeans Community. Такому выбору поспособствовали несколько достоинств данной программы:

  1.  Интуитивно-понятный интерфейс;
  2.  Удобный отладчик;
  3.  Наличие мануала от разработчиков;
  4.  Мощный функционал;
  5.  Бесплатность.

В качестве шаблона для создания приложения использован стандартный шаблон NetBeans «Веб-приложение», который разработан специально для таких ситуаций. Был сгенерирован основной класс, в котором реализованы обмен с сервером пакетами по методу POST, а также отрисовка GUI. Весь графический интерфейс состоит из объектов классов библиотеки awt, которая предоставляет набор базовых средств для работы с графикой.

Серверная часть представлена двумя сервлетами. Первый из них, EchoServlet отвечает за отправку клиенту необходимых данных, а именно – координат и названий городов, которые могут участвовать в задаче. Данные будут высланы не сразу, а лишь после получения отчета о готовности от апплета. Это сделано для того, чтобы при более ранней инициализации сервлета, чем апплета, пакет с информацией не был выслан в никуда.

Второй сервлет, MonteCarlo, ответственен за проведение расчетов после получения от апплета списка городов, через которые необходимо проложить маршрут. Приняв данные, сервлет высылает их вспомогательному классу CountDist, который проводит все необходимые расчеты и возвращает результат обратно. Полученный ответ высылается на апплет, который отображает его в удобном для пользователя виде.

Если описать процедуру поэтапно, то процесс решения задачи будет выглядеть так:

  1.  Инициализация сервлета и апплета;
  2.  Отсылка отчета о готовности апплетом сервлету;
  3.  Принятие отчета сервлетом, отсылка данных о городах на апплет;
  4.  Принятие пакета данных и построение карты по его данным;
  5.  Ввод условий задачи пользователем, отправка их на сервер;
  6.  Принятие условий задачи, их передача классу расчетов;
  7.  Произведение расчетов и возвращение ответа сервлету;
  8.  Отправка результатов клиенту;
  9.  Принятие результатов, отображение их в удобном пользователю виде.


  1.  
    Список используемых источников
    :

  1.  Герберд  Шилдт  «Полный справочник по Java».  Java SE 6 Edition 7-е издание.  Издательский дом  «Вильямс»  2008 год.
  2.   О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
  3.  Герберд Шилдт  «Swing. Руководство для начинающих». Издательский дом «Вильямс» 2007 год.


 

А также другие работы, которые могут Вас заинтересовать

51418. Факторизация больших чисел 386.5 KB
  2 Пусть S – множество содержащее r элементов – функция выбранная случайным образом из конечного числа функций.4 Существует взаимнооднозначное соответствие между представлением числа n в виде и в виде а именно: ; . Тогда мы будем подбирать такие числа t и s чтобы было квадратом небольшого числа s. Если полученные таким образом числа и не делят n то берется или .
51419. Гражданское право. Сделки в гражданском праве 172.5 KB
  Гражданское право основывается на признании равенства участников регулируемых им отношений, неприкосновенности собственности, свободы договора, недопустимости произвольного вмешательства в частные дела, беспрепятственном осуществлении гражданских прав, восстановлении нарушенных прав и их судебной защите.
51420. РАСЧЕТ СТОИМОСТИ ТУРА 91 KB
  Выберем элемент Список на панели Формы и отчертим прямоугольник на листе Выбор. Теперь этот объект нужно связать со столбцом Тур который находится на листе Расчет. Результат помещаем в ячейку А20 на листе Расчет. Теперь на листе Выбор укажем например Испания и проверим появился ли на листе Расчет в ячейке А20 порядковый номер тура т.