Все
 
 
 


Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным
 
Код статьиS000523100000273-4-1
DOI10.31857/S000523100000273-4
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Головешкин Василий Адамович 
Аффилиация:
Московский технологический университет
Институт прикладной механики РАН (ИПРИМ РАН)
Жукова Галина Николаевна
Аффилиация: Национальный исследовательский университет «Высшая школа экономики»
Адрес: Российская Федерация
Ульянов Михаил Васильевич
Аффилиация:
Институт проблем управления РАН им. В.А. Трапезникова
МГУ им. Ломоносова
Адрес: Российская Федерация
Фомичев Михаил Игоревич
Аффилиация: Национальный исследовательский университет «Высшая школа экономики»
Адрес: Российская Федерация
Название журналаАвтоматика и телемеханика
ВыпускВыпуск 7
Страницы149-167
Аннотация

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

Ключевые словаЗадача коммивояжера, сложность индивидуальной задачи коммивояжера, аппроксимация вероятностного распределения, квантильный коэффициент асимметрии, квантильный коэффициент эксцесса, вероятностный прогноз
Источник финансированияРабота выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 16-07-160) и Российского научного фонда (проект № 17-19-01665).
Получено29.09.2018
Дата публикации29.09.2018
Кол-во символов993
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1360

Оценка читателей: голосов 0 

1. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ М.: ФИЗМАТЛИТ, 2008.
2. Oliver I.M., Smith D.J., Holland J.R.C. A Study of Permutation Crossover Operators on the Traveling Salesman Problem // Proc. 2nd Int. Conf. on Genetic Algorithms. Hillsdale, N.J.: Lawrence Erlbaum Associates, 1987. P. 224–230.
3. Cotta C., Aldana J.F., Nebro A.J., Troya J.M. Hybridizing Genetic Algorithms with Branch and Bound Techniques for the Resolution of the TSP / Artificial Neural Nets and Genetic Algorithm. Pearson D., Steele N., Albrecht R. (Eds.), Wien, N.Y.: Springer-Verlag, 1995. P. 277–280.
4. Goldberg D.E., Lingle R. Alleles, Loci, and the Travelling Salesman Problem // Proc. 1st Int. Conf. on Genetic Algorithms (ICGA’85). Hillsdale, N.J.: Lawrence Erlbaum Associates, 1985. P. 154–159.
5. Сергеев С.И. Задача коммивояжера. Использование нелинейных разрешающих функций // АиТ. 2013. № 6. С. 101–120.
Sergeev S. Nonlinear Resolving Functions for the Travelling Salesman Problem // Autom. Remote Control. 2013. V. 74. No. 6. P. 978–994.
6. Сергеев С.И. Симметричная задача коммивояжера. II // АиТ. 2010. № 4. С. 150–168.
Sergeev S. The Symmetric Travelling Salesman Problem. II // Autom. Remote Control. 2010. V. 71. No. 4. P. 681–696.
7. Chang-Chien Chou. On the Shortest Path Touring n Circles // Int. J. Advancement Comput. Technol. 2012. V. 4. No. 10. P. 356–364.
8. Toriello A. Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem // Math. Programm. 2014. V. 144. No. 1/2. P. 247–264.
9. Хачай М.Ю., Незнахина Е.Д. Приближенные схемы для обобщенной задачи коммивояжера // Тр. ИММ УрО РАН. 2016. No. 22:3. С. 283–292.
10. Хачай М.Ю., Дубинин Р.Д. Аппроксимируемость задачи об оптимальной маршрутизации транспорта в конечномерных евклидовых пространствах // Тр. ИММ УрО РАН. 2016. № 22:2. С. 292–303.
11. Knuth D.E. Estimating the Efficiency of Backtracking Programs // Math. Comput. 1975. V. 29. P. 121–136.
12. Cornu´ejols G., Karamanov M., Li Y. Early Estimates of the Size of Branch-andBound Trees // INFORMS J. Comput. 2006. V. 18. No. 1. P. 86–96.
13. Lobjois L., Lemaitre M. Branch-and-Bound Algorithm Selection by Performance Prediction // Amer. Associat. Artific. Intelligence, Menlo Park, CA, 1998.
14. Purdom P.W. Tree Size by Partial Backtracking // SIAM J. Comput. 1978. V. 7. No. 4. P. 481–491.
15. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An Algorithm for the Traveling Salesman Problem // Oper. Res. 1963. No. 11. P. 972–989.
16. Ulyanov M.V., Fomichev M.I. Resource Characteristics of Ways to Organize a Decision Tree in the Branch-and-Bound Method for the Traveling Salesmen Problem // Бизнес–информатика. 2015. № 4(34). C. 38–46.
17. Головешкин В.А., Жукова Г.Н., Ульянов М.В., Фомичев М.И. Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP // Современ. информ. технологии и ИТ-образование. 2015. Т. 2. № 11. C. 151–159.
18. Крамер Г. Математические методы статистики. М.: Мир, 1975.
19. Pearson K. Contributions to the Mathematical Theory of Evolution. III // Phil. Trans. Royal Soc. London. 1896. V. 187. P. 253–318.
20. Головешкин В.А., Жукова Г.Н., Ульянов М.В., Фомичев М.И. Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа // Современ. информ. технологии и ИТ-образование. 2016. Т. 12. № 3. Ч. 2. C. 131–137.
21. Головешкин В.А. , Жукова Г.Н., Ульянов М.В., Фомичев М.И. Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера // Int. J. Open Inform. Technol. 2016. Т. 4. № 12. C. 7–12.
22. Жукова Г.Н. Идентификация вероятностного распределения по коэффициентам асимметрии и эксцесса // Автоматизация. Современные технологии. 2016. № 5. C. 26–33.
23. Moors J.J.A. A Quantile Alternative for Kurtosis // The Statist. 1988. V. 37. P. 25-32.
24. Moors J.J.A., Coenen V.M.J., Heuts R.M.J. Limiting Distributions of Moment- and Quantile-based Measures for Skewness and Kurtosis // School Econom. Management, Tilburg Univer., Res. Mem. FEW 620, 1993.
25. Moors J.J.A., Wagemakers R.Th.A., Coenen V.M.J., et al. Characterizing Systems of Distributions by Quantile Measures // Statist. Neerlandica, 1996. V. 50. No. 3. P. 417–430.

Система Orphus

Загрузка...
Вверх