|
Труды Института математики и механики УрО РАН, 2014, том 20, номер 2, страницы 88–98
(Mi timm1061)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху
Э. Х. Гимадиab, А. М. Истоминba, И. А. Рыковab, О. Ю. Цидулкоba a Новосибирский государственный университет
b Институт математики СО РАН
Аннотация:
В работе представлен вероятностный анализ приближенного алгоритма решения задачи о $m$ коммивояжерах на минимум с различными весовыми функциями их маршрутов (гамильтоновых циклов). Временная сложность алгоритма $O(mn^2)$. Предполагается, что элементы матрицы расстояний являются независимыми одинаково распределенными случайными величинами, принимающими значения из неограниченной сверху области $[a_n,\infty)$, $a_n>0$. Анализ проведен на примере усеченно-нормального и показательного распределений. Найдены оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма.
Ключевые слова:
задача о нескольких коммивояжерах, приближенный алгоритм, временная сложность, асимптотическая точность, случайные входные данные, функция распределения, усеченно-нормальное, показательное.
Поступила в редакцию: 30.01.2014
Образец цитирования:
Э. Х. Гимади, А. М. Истомин, И. А. Рыков, О. Ю. Цидулко, “Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху”, Тр. ИММ УрО РАН, 20, № 2, 2014, 88–98; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77–87
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1061 https://www.mathnet.ru/rus/timm/v20/i2/p88
|
Статистика просмотров: |
Страница аннотации: | 345 | PDF полного текста: | 80 | Список литературы: | 57 | Первая страница: | 11 |
|