RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2014, том 20, номер 2, страницы 88–98 (Mi timm1061)

Эта публикация цитируется в 2 статьях

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

Э. Х. Гимадиab, А. М. Истоминba, И. А. Рыковab, О. Ю. Цидулкоba

a Новосибирский государственный университет
b Институт математики СО РАН

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

Ключевые слова: задача о нескольких коммивояжерах, приближенный алгоритм, временная сложность, асимптотическая точность, случайные входные данные, функция распределения, усеченно-нормальное, показательное.

УДК: 519.16+519.85

Поступила в редакцию: 30.01.2014


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2015, 289, suppl. 1, 77–87

Реферативные базы данных:


© МИАН, 2024