Рис. 3. Ветвление на третьем шаге

     Приведенная платежная матрица для   

 

     Степени Θ_ij нулевых элементов этой матрицы Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7. Выбираем Θ₃₅ = 8. Разбиваем на и .

     Нижняя  граница для равна 55 + 8 = 64. В матрице для вычеркиваем строку 3 и столбец 5 и полагаем c₆₃= ∞. Получим 

 

     Для приведения надо вычесть минимум  по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим 

     Из  матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

     

     Рис. 4 Ветвление на четвертом шаге 

     

     Рис. 5 Дерево ветвления с оценками 

     Полученный  маршрутом коммивояжера z₀ = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).

 

      Глава 3. Программная  реализация метода ветвей и границ

     3.1. Язык программирования

 

     Для написания программы был выбран язык Си++ по следующим причинам:

1. Среда программирования Windows-приложений Microsoft Visual C++ 6.0 позволяет в моей задаче наглядно отобразить карту городов и схему их соединения.
2. Это один из языков, в котором я неплохо разбираюсь. Поэтому мне удобнее  писать программу с помощью Visual C++.

     3.2. Описание алгоритма

 

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

1. Для каждого города (i = от 1 до n), где мы еще не были.
2. Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были.
3. Подсчитываем длину пройденного пути.
4. Если она больше чем длина минимального пути,
1. Тогда нет смысла идти по этому пути дальше.
1. помечаем город как не посещенный, выходим из города.
2. Иначе,
1. если мы в конце пути
1. тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути,  тогда минимальный путь = кратчайший путь.
2. иначе переходим к пункту 1.
5. Переходим к следующему городу, где мы не были.

     Следует рассмотреть один из основных моментов алгоритма, связанных с перебором  маршрутов. Из рисунка №2 можно проследить порядок формирования путей и  рассмотреть на конкретном примере, как работает алгоритм. Здесь приведен пример для 4 городов. Остановимся на рисунке по подробнее.

1. Мы начинаем путь из пункта 1. В нашем маршруте записан первый город. Рассматриваем те города, где мы не были: это 2, 3 и 4. Сначала переходим во второй.
2. Добавляем к маршруту 2 город. Смотрим, можно ли куда-то перейти из второго города. Можно посетить третий и четвертый. Мы выбираем третий город.
3. Ставим на третье место в нашем маршруте город 3. Далее мы смотрим, куда можно отправиться – в пункт 4.
4. На четвертое место в маршруте ставим город 4. Здесь мы видим, что в нашем маршруте заполнены все четыре места и значит наш путь закончен. Сравниваем длину нашего пути с минимальным. Затем мы выходим назад из пункта 4 в пункт 3 и в маршруте перемещаемся на третье место. Смотрим, что в городе 3 мы были, тогда берем следующий не посещенный город – четвертый.
5. Ставим на третье место маршрута четвертый город. Из четвертого пункта можно посетить только третий.
6. Пришли в третий пункт. Ставим на четвертое место маршрута город 3. Видим, что все четыре места в нашем пути заполнены и значит путь закончен. Сравниваем длину нашего пути с минимальным. Выходим назад – из пункта 3 в пункт 4 и в маршруте перемещаемся на третье место. Видим что здесь тоже нет не посещенных городов. Опять переходим на уровень вверх: из пункта 4 в пункт2 и в маршруте перемещаемся на второе место. В пункте 2 мы были, но остались не посещенными города 3 и 4. Переходим в третий. На второе место в маршруте записываем третий город.
7. Отсюда можно попасть во второй и четвертый. Переходим во второй. На третье место в маршруте ставим второй город. И так далее.

     Из  приведенного примера уже можно  выделить, как алгоритм перебирает пути. Он действует по следующей  схеме:

0. Начальное значение j = 1 (первое место в маршруте).
1. Мы находимся в городе  k.
2. Для каждого города (i = от 1 до n)
3. Рассматриваем город i.
4. Если этот город еще не посещен,
1. тогда переходим в город i;  j увеличиваем на единицу. Добавляем номер города в маршрут на место j. Помечаем город как посещенный. Переходим к пункту 1 (k = i).
2. иначе идти некуда, т.е. все города мы посетили.
1. если j = количеству городов (n), т.е мы добрались до последнего пункта в маршруте и наш путь сформирован, тогда сравниваем длину пути с длиной минимального маршрута.
2. Помечаем город как не посещенный и выходим из него. Уменьшаем j на единицу.
5. Берем следующий город (i=i+1).

 

     

 
3.3. Описание основных структур данных

 

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

     Программа состоит из 4 классов:

