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

Кемерово, 29 октября - 2 ноября 2018 г.

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

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

 


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

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

Приводятся результаты статистического исследования сложности асимметричной задачи коммивояжера (ATSP), полученные в результате обработки специально сгенерированного пула матриц (100 000 матриц для каждой размерности от 20 до 49). Построено семейство логнормальных вероятностных распределений, являющееся удовлетворительным приближением распределения сложности. Основная цель исследования — прогноз сложности индивидуальных задач для больших размерностей. В этом аспекте предложено представление распределения сложности, позволяющее решить задачу вероятностного прогнозирования. Формулируется гипотеза об унификации, и указываются направления развития исследований — основное из них — задача непосредственного прогнозирования сложности индивидуальной задачи по исходной матрице стоимостей с полиномиальной трудоемкостью.

 

 



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