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

 

 

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

 

по дисциплине:

    «Структуры  и алгоритмы обработки данных  »

на тему:

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

 

                                                                              

 

 

 

 

 

 

 

 

 

 

 

 

 

Аннотация

 

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

3   рисунка;

 5   таблиц

21  страниц машинописного текста.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

 

     В современной науке широкое распространение получили комбинаторные задачи. Для решения такого рода задач, несомненно, необходима ЭВМ, а также высокоэффективные алгоритмы решения этих задач. 

Большинство таких задач  основано на представлении в виде графа.

Одной из таких задач  является “Задача коммивояжера”.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.) Содержательная постановка задачи.

 

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

 

2.)Анализ  и пример решения задачи.

    Задача коммивояжера относится к NP трудным задачам. Сутью задачи является нахождение оптимального маршрута посещения n городов. Эту задачу можно сформулировать следующим образом:

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

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

  В терминах теории  графов задача формулируется  следующим образом:

Требуется найти в  данном графе гамильтонов цикл наименьшей стоимости.

  Известно, что при  количестве городов равном n существуют (n-1)!  возможных решений, из которых одно единственное является оптимальным. Искать оптимальное решение методом перебора всех этих значений тяжелая задача, даже для современных ЭВМ.

Для решения данной задачи существуют 2 группы методов.

Первые принадлежат  к группе “точных”  методов. Они  дают оптимальное, исчерпывающее решение. Другая группа – группа “приближенных” методов, которые дают не точные, а   приближенные решения. В наилучшем случае решения задачи этими методами может дать

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

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

Количество решений  всевозможных решений будет равно (4-1)!=6

 

        

 

 

 

 

 

 

 

                                                  

  

 

 

Вот все эти решения  и цена каждого маршрута

 

 

                                                                                     

Путь	Цена
ABCDA	11
ABDCA	21
ACBDA	18
ACDBA	21
ADBCA	18
ADCBA	11

              B                              

       1      2         3

    

    12

   A    1             6   C

 

                    D

Как видно из приведенной  таблицы оптимальным маршрутом  является  маршрут ABCDA.

Условие симметричности в данном случае позволяет отбросить  симметричные решения и искать оптимальный  маршрут всего из 3 возможных решений:

Путь	Цена
ABCDA	11
ABDCA	21
ACBDA	18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.) Формальная  постановка задачи.

 

 

3.1) Исходные  данные.

Исходные данные необходимые  для решения задачи коммивояжера следующие:

• Количество городов
• Названия городов
• Матрица стоимостей (путей).

 

3.2) Ограничения  на исходные данные

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

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

 

3.3) Результирующие  данные

Результатом решение  коммивояжера является вывод цепочки  городов оптимального маршрута и его стоимости, а также вывод приближенного тура и его стоимости.

 

3.4) Связь выходных  данных с исходными данными  

 a) Динамическое программирование.

      Пусть  даны множество  и .

Обозначим С(S,R) оптимальную стоимость пути, начинающегося в 1 городе и         оканчивающегося в R городе, проходящего по всем городам множества S.

Для вычисления С(S,R) при |S|>1 будем использовать тот факт, что для нахождения наилучшего маршрута из города множества S, достаточно рассмотреть для каждого m вариант, в котором m город, который посещается непосредственно перед городом R, и обратимся к C(S-{R}, m)  в предыдущей таблице. Таким образом :

 

 

 

 

 

 

 

 

 

 

 

b) Метод ближайшего соседа.

      Пусть  даны множество и .

Обозначим С(i,j) оптимальную стоимость пути из  i-го города в и j городе.

Для каждого i города будем выбирать тот город j, для которого выполняется

где множество L – это множество городов, в которые ход из i города запрещен.

Для каждого i города вычисления прекращаются, когда |L|=|S|

Этот процесс осуществляется для каждого i города, в который можно попасть из первого города.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.)Спецификация программы.

