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

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

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



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






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


ПДМ, 2013, номер 4(22), страницы 73–81 (Mi pdm434)  

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

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

Задача коммивояжёра: улучшенная нижняя граница в методе ветвей и границ

Ю. Л. Костюк

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

Аннотация: Рассматривается решение задачи коммивояжёра методом ветвей и границ. Предлагается способ дополнительного (по сравнению с алгоритмом Литтла) уточнения нижней границы, особенно эффективный для случая симметричной матрицы, и на его основе строится новый алгоритм. С помощью вычислительного эксперимента получены оценки констант в формулах трудоёмкости для трёх модификаций алгоритма Литтла на трёх видах случайных матриц расстояний: 1) несимметричных матрицах со случайными расстояниями; 2) матрицах с евклидовыми расстояниями между случайными точками внутри квадрата; 3) несимметричных матрицах со случайными расстояниями, удовлетворяющими неравенству треугольника.

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

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

Образец цитирования: Ю. Л. Костюк, “Задача коммивояжёра: улучшенная нижняя граница в методе ветвей и границ”, ПДМ, 2013, № 4(22), 73–81

Цитирование в формате AMSBIB
\RBibitem{Kos13}
\by Ю.~Л.~Костюк
\paper Задача коммивояжёра: улучшенная нижняя граница в~методе ветвей и границ
\jour ПДМ
\yr 2013
\issue 4(22)
\pages 73--81
\mathnet{http://mi.mathnet.ru/pdm434}


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

    ОТПРАВИТЬ: 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. Ю. Л. Костюк, “Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью”, ПДМ, 2019, № 45, 104–112  mathnet  crossref
    2. Matsyi O., “Approaches to Solving Basic Problems of Closed Routes”, 15Th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (Tcset - 2020), IEEE, 2020, 69–72  crossref  isi  scopus
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:233
    Полный текст:77
    Литература:23
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021