RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2013, номер 2(20), страницы 78–90 (Mi pdm410)  

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Вычислительные методы в дискретной математике

Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ

Ю. Л. Костюк

Национальный исследовательский Томский государственный университет, г. Томск, Россия

Аннотация: Для известного алгоритма точного решения задачи коммивояжёра методом ветвей и границ (алгоритма Литтла) предлагается следующая модификация. На каждой промежуточной стадии выполнения алгоритма вычисляется более точная оценка снизу для всех альтернативных маршрутов, которые можно построить на основе текущего частичного решения. Благодаря этому, отсечение бесперспективных вариантов выполняется, как правило, намного эффективнее, особенно для случайной несимметричной матрицы расстояний. Рассмотрены реализации модифицированного алгоритма с поиском вглубь и вширь, а также с поиском вглубь, когда ищется приближенный маршрут с произвольно задаваемой погрешностью. Для функции трудоёмкости $U(n)=a\cdot c^n$, измеряющей количество обрабатываемых матриц расстояний (узлов дерева решений) в графе с $n$ вершинами, с помощью вычислительного эксперимента получены оценки констант $a$ и $c$ для различных реализаций алгоритма. При этом время обработки каждого узла увеличивается в 1,5–2 раза при существенном уменьшении общего времени выполнения алгоритма.

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

Полный текст: PDF файл (882 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.7

Образец цитирования: Ю. Л. Костюк, “Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ”, ПДМ, 2013, № 2(20), 78–90

Цитирование в формате AMSBIB
\RBibitem{Kos13}
\by Ю.~Л.~Костюк
\paper Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ
\jour ПДМ
\yr 2013
\issue 2(20)
\pages 78--90
\mathnet{http://mi.mathnet.ru/pdm410}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm410
  • http://mi.mathnet.ru/rus/pdm/y2013/i2/p78

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Ю. Л. Костюк, “Задача коммивояжёра: улучшенная нижняя граница в методе ветвей и границ”, ПДМ, 2013, № 4(22), 73–81  mathnet
    2. В. В. Васильчиков, “Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера”, Модел. и анализ информ. систем, 23:4 (2016), 401–411  mathnet  crossref  mathscinet  elib
    3. V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Autom. Control Comp. Sci., 51:7 (2017), 551–557  crossref  isi  scopus
    4. V. V. Burkhovetskiy, B. Ya. Steinberg, “Parallelizing an exact algorithm for the traveling salesman problem”, 6th International Young Scientist Conference on Computational Science (YSC 2017), Procedia Computer Science, 119, eds. A. Klimova, A. Bilyatdinova, J. Kortelainen, A. Boukhanovsky, Elsevier Science BV, 2017, 97–102  crossref  isi  scopus
    5. Ю. Л. Костюк, “Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью”, ПДМ, 2019, № 45, 104–112  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:2407
    Полный текст:649
    Литература:75
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020