Вероятностный анализ одного алгоритма приближённого решения задачи коммивояжёра на неограниченных сверху входных данных

Представлен вероятностный анализ модификации алгоритма “Иди в ближайший непройденный город” для приближённого решения задачи коммивояжёра на минимум. Рассмотрен случай, когда элементы матрицы расстояний являются независимыми одинаково распределёнными случайными величинами, принимающими значения из неограниченной сверху области $[a_n,\infty)$, $a_n>0$, и распределёнными по усечённому нормальному или показательному законам. Обоснованы оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма. Предложенная модификация алгоритма позволила провести анализ унифицированным образом так, что полученные результаты оказываются справедливыми для задач коммивояжёра как на ориентированных, так и на неориентированных графах. Библ. 8.