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

Статья

ОЦЕНКА ПАРАМЕТРОВ РАСПРЕДЕЛЕНИЯ ЛОГАРИФМА СЛОЖНОСТИ ЗАДАЧИ КОММИВОЯЖЕРА

Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра нормального распределения, аппроксимирующего распределение натурального логарифма сложности, и линейная зависимость параметра позволяют получить оценку снизу для квантилей натурального логарифма сложности уровня 0.95. Проведен экспериментальный анализ качества полученных оценок, показано, что относительное отклонение предполагаемых значений квантилей натурального логарифма сложности уровня 0.95 от выборочных не превышает 0.3% в случае размерности задачи от 45 до 50.