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

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

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

Автор:

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

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

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

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

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

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



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

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

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

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

Есть 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).

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


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

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

Похожие статьи

Математические методы маршрутизации доставки светлых...

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

Целочисленное решение задач линейного программирования...

При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.

Компьютерная модель для лабораторной работы...

Для решения данной задачи был использован методветвей и границ” [3], являющийся одним из основных для решения задач дискретного программирования. В табл. 1 приведена матрица параметров траектории (например, расстояние, экономические затраты и т. п.) для простого...

Алгоритмы нахождения пути, их сравнение и визуализация на...

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

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

Анализ поисковых алгоритмов при решении задач идентификации...

Суть метода заключается в сведении поиска по сходству к точному поиску.

Простейшее решение задачи перебора состоит в последовательном сравнении, начиная с t(1)

На практике при решении задач точного поиска в большинстве случаев алгоритм Бойера-Мура работает...

Особенности изучения способа тестирования базового пути...

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

Путь начинается в начальном узле, а заканчивается в конечном узле графа. Независимые пути формируются в порядке от самого короткого к самому длинному.

Реализация алгоритма поиска ближайших объектов с помощью...

В данной статье разработан алгоритм поиска ближайших объектов с помощью вспомогательной структуры, основанной на K-D tree, а также рассматривается приложение на языке Java, реализующее данный алгоритм.

Эффективность применения поиска полным перебором...

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи.

Похожие статьи

Математические методы маршрутизации доставки светлых...

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

Целочисленное решение задач линейного программирования...

При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.

Компьютерная модель для лабораторной работы...

Для решения данной задачи был использован методветвей и границ” [3], являющийся одним из основных для решения задач дискретного программирования. В табл. 1 приведена матрица параметров траектории (например, расстояние, экономические затраты и т. п.) для простого...

Алгоритмы нахождения пути, их сравнение и визуализация на...

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

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

Анализ поисковых алгоритмов при решении задач идентификации...

Суть метода заключается в сведении поиска по сходству к точному поиску.

Простейшее решение задачи перебора состоит в последовательном сравнении, начиная с t(1)

На практике при решении задач точного поиска в большинстве случаев алгоритм Бойера-Мура работает...

Особенности изучения способа тестирования базового пути...

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

Путь начинается в начальном узле, а заканчивается в конечном узле графа. Независимые пути формируются в порядке от самого короткого к самому длинному.

Реализация алгоритма поиска ближайших объектов с помощью...

В данной статье разработан алгоритм поиска ближайших объектов с помощью вспомогательной структуры, основанной на K-D tree, а также рассматривается приложение на языке Java, реализующее данный алгоритм.

Эффективность применения поиска полным перебором...

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи.

Задать вопрос