ВВЕДЕНИЕ 3
1. ЗАДАЧА КОММИВОЯЖЕРА 6
1.1. Методы решения 6
1.2. Дополнительные сведения 9
1.3. Описание метода Лина 11
2. РЕАЛИЗАЦИЯ АЛГОРИТМА 15
2.1. Исходные данные 16
2.1.1. Функция перестановок 18
2.2. Окно программы 19
3. ПРОВЕДЕНИЕ ЭКСПЕРИМЕНТОВ 22
ЗАКЛЮЧЕНИЕ 28
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 30
ПРИЛОЖЕНИЕ
В 1831 г. в Германии вышла книга под названием «Кто такой коммивояжер и что он должен делать для процветания своего предприятия». Одна из рекомендаций этой книги гласила: «Важно посетить как можно больше мест возможного сбыта, не посещая ни одно из них дважды». Так звучала первая формулировка задачи коммивояжера [1].
Сейчас есть более полная постановка задачи. Дана карта городов. Между городами существуют дороги с различными длинами. Расстояния между любой парой городов известны. Коммивояжер обязан посетить каждый из заданных n городов только один раз, начиная с любого города, и возвратиться к исходному месту отправления. Какой маршрут он должен выбрать, чтобы длина всего цикла была минимальной?
Эта проблема, задача коммивояжера (ЗК), является одной из наиболее широко изученных в задачах комбинаторной оптимизации. Проблема проста в определении, но трудна в решении.
Важность ЗК проистекает из ряда областей, самой очевидной из которых является транспорт. Сейчас набирают популярность курьерские службы, которым необходимо доставить товар в разные точки за минимальное время и с наименьшими затратами. Таксистам крайне важно составлять оптимальный маршрут, чтобы быть конкурентоспособными. За примером далеко ходить не надо: в ближайшее время в России пройдут сначала Кубок конфедераций, а затем и Чемпионат мира по футболу. В нашу страну приедет большое количество туристов, они наверняка захотят изучить местные достопримечательности. Вот здесь и понадобиться возможность строить оптимальные маршруты через весь город.
Но есть и менее очевидные сферы применения. Например, задача планирования процесса. Ряд работ должен быть обработан на одной машине. Машина может обрабатывать только одно задание за раз. Перед тем, как работа может быть обработана, машина должна быть готова. Принимая во внимание 3
время выполнения каждого задания и время переключения между каждой парой работ, задача состоит в том, чтобы найти последовательность выполнения заданий, в результате чего общее время выполнения будет как можно меньше.
Отчетливо видно, что эта проблема является примером ЗК. Здесь cij представляет собой время, чтобы завершить работу j после работы i (переключение между работами прибавляется ко времени выполнения задания j). Работа со временем выполнения равная нулю означает начало и окончание выполнения работ.
Не меньший интерес задача представляет для исследователей и специалистов в области дискретной оптимизации [5].
Множество проблем из реального мира может быть сформулировано как пример задач коммивояжера. Ее многофункциональность иллюстрируется следующими примерами областей применения:
• Компьютерная проводка
• Листовая резка деталей
• Кристаллография
• Управление роботами
• Сверление печатных плат
ЗК является типичной задачей комбинаторной оптимизации. Это означает, что теоретическое и практическое понимание, достигаемое при изучении ЗК, зачастую может быть использовано при решении других проблем в этой области.
Существует большое количество методов решения данной задачи, как точных, так и эвристических, [3]. Первые гарантировано находят оптимальный маршрут, однако очень чувствительны к специфике задачи и наличию дополнительных условий. К тому же, большинство из них не способно найти ответ на большом (более 100) числе городов ввиду того, что количество возможных маршрутов равно (и — 1)! для несимметричной матрицы.
Эвристические алгоритмы не всегда находят оптимальный маршрут, чаще всего выдавая приближенный. Зато, они способны работать с большим числом городов. Учитывая, что задача находит большое применение в различных сферах деятельности человека, лучше иметь приближенный ответ, чем не иметь вовсе.
Метод Лина, который будет подробно рассматриваться в данной работе, относится к классу эвристических. В обзорной статье [4] сказано, что ни один другой алгоритм в то время не показал столь же хорошую эффективность, какая была получена у автора данного алгоритма.
Моим научным руководителем было предложено рассмотреть метод Лина, потому что он допускает большое количество реализаций, разработать несколько и сравнить их между собой.
Цель дипломной работы:
Найти наиболее эффективную реализацию алгоритма, основанного на методе Лина.
Задачи:
1. Изучить имеющиеся методы решения задачи.
2. Подробно изучить суть метода, предложенный Лином.
3. Разработать программу, реализующую различные вариации алгоритма.
4. Проанализировать поведение алгоритмов и выяснить, какая реализация алгоритма лучше всего справляется с решением задачи коммивояжера.
В ходе работы были поставлены следующие задачи:
1. Изучить имеющиеся методы решения задачи.
2. Подробно изучить суть метода, предложенный Лином.
3. Разработать программу, реализующую различные вариации алгоритма.
4. Проанализировать поведение алгоритмов и выяснить, какая реализация алгоритма лучше всего справляется с решением задачи коммивояжера.
В первой главе была поставлена математическая формулировка задачи коммивояжера. изучены методы решения. Кратко были обозначены достоинства и недостатки алгоритмов. Подробно был изучен метод Лина, который лег в основу разработанной программы, реализующей несколько реализаций алгоритмов.
Программа, написанная на языке C++, позволяет пользователю менять параметры матрицы смежности, выбирать, по каким критериям будет работать алгоритм и предоставляет полученные данные в виде текстового файла с содержанием хода работы и полученными результатами.
В ходе экспериментов была проанализирована работа алгоритмов при решении задач с различными исходными данными. Так как было неизвестно, как ведут себя алгоритмы при решении задач, в первую очередь были определены исходные параметры для критериев остановки и поиска, по которым они работают. Для выявления победителя среди алгоритмов проводились эксперименты на матрицах большой размерности. Наилучшие результаты показала реализация алгоритма с критерием остановки после серии безуспешных итераций и с регулярным выбором кусков в маршруте.
Данную программу можно будет применять во всех сферах деятельности человека, где исходная задача сводится к решению задачи коммивояжера. К таким сферам относятся металлургия (изготовление деталей), составление расписаний для рабочих машин в производстве, транспорт (курьерские услуги, построение оптимального маршрута в городе), туризм.
28
Так как целью работы было провести анализ алгоритмов, а не выставление программы на продажу, программа не имеет пользовательского графического интерфейса, вместо этого ограничившись консольным. В дальнейшем предлагается добавить графику, чтобы наглядно показывать работу алгоритма на графах на каждом шаге итераций.
Также, в ходе тестирования программы, был выявлен недостаток исходного метода, заключающийся в том, что алгоритм может дать локально оптимальный тур, но при этом это может привести к блокировке других возможных оптимальных туров. В дальнейшем, с целью решения данной проблемы предлагается модифицировать текущий алгоритм с учетом существующих методов улучшения оригинального метода Лина. Одним из таких улучшений является использование динамического значения параметра к (в разработанном методе используется фиксированное значение равное трем). Также можно попробовать проводить построение графа с помощью других методов с дальнейшим применением разработанного алгоритма, тем самым увеличив вероятность нахождения оптимального решения.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
