• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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