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

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