Том 15, номер 1, 2008 г., Стр. 23-43

УДК 519.8
Э. Х. Гимади, А. Ле Галлу, А. В. Шахшнейдер
Вероятностный анализ одного алгоритма приближённого решения задачи коммивояжёра на неограниченных сверху входных данных

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

Э. Х. Гимади ¹
А. Ле Галлу ¹
А. В. Шахшнейдер ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru

Статья поступила 24 июля 2007 г.