4511
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:44, 17 июля 2014
, 17 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
== Основные результаты == | == Основные результаты == | ||
Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с <math>O(n^{2.688}) \, </math> до <math>O(n^{2.575}) \, </math> для | Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с <math>O(n^{2.688}) \, </math> до <math>O(n^{2.575}) \, </math> для ребер единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц. | ||
В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть <math>\omega(p, q, r) \, </math> – порядок временной сложности при умножении матриц <math>(n^p, n^q) \, </math> и <math>(n^q, n^r) \, </math>. Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за <math>O(n^{\omega (1, \mu, 1)}) \, </math> арифметических операций, где <math>m = n^{\mu} \, </math> и <math>0 \le \mu \le 1 \, </math>. Нам известно следующее: <math>O(n^{\omega( 1, 1, 1)}) = O(n^{2.376}) \, </math> и <math>O(n^{\omega (1, 0.294, 1)}) = \tilde{O}(n^2) \, </math>. Для вычисления произведения квадратных матриц (n, n) требуется <math>n^{1 - \mu} \, </math> операций матричного умножения, что дает время исполнения <math>O(n^{(\omega(1, \mu, 1) + 1 - \mu}) \, </math>, которое можно преобразовать в <math>O(n^{2 + \mu}) \, </math>, где <math>\mu \, </math> удовлетворяет равенству <math>\omega(1, \mu, 1) = 2 \mu + 1 \, </math>. На данный момент лучшее известное значение <math>\mu \, </math> составляет <math>\mu = 0.575 \,</math>, так что временная граница превращается в <math>O(n^{2.575}) \, </math> – это значение уступает <math>O(n^{2.376}) \, </math>. Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц. | В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть <math>\omega(p, q, r) \, </math> – порядок временной сложности при умножении матриц <math>(n^p, n^q) \, </math> и <math>(n^q, n^r) \, </math>. Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за <math>O(n^{\omega (1, \mu, 1)}) \, </math> арифметических операций, где <math>m = n^{\mu} \, </math> и <math>0 \le \mu \le 1 \, </math>. Нам известно следующее: <math>O(n^{\omega( 1, 1, 1)}) = O(n^{2.376}) \, </math> и <math>O(n^{\omega (1, 0.294, 1)}) = \tilde{O}(n^2) \, </math>. Для вычисления произведения квадратных матриц (n, n) требуется <math>n^{1 - \mu} \, </math> операций матричного умножения, что дает время исполнения <math>O(n^{(\omega(1, \mu, 1) + 1 - \mu}) \, </math>, которое можно преобразовать в <math>O(n^{2 + \mu}) \, </math>, где <math>\mu \, </math> удовлетворяет равенству <math>\omega(1, \mu, 1) = 2 \mu + 1 \, </math>. На данный момент лучшее известное значение <math>\mu \, </math> составляет <math>\mu = 0.575 \,</math>, так что временная граница превращается в <math>O(n^{2.575}) \, </math> – это значение уступает <math>O(n^{2.376}) \, </math>. Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц. | ||
| Строка 58: | Строка 58: | ||
Вышеприведенный алгоритм встроен в вычисление произведения (n, m)-Романи при <math>m = n^{\mu} \, </math> и <math>M = n^t \, </math> для некоторого t > 0, а время исполнения составляет <math>\tilde{O}(Mn^{\omega (1, \mu, 1)}) \, </math>. Следующий этап заключается во встраивании произведения (n, m)-Романи в алгоритм нахождения кратчайших путей между всеми парами. Первый алгоритм представляет собой последовательное применение операции возведения в квадрат, напоминающее второй этап алгоритма в [1]. Чтобы с пользой применить алгоритм произведения прямоугольных матриц (n, m)-Романи, нам потребуется определение мостового множества, которое будет играть ту же роль, что и множество I в алгоритме частичного вычисления матричного произведения в разделе «Постановка задачи». | Вышеприведенный алгоритм встроен в вычисление произведения (n, m)-Романи при <math>m = n^{\mu} \, </math> и <math>M = n^t \, </math> для некоторого t > 0, а время исполнения составляет <math>\tilde{O}(Mn^{\omega (1, \mu, 1)}) \, </math>. Следующий этап заключается во встраивании произведения (n, m)-Романи в алгоритм нахождения кратчайших путей между всеми парами. Первый алгоритм представляет собой последовательное применение операции возведения в квадрат, напоминающее второй этап алгоритма в [1]. Чтобы с пользой применить алгоритм произведения прямоугольных матриц (n, m)-Романи, нам потребуется определение мостового множества, которое будет играть ту же роль, что и множество I в алгоритме частичного вычисления матричного произведения в разделе «Постановка задачи». | ||
Обозначим за <math>\delta(i,j) \, </math> кратчайшее расстояние между i и j, а за <math>n(i,j) \, </math> – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является <math>\ell</math>-мостовым множеством, если удовлетворяет следующему условию: если <math>\eta(i,j) \ge \ell</math>, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math>. I является сильным <math>\ell</math>-мостовым множеством при выполнении условия: если <math>\eta(i,j) \ge \ell \, </math>, то существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\eta(i,j) = \eta(i,k) + \eta(k,j) \, </math>. Заметим, что для графа с | Обозначим за <math>\delta(i,j) \, </math> кратчайшее расстояние между i и j, а за <math>n(i,j) \, </math> – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является <math>\ell</math>-мостовым множеством, если удовлетворяет следующему условию: если <math>\eta(i,j) \ge \ell</math>, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math>. I является сильным <math>\ell</math>-мостовым множеством при выполнении условия: если <math>\eta(i,j) \ge \ell \, </math>, то существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\eta(i,j) = \eta(i,k) + \eta(k,j) \, </math>. Заметим, что для графа с ребрами единичной стоимости эти множества совпадают. | ||
Заметим также, что если <math>(2/3) \ell \le \mu(i,j) \le \ell \,</math> и I является сильным <math>\ell/3</math>-мостовым множеством, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\mu(i,j) = \mu(i, k) + \mu(k,j) \,</math>. Если выполняется свойство сильного мостового множества, произведение (n, m)-Романи может быть использовано для решения задачи нахождения кратчайших путей между всеми парами следующим образом. Последовательным применением возведения в квадрат, как в случае алгоритма Алона-Галила-Маргалита, алгоритм вычисляет <math>D^{(\ell)} \, </math> для <math>\ell = 1, \mathcal{d} 3/2 \mathcal{e}, \mathcal{d} 3/2 \mathcal{d} 3/2 \mathcal{e} \mathcal{e}, ... , n' \, </math> (где n' – первое значение <math>\ell</math>, превышающее n), используя различные варианты множества I, описанного ниже. Для вычисления мостового множества алгоритм поддерживает матрицу свидетелей с дополнительным полилогарифмическим коэффициентом в оценке сложности. В источнике [10] предложены три способа выбора множества I. Пусть <math>|I| = n^r \, </math> для некоторого r, <math>0 \le r \le 1</math>. | Заметим также, что если <math>(2/3) \ell \le \mu(i,j) \le \ell \,</math> и I является сильным <math>\ell/3</math>-мостовым множеством, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\mu(i,j) = \mu(i, k) + \mu(k,j) \,</math>. Если выполняется свойство сильного мостового множества, произведение (n, m)-Романи может быть использовано для решения задачи нахождения кратчайших путей между всеми парами следующим образом. Последовательным применением возведения в квадрат, как в случае алгоритма Алона-Галила-Маргалита, алгоритм вычисляет <math>D^{(\ell)} \, </math> для <math>\ell = 1, \mathcal{d} 3/2 \mathcal{e}, \mathcal{d} 3/2 \mathcal{d} 3/2 \mathcal{e} \mathcal{e}, ... , n' \, </math> (где n' – первое значение <math>\ell</math>, превышающее n), используя различные варианты множества I, описанного ниже. Для вычисления мостового множества алгоритм поддерживает матрицу свидетелей с дополнительным полилогарифмическим коэффициентом в оценке сложности. В источнике [10] предложены три способа выбора множества I. Пусть <math>|I| = n^r \, </math> для некоторого r, <math>0 \le r \le 1</math>. | ||
| Строка 64: | Строка 64: | ||
(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) Рассмотрим случай с единичными стоимостями | (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) Если стоимости | (3) Если стоимости ребер положительны и ограничены <math>M = n^t > 0 \, </math>, сходная процедура может быть использована для вычисления <math>O(\ell)</math>-мостового множества размера O(n ln n/ℓ) за время <math>\tilde{O}(\ell n^2)</math>. Используя мостовое множество, задачу нахождения кратчайших путей между всеми парами вершин можно решить за время <math>\tilde{O}(n^{2 + \mu (t)}) \, </math> способом, сходным с вариантом (1). Этот результат можно обобщить на случай, когда стоимости ребер находятся в диапазоне от -M до M, сохранив ту же временную сложность, если модифицировать процедуру для вычисления <math>\ell</math>-мостового множества в случае, если не имеется отрицательных контуров. Подробности изложены в [10]. | ||
== Применение == | == Применение == | ||
