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

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

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



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






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


Автомат. и телемех., 2018, выпуск 7, страницы 149–166 (Mi at14693)  

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

Оптимизация, системный анализ и исследование операций

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

В. А. Головешкинab, Г. Н. Жуковаc, М. В. Ульяновde, М. И. Фомичевc

a Московский технологический университет
b Институт прикладной механики РАН (ИПРИМ РАН), Москва
c Национальный исследовательский университет "Высшая школа экономики", Москва
d Институт проблем управления им. В. А. Трапезникова РАН, Москва
e ВМК МГУ им. Ломоносова

Аннотация: Приведены результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные при обработке специально сгенерированного пула матриц. Показано, что нормальное распределение может служить приближением для распределения логарифма сложности при фиксированной размерности задачи. Построено семейство вероятностных распределений, являющихся удовлетворительными приближениями распределения сложности при размерности матрицы стоимостей от 20 до 49. Основная цель – вероятностный прогноз сложности индивидуальных задач для бóльших значений размерности матрицы стоимостей. Предложено представление распределения сложности, позволяющее прогнозировать сложность. Сформулирована гипотеза об унификации и указаны направления развития исследований – предложения по задаче кластеризации “сложных” и “простых” задач NTSP и предложения по задаче непосредственного прогнозирования сложности индивидуальной задачи по исходной матрице стоимостей.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-07-160
Российский научный фонд 17-19-01665
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 16-07-160) и Российского научного фонда (проект № 17-19-01665).

Автор для корреспонденции

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

Англоязычная версия:
Automation and Remote Control, 2018, 79:7, 1296–1310

Реферативные базы данных:

Тип публикации: Статья
Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 28.02.2017

Образец цитирования: В. А. Головешкин, Г. Н. Жукова, М. В. Ульянов, М. И. Фомичев, “Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным”, Автомат. и телемех., 2018, № 7, 149–166; Autom. Remote Control, 79:7 (2018), 1296–1310

Цитирование в формате AMSBIB
\RBibitem{GolZhuUly18}
\by В.~А.~Головешкин, Г.~Н.~Жукова, М.~В.~Ульянов, М.~И.~Фомичев
\paper Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным
\jour Автомат. и телемех.
\yr 2018
\issue 7
\pages 149--166
\mathnet{http://mi.mathnet.ru/at14693}
\elib{http://elibrary.ru/item.asp?id=35757396}
\transl
\jour Autom. Remote Control
\yr 2018
\vol 79
\issue 7
\pages 1296--1310
\crossref{https://doi.org/10.1134/S0005117918070093}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000438654700009}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85049941140}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at14693
  • http://mi.mathnet.ru/rus/at/y2018/i7/p149

    ОТПРАВИТЬ: 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, № 11, 155–172  mathnet  crossref; G. N. Zhukova, M. V. Ul'yanov, M. I. Fomichev, “A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency”, Autom. Remote Control, 80:11 (2019), 2054–2067  crossref  isi  elib
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:126
    Литература:11
    Первая стр.:12
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020