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

Статья

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

International Journal of Open Information Technologies. 2016. Т. 4. № 12. С. 7-12.

Исследуется сложность индивидуальных задач коммивояжера, т.е. число порожденных вершин поискового дерева в классическом методе ветвей и границ. Вероятностное распределение логарифма сложности аппроксимируется нормальным распределением. На основе экспериментальных данных рассчитаны значения параметров линейного преобразования, обеспечивающих минимальное среднеквадратическое отклонение выборочных квантилей логарифма сложности от соответствующих квантилей стандартного нормального распределения, получена формула зависимости этих параметров от числа вершин графа.