|
Дискретный анализ и исследование операций, 2008, том 15, выпуск 1, страницы 23–43
(Mi da520)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Вероятностный анализ одного алгоритма приближённого решения задачи коммивояжёра на неограниченных сверху входных данных
Э. Х. Гимади, А. Ле Галлу, А. В. Шахшнейдер Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Представлен вероятностный анализ модификации алгоритма “Иди в ближайший непройденный город” для приближённого решения задачи коммивояжёра на минимум. Рассмотрен случай, когда элементы матрицы расстояний являются независимыми одинаково распределёнными случайными величинами, принимающими значения из неограниченной сверху области $[a_n,\infty)$, $a_n>0$, и распределёнными по усечённому нормальному или показательному законам. Обоснованы оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма. Предложенная
модификация алгоритма позволила провести анализ унифицированным образом так, что полученные результаты оказываются справедливыми для задач коммивояжёра как на ориентированных, так и на неориентированных графах. Библ. 8.
Статья поступила: 24.07.2007
Образец цитирования:
Э. Х. Гимади, А. Ле Галлу, А. В. Шахшнейдер, “Вероятностный анализ одного алгоритма приближённого решения задачи коммивояжёра на неограниченных сверху входных данных”, Дискретн. анализ и исслед. опер., 15:1 (2008), 23–43; J. Appl. Industr. Math., 3:2 (2009), 207–221
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da520 https://www.mathnet.ru/rus/da/v15/i1/p23
|
Статистика просмотров: |
Страница аннотации: | 729 | PDF полного текста: | 151 | Список литературы: | 49 | Первая страница: | 12 |
|