4430
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 18:30, 23 января 2012
, 23 января 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
(1) Выберем 9n ln n/ℓ вершин из V случайным образом. В этом случае можно показать, что алгоритм решает задачу нахождения кратчайших путей между всеми парами с высокой вероятностью, т.е. с вероятностью 1 - <math>1/n^c</math> для некоторой константы c > 0; можно показать, что она равна 3. Иными словами, I является сильным <math>\ell/3</math>—мостовым множеством с высокой вероятностью. Время T в основном определяется произведением (n,m)-Романи. <math>T = \tilde{O}( \ell Mn^{(\omega (1, r, 1)})</math>, поскольку элементы матрицы могут иметь величину вплоть до <math>\ell M</math>. Из того, что m = O(n ln n/ℓ) = <math>n^r</math>, следует, что <math>\ell = \tilde{O}(n^{1 - r})</math> и, в силу этого, <math>T = O(Mn^{l - r} n^{\omega (1, r, 1)}) \, </math>. В случае M = 1 граница значения r равна <math>\mu</math> = 0.575, и, следовательно, <math>T = O(n^{2.575}) \, </math>. Если <math>M = n^t \ge 1 \, </math>, время оценивается как <math>О(n^{2 + \mu (t)}) \, </math>, где <math>t \le 3 - \omega = 0.624 \, </math>, а <math>\mu = \mu (t) \, </math> удовлетворяет равенству <math>\omega (1, \mu , 1) = 1 + 2 \mu - t \, </math>. Это определено из наиболее известного <math>\omega(1, \mu, 1) \,</math> и значения t. Поскольку результат является корректным с высокой вероятностью, этот алгоритм является рандомизированным. | (1) Выберем 9n ln n/ℓ вершин из V случайным образом. В этом случае можно показать, что алгоритм решает задачу нахождения кратчайших путей между всеми парами с высокой вероятностью, т.е. с вероятностью 1 - <math>1/n^c</math> для некоторой константы c > 0; можно показать, что она равна 3. Иными словами, I является сильным <math>\ell/3</math>—мостовым множеством с высокой вероятностью. Время T в основном определяется произведением (n,m)-Романи. <math>T = \tilde{O}( \ell Mn^{(\omega (1, r, 1)})</math>, поскольку элементы матрицы могут иметь величину вплоть до <math>\ell M</math>. Из того, что m = O(n ln n/ℓ) = <math>n^r</math>, следует, что <math>\ell = \tilde{O}(n^{1 - r})</math> и, в силу этого, <math>T = O(Mn^{l - r} n^{\omega (1, r, 1)}) \, </math>. В случае M = 1 граница значения r равна <math>\mu</math> = 0.575, и, следовательно, <math>T = O(n^{2.575}) \, </math>. Если <math>M = n^t \ge 1 \, </math>, время оценивается как <math>О(n^{2 + \mu (t)}) \, </math>, где <math>t \le 3 - \omega = 0.624 \, </math>, а <math>\mu = \mu (t) \, </math> удовлетворяет равенству <math>\omega (1, \mu , 1) = 1 + 2 \mu - t \, </math>. Это определено из наиболее известного <math>\omega(1, \mu, 1) \,</math> и значения t. Поскольку результат является корректным с высокой вероятностью, этот алгоритм является рандомизированным. | ||
(2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в <math>\tilde{O} </math>-нотации. Более конкретно, I выбирается в качестве <math>\ell / 3</math>-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как O( | (2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в <math>\tilde{O} </math>-нотации. Более конкретно, I выбирается в качестве <math>\ell / 3</math>-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как <math>O(\ell)</math>-мостовое множество, необходимо получить вершины кратчайшего пути из i в j для каждого i и j, используя матрицу свидетелей W, за время <math>O(\ell)</math>. После получения этих <math>n^2 \,</math> множеств за время <math>O(\ell n^2)</math> можно вычислить <math>O(\ell)</math>-мостовое множество размера O(n ln n/ℓ) с той же временной сложностью, как показано в [10]. Процесс вычисления мостового множества должен остановиться в <math>\ell = n^{1/2} \, </math>, поскольку после этой границы процесс становится чрезмерно дорогим; в силу этого после данной границы используется одно и то же мостовое множество. Время вычисления до этой границы остается тем же, что и в варианте (1), а после границы составляет <math>\tilde{O}(n^{2.5}) \, </math>. Таким образом, мы получаем алгоритм из двух этапов. | ||
(3) Если стоимости дуг положительны и ограничены M = nt > 0, сходная процедура может быть использована для вычисления O(ℓ)-мостового множества размера O(n ln n/ℓ) за время | |||
(3) Если стоимости дуг положительны и ограничены M = nt > 0, сходная процедура может быть использована для вычисления O(ℓ)-мостового множества размера O(n ln n/ℓ) за время \tilde{O}{ℓn2). Используя мостовое множество, задачу нахождения кратчайших путей между всеми парами вершин можно решить за время \tilde{O}(M2+(t)) способом, сходным с вариантом (1). Этот результат можно обобщить на случай, когда стоимости дуг находятся в диапазоне от -M до M, сохранив ту же временную сложность, если модифицировать процедуру для вычисления ℓ-мостового множества в случае, если не имеется отрицательных контуров. Подробности изложены в [10]. | |||
Применение | Применение | ||