1. CAboutDlg связан со встроенным диалоговым окном «О программе».
2. CKurs_LipinApp управляет запуском приложения и не связан с каким-либо диалоговым окном.  [1]
3. CKurs_LipinDlg связан с окном IDD_KURS_LIPIN_DIALOG. Этот класс организует постановку и решение задачи.
4. CSetting связан с окном IDD_DIALOG1. В окне вводятся параметры к задаче – расстояния между городами.

     Класс CKurs_LipinDlg. В начале при вызове функции OnInitDialog() переменные заполняются начальными данными. Затем из файла «table.ini» считывается таблица расстояний между городами. И теперь диалоговое окно готово к работе с пользователем. Функция OnPaint() выводит на экран карту, позволяет выделять города, выбранные пользователем, а также соединяет города линиями-путями, когда задача решена. Кроме того, обеспечивается вывод информации для пользователя: пояснения, длина минимального пути и список расстояний между городами, составляющие минимальный путь.

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

     Кнопка  «Выбрать стандартные города» выделяет города, которые требуется соединить  в условии задачи, а именно Москва, Ярославль, Нижний Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецк, Тамбов, Орел, Курск, Тула. Кнопка «Очистить» снимает выделение со всех городов и задает начальные значения ряду необходимых переменных.

     Функция OnButton3() связана с кнопкой «Задать пункт отправления». После нажатия кнопки пользователь может щелчком мыши выбрать пункт отправления коммивояжера. Кнопка «Параметры» вызывает диалоговое окно «Параметры», где пользователь может редактировать таблицу расстояний между городами. Функция OnOK() обрабатывает нажатие кнопки «Рассчитать путь». Она подготавливает начальные значения для вызова рекурсивной функции: создается таблица расстояний только для выделенных городов, заполняется первоначальный минимальный путь, выводится поясняющая информация. Затем вызывается функция recursiv(), которая перебирает варианты маршрутов, отсекает лишние ветви путей и находит минимальный.

     Класс CSetting.

     Функция OnInitDialog() программным путем создает и выводит поля ввода, имитируя таблицу расстояний между городами. Затем считывается файл «table.ini», и заполняются поля ввода полученными значениями. Вызывается функция Proverka(), которая сканирует полученные данные на ошибки, т.е. определяет введены ли только цифры, и если нет, тогда удаляет все лишние символы.

     По  нажатию кнопки «Сохранить» программа  передает данные в родительское окно, записывает данные из полей ввода  в файл и закрывает диалоговое окно.

     3.4. Описание интерфейса с пользователем

 

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

     Чтобы отменить выделение  городов нужно  щелкнуть по кнопке «Очистить». Нажав  кнопку «Рассчитать путь», мы получим  результат: города соединены минимальным  путем, его длина дана в окне информации, в списке показаны расстояния между городами, входящими в полученный путь. Кнопка «Выбрать стандартные города» выделяет города, требуемые в задании.

     Чтобы выделить пункт отправления коммивояжера нужно выбрать «Задать пункт  отправления».

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

     Здесь пользователь может отредактировать  расстояния между городами. Для этого нужно щелкнуть в поле ввода, и ввести другое значение. Перемещаться по этой «таблице» можно по строкам при помощи клавиш Tab или Shift+Tab.

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

     Кнопка  «Отмена» позволяет не сохранять  введенные изменения, если пользователь ошибся во введенной информации.

     По  нажатии любой из кнопок диалоговое окно «Параметры» закрывается и мы возвращаемся к главному окну.

     Если  в строке заголовка главного окна щелкнуть правой кнопкой мыши и выбрать  пункт «О программе», то появится диалоговое окно, содержащее сведения о программе  и об авторе. Нажав кнопку «OK» возвращаемся к главному окну.

 

      Заключение 

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

 

Литература 

1. Круглински  Д., Программирование на Microsoft Visual C++ 6.0 для профессионалов/Пер.с англ. –СПб:Питер; 2004г. – 861 с.: ил.
2. Беляев С.П. Курс лекций по «Исследованию операций».                            3.     Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1990.-410 с., ил.                   4.     Братко. Программирование на языке Пролог для искусственного интеллекта:                                               Пер. с англ. -М.: Мир, 1990.- 560 с      5.     Ананий В. Левитин Глава 3. Метод грубой силы: Задача коммивояжера // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 159-160.                                                                                     6.     Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.:«Вильямс», 2006. — С. 1296.                                                                        7.      В.И. Мудров Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.