XVIII Всероссийская конференция молодых учёных
по математическому моделированию и информационным технологиям

г. Иркутск, 21–25 августа 2017 г.

Пленарные доклады

На пленарных заседаниях успешные ученые сделают доклады о современных научных результатах и актуальных открытых проблемах.

 


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

Автор: д.т.н., профессор  Михаил Васильевич Ульянов

В докладе приводятся результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные в результате обработки пула, состоящего из 15∙106 несимметричных матриц. Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. На этой основе построено семейство распределений сложности, позволяющее удовлетворительно решить задачу вероятностного прогнозирования. Вводится понятие TSP-сложности матрицы, на основе которого формулируются два направления развития исследований.

 

 

 



 

© 1996-2017, Институт вычислительных технологий СО РАН, Новосибирск