Метод ветвей и границ для решения задачи о коммивояжёре | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 6 марта, печатный экземпляр отправим 10 марта.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №2 (344) январь 2021 г.

Дата публикации: 09.01.2021

Статья просмотрена: 22 раза

Библиографическое описание:

Клоков, С. А. Метод ветвей и границ для решения задачи о коммивояжёре / С. А. Клоков. — Текст : непосредственный // Молодой ученый. — 2021. — № 2 (344). — С. 21-23. — URL: https://moluch.ru/archive/344/77401/ (дата обращения: 25.02.2021).



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

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

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

Формулировка задачи:

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

Расстояние из города j в город i считается неотрицательным числом: Dji ≥ 0. Часто Dji называют стоимостью ребра, так как дороги можно представить рёбрами, соединяющими города-вершины некоторого графа.

Допускается несимметричность матрицы Dji ≠ Dji. В ещё более общем случае пути между некоторыми городами могут отсутствовать.

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

Необходимые поля:

− Количество узлов

− Массив минимального пути

− Посещенные пути при текущем проходе

− Вес минимального пути

Необходимые методы:

− Начальный метод поиска пути

− Рекурсивный метод построения пути для заданного начала (в качестве параметра)

− Первый минимум массива

− Второй минимум массива

− Сохранение пути

Алгоритм начального метода поиска пути

− Инициализация нижней границы (bound):

− Цикл вызова рекурсивного поиска минимального пути для каждого узла в качестве начальной точки

Алгоритм рекурсивного поиска пути

− Если все пройдено

  • Если есть путь до начальной точки
    • Длина пройденного пути = переданная длина + путь до начальной точки
    • Если длина пути меньше минимальной длины
      • Сохраняем путь и длину в качестве минимальных
  • Завершаем метод

− Иначе проходим по всем путям (i=0..N-1)

  • Если есть путь до не посещенной точки
    • Сохраняем нижнюю границу
    • Идем в узел i
    • Добавляем к текущей длине пути
    • Вычисляем нижнюю границу для текущего пути по формуле выше

− Если текущая длина + граница для текущего пути меньше минимума

  • Рекурсивный вызов следующего уровня (проходим в узел i)
  • Обрезаем узел
  • Очищаем массив посещенных узлов

Расчеты

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

(10! вариантов путей) * (10 переходов на 1 путь) = 36 288 000 переходов

Таблица 1

Таблица количества переходов

Номер матрицы

Количество переходов

Номер матрицы

Количество переходов

Номер матрицы

Количество переходов

1

89

11

476

21

442

2

179

12

113

22

691

3

2340

13

2294

23

605

4

689

14

1819

24

483

5

1616

15

3240

25

2180

6

309

16

290

26

147

7

4175

17

3270

27

1262

8

2365

18

2606

28

622

9

914

19

734

29

97

10

93

20

3576

30

2099

Среднее количество переходов: 1328 , что меньше грубого подхода в 27 325 раз.

Вывод

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

Литература:

1. Тема 4: Методы неявного перебора. — Текст: электронный // Дискретные задачи размещения: [сайт]. — URL: http://math.nsc.ru/LBRT/k4/or/or_part4.pdf (дата обращения: 06.01.2021).

2. Глава 4. Задача коммивояжера. — Текст: электронный // Дискретные задачи размещения: [сайт]. — URL: http://www.math.nsc.ru/LBRT/k5/OR-MMF/TSPr.pdf (дата обращения: 07.01.2021).

3. Метод ветвей и границ. — Текст: электронный // Экономико-математические методы: [сайт]. — URL: http://www.math.mrsu.ru/text/courses/method/metod_vetvei_i_granic.htm (дата обращения: 06.01.2021).

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


Ключевые слова

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