ОЦЕНКА ПАРАМЕТРОВ РАСПРЕДЕЛЕНИЯ ЛОГАРИФМА СЛОЖНОСТИ ЗАДАЧИ КОММИВОЯЖЕРА - Головешкин, Василий Адамович; Жукова, Галина Николаевна; Ульянов, Михаил Васильевич; Фомичев, Михаил Игоревич (Современные информационные технологии и ИТ-образование; Том 13 № 1 (2017): Современные информационные технологии и ИТ-образованиеDO - 10.25559/SITITO.2017.1.405, 2017)
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра масштаба  нормального распределения, аппроксимирующего распределение натурального логарифма сложности, и линейная зависимость параметра сдвига позволяют получить оценку снизу для квантилей натурального логарифма сложности уровня 0.95. Проведен экспериментальный анализ качества полученных оценок, показано, что относительное отклонение предполагаемых значений квантилей натурального логарифма сложности уровня 0.95 от выборочных не превышает 0.3%  в случае размерности задачи от 45 до 50.