Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 48: Строка 48:


Заметим, что граница M была заменена на <math>\ell</math>M в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – <math>\tilde{O}(n^{\omega} r^2 M) \, </math>. Мы предполагаем, что M соответствует <math>O(n^k) \, </math> для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, <math>O(n^3/r) \, </math>, получаем полное время вычисления <math>\tilde{O}(n^{(6 + \omega)/3} M^{1/3}) \, </math> при выборе <math>r = O(n^{(3 - \omega)/3} M^{-1/3}) \, </math>. Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с <math>O(n^{0.624}) \, </math>.
Заметим, что граница M была заменена на <math>\ell</math>M в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – <math>\tilde{O}(n^{\omega} r^2 M) \, </math>. Мы предполагаем, что M соответствует <math>O(n^k) \, </math> для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, <math>O(n^3/r) \, </math>, получаем полное время вычисления <math>\tilde{O}(n^{(6 + \omega)/3} M^{1/3}) \, </math> при выборе <math>r = O(n^{(3 - \omega)/3} M^{-1/3}) \, </math>. Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с <math>O(n^{0.624}) \, </math>.


== Основные результаты ==
== Основные результаты ==


Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с O(n2.688) до O(n2.575) для дуг единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц.
Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с <math>O(n^{2.688}) \, </math> до <math>O(n^{2.575}) \, </math> для дуг единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц.
   
   
В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть (p, q, r) – порядок временной сложности при умножении матриц (np, nq) и (nq, nr). Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за О(n((1,,1)) арифметических операций, где m = n и 0 ≤  ≤ 1. Нам известно следующее: O(n(1,1,1)) = O(n2.376) и O(n(1,0.294,1)) = Õ(n2). Для вычисления произведения квадратных матриц (n, n) требуется n1- операций матричного умножения, что дает время исполнения О(n((1,,1)+1-), которое можно преобразовать в O(n2+), где  удовлетворяет равенству (l,,1) = 2 + 1. На данный момент лучшее известное значение  составляет  = 0.575, так что временная граница превращается в O(n2.575) – это значение уступает O(n2.376). Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц.
В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть (p, q, r) – порядок временной сложности при умножении матриц (np, nq) и (nq, nr). Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за О(n((1,,1)) арифметических операций, где m = n и 0 ≤  ≤ 1. Нам известно следующее: O(n(1,1,1)) = O(n2.376) и O(n(1,0.294,1)) = Õ(n2). Для вычисления произведения квадратных матриц (n, n) требуется n1- операций матричного умножения, что дает время исполнения О(n((1,,1)+1-), которое можно преобразовать в O(n2+), где  удовлетворяет равенству (l,,1) = 2 + 1. На данный момент лучшее известное значение  составляет  = 0.575, так что временная граница превращается в O(n2.575) – это значение уступает O(n2.376). Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц.
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритм_поиска_кратчайших_путей_между_всеми_парами_при_помощи_матричного_произведения