Аннотация:
В работе представлен вероятностный анализ приближенного алгоритма решения задачи о $m$ коммивояжерах на минимум с различными весовыми функциями их маршрутов (гамильтоновых циклов). Временная сложность алгоритма $O(mn^2)$. Предполагается, что элементы матрицы расстояний являются независимыми одинаково распределенными случайными величинами, принимающими значения из неограниченной сверху области $[a_n,\infty)$, $a_n>0$. Анализ проведен на примере усеченно-нормального и показательного распределений. Найдены оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма.
Ключевые слова:задача о нескольких коммивояжерах, приближенный алгоритм, временная сложность, асимптотическая точность, случайные входные данные, функция распределения, усеченно-нормальное, показательное.