4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 13:35, 23 января 2012
, 23 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 43: | Строка 43: | ||
Такое произведение матриц расстояния называется произведением (n, m)-Романи. Ранее мы имели дело с умножением квадратных матриц, или произведением (n, n)-Романи. В следующем разделе будет рассмотрен случай для m < n. | Такое произведение матриц расстояния называется произведением (n, m)-Романи. Ранее мы имели дело с умножением квадратных матриц, или произведением (n, n)-Романи. В следующем разделе будет рассмотрен случай для m < n. | ||
Матрица С может быть вычислена при помощи <math>O(n^{\omega}) \, </math> арифметических операций на целых числах вплоть до <math>(n + 1)M</math>. Поскольку эти значения можно выразить при помощи O(M log n) бит, а алгоритм Шонхаге и Штрассена [8] для умножения k-битных чисел требует O(k log k log log k) битовых операций, для вычисления C потребуется время O( | Матрица С может быть вычислена при помощи <math>O(n^{\omega}) \, </math> арифметических операций на целых числах вплоть до <math>(n + 1)^M \, </math>. Поскольку эти значения можно выразить при помощи O(M log n) бит, а алгоритм Шонхаге и Штрассена [8] для умножения k-битных чисел требует O(k log k log log k) битовых операций, для вычисления C потребуется время O(<math>n^{\omega}</math> M log n log(M log n) log log(M log n)), или <math>\tilde{O}(Mn^{\omega}) \, </math>. | ||
Первый этап заменяется алгоритмом на основе произведения (n, n)-Романи, а второй этап модифицируется таким образом, чтобы иметь дело с длинами путей, а не расстояниями. | Первый этап заменяется алгоритмом на основе произведения (n, n)-Романи, а второй этап модифицируется таким образом, чтобы иметь дело с длинами путей, а не расстояниями. | ||
Заметим, что граница M была заменена на ℓM в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – Õ(nr2М). Мы предполагаем, что M соответствует O(nk) для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, O(n3/r), получаем полное время вычисления Õ(n(6+)/3М1/3) при выборе r = О{n(3-)/3M-1/3). Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с O(n0.624). | Заметим, что граница M была заменена на ℓM в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – Õ(nr2М). Мы предполагаем, что M соответствует O(nk) для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, O(n3/r), получаем полное время вычисления Õ(n(6+)/3М1/3) при выборе r = О{n(3-)/3M-1/3). Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с O(n0.624). | ||