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

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

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



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






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


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

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

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

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

Ю. Л. Костюк

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

Аннотация: Для известного алгоритма точного решения задачи коммивояжёра методом ветвей и границ (алгоритма Литтла) предлагается следующая модификация. На каждой промежуточной стадии выполнения алгоритма вычисляется более точная оценка снизу для всех альтернативных маршрутов, которые можно построить на основе текущего частичного решения. Благодаря этому, отсечение бесперспективных вариантов выполняется, как правило, намного эффективнее, особенно для случайной несимметричной матрицы расстояний. Рассмотрены реализации модифицированного алгоритма с поиском вглубь и вширь, а также с поиском вглубь, когда ищется приближенный маршрут с произвольно задаваемой погрешностью. Для функции трудоёмкости $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
    6. В. В. Бурховецкий, “Оптимизация и распараллеливание упрощенного алгоритма Балаша–Кристофидеса для задачи коммивояжера”, Программные системы: теория и приложения, 11:4 (2020), 3–16  mathnet  crossref
    7. Shramenko N., Muzylyov D., Shramenko V., “Service Costs in Operational Planning of Transportation With Small Batches of Cargo in City”, Advances in Design, Simulation and Manufacturing III: Manufacturing and Materials Engineering, Vol 1, Lecture Notes in Mechanical Engineering, eds. Ivanov V., Trojanowska J., Pavlenko I., Zajac J., Perakovic D., Springer International Publishing Ag, 2020, 201–209  crossref  isi  scopus
    8. Shramenko N., Muzylyov D., Shramenko V., “Methodology of Costs Assessment For Customer Transportation Service of Small Perishable Cargoes”, Int. J. Bus. Perform. Manag., 21:1-2 (2020), 132–148  crossref  isi
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:3261
    Полный текст:896
    Литература:91
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021