4.1)Исходные  данные.

Исходные данные должны быть представлены в файле с именем “In_ file.pas”

Структура описания данных в файле следующая:

- Количество городов  (целое число).

- Название городов  (название города представляет  собой одиночный символ, который ставится в соответствие этому городу).

- Матрица стоимостей  путей. (целочисленная матрица размерностью n*n).

Первый символ в строке описания названия городов автоматически  становится отправным городом.

 

4.2) Функции  программы по обработке исключительных ситуаций.

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

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

При всех критических  завершениях программы в выходной файл записывается строка:

“Error in input file”.

 

4.3)Выходные данные.

Выходные данные находятся  в файле с именем “Out_ file.pas”.

Структура выходных данных следующая:

Данные для решения  задачи методом динамического программирования:

- Строка из цепочки  городов входящих в оптимальный  тур.

- Стоимость найденного  оптимального тура.

Данные для решения  задачи методом ближайшего соседа:

- Строка из цепочки  городов входящих в оптимальный  тур.

- Стоимость найденного  оптимального тура.

 

 

4.4)Сценарий  диалога.

Для правильной работы программы необходимо обязательно создать входной  файл с необходимыми данными. Данный файл создается в той же директории что и сама программа. Название файла имеет следующее название : “In_ file.pas”.

Далее пользователю необходимо запустить  программу на выполнение.

Файл выходными данными создается  автоматически, в той же директории и имеет имя : “Out_ file.pas”.

 

 

 

 

 

 

 

5.)Разработка  структур данных и алгоритмов.

Рассмотрим словесно-содержательные алгоритмы для каждого из методов.

 а) Метод динамического программирования.

         Начало

1)Ввод кол-ва  городов |S|.

2)Ввод множества  городов S.

3)Ввод матрицы  стоимости путей.

4)Пусть  С(S,r) есть оптимальный тур по всем городам множества S начинающийся в 1 городе и оканчивающийся в городе r. Используя реккурентную формулу:

вычислим  предыдущие оптимальные туры для  всех m из множества S ,

где m- город, который посещается непосредственно перед узлом r.

D_mr расстояние от города m до города r.

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

5)Выведем  цепочку городов входящих в  найденный оптимальный тур в  обратном порядке.

Конец.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b) Метод ближайшего соседа.

Начало

1.)Ввод кол-ва  городов n .

2.)Ввод названия  городов.

3.)Ввод матрицы  стоимости путей.

4.)Создание для каждого города записи содержащей следующие поля:

    Поле для хранения названия  города.

    Поле для хранения индекса  города в матрице стоимости  путей.

    Поле для хранения множества  городов, не подлежащих дальнейшей  проверке.

    Поле для хранения городов вошедших в текущий маршрут.

    Поле для хранения общего стоимости  пути текущего тура.

5.)Запись  стоимости пути от первого  города до i города, в поле хранения стоимости путей тура каждого i города .  ( i=2..n )

6.)Запись  первого города в число городов  вошедших в текущий маршрут  i города.

7.)Запись  первого города в множества   городов, не подлежащих дальнейшей  проверке  каждого i города. ( i=2..n )

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

9.)Добавление  найденного города в число  городов, вошедших в текущий  маршрут i города.

10.)Добавления  стоимости пути от i города к найденному, в поле хранения общей стоимости путей текущего маршрута, для данного i города.

11.)Добавление  найденного города в множество  городов, не подлежащих дальнейшей  проверке, данного i города.

12.)Запись  названия найденного города в  поле хранения названия i города.

13.)Если  для всех i городов, мощность множества городов, не подлежащих дальнейшей проверке равна n, то переход к пункту 14, иначе переход к пункту 8;

14.)Добавить  к полю для хранения общей  стоимости пути текущего тура  i города, расстояния до первого города. ( i=2..n )

15.)Вывод  наименьшей из стоимостей общего  пути тура из всех i городов. ( i=2..n )

Конец.

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