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

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

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



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






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


Модел. и анализ информ. систем, 2020, том 27, номер 1, страницы 72–85 (Mi mais704)  

Algorithms

Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа

А. Н. Максименко

Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14, Ярославль, 150003, Россия

Аннотация: В настоящей работе рассматривается понятие линейного разделяющего алгоритма прямого типа, введенное В. А. Бондаренко в 1983 г. Понятие алгоритма прямого типа определяется с помощью графа решений задачи комбинаторной оптимизации. Вершинами этого графа служат все допустимые решения задачи. Два решения называются смежными, если существуют входные данные, для которых эти решения и только они являются оптимальными. Ключевой особенностью алгоритмов прямого типа является то, что их трудоемкость оценивается снизу кликовым числом графа решений. В 2015-2018 гг. было опубликовано пять работ, основными результатами которых являются оценки кликовых чисел графов многогранников, ассоциированных с различными задачами комбинаторной оптимизации. В качестве основной мотивации в этих работах приводится тезис о том, что класс алгоритмов прямого типа является широким и включает в себя многие классические комбинаторные алгоритмы, в том числе алгоритм ветвей и границ для задачи коммивояжера, предложенный J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel в 1963 г. Мы покажем, что этот алгоритм не является алгоритмом прямого типа. Ранее, в 2014 г., автором настоящей работы было показано, что венгерский алгоритм для задачи о назначениях не является алгоритмом прямого типа. Таким образом, класс алгоритмов прямого типа не является настолько широким, как предполагалось ранее.

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

DOI: https://doi.org/10.18255/1818-1015-2020-1-72-85

Полный текст: PDF файл (657 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.16
MSC: 90C57
Поступила в редакцию: 03.12.2019
Исправленный вариант: 05.01.2020
Принята в печать:28.02.2020

Образец цитирования: А. Н. Максименко, “Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа”, Модел. и анализ информ. систем, 27:1 (2020), 72–85

Цитирование в формате AMSBIB
\RBibitem{Mak20}
\by А.~Н.~Максименко
\paper Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа
\jour Модел. и анализ информ. систем
\yr 2020
\vol 27
\issue 1
\pages 72--85
\mathnet{http://mi.mathnet.ru/mais704}
\crossref{https://doi.org/10.18255/1818-1015-2020-1-72-85}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais704
  • http://mi.mathnet.ru/rus/mais/v27/i1/p72

    ОТПРАВИТЬ: 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
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:51
    Полный текст:7
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020