4511
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:07, 23 января 2012
, 23 января 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [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>. Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц. | ||
Вышеприведенный алгоритм встроен в вычисление произведения (n, m)-Романи при m = | Вышеприведенный алгоритм встроен в вычисление произведения (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 в алгоритме частичного вычисления матричного произведения в разделе «Постановка задачи». | ||
Обозначим за (i,j) кратчайшее расстояние между i и j, а за n{i,j) – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является ℓ-мостовым множеством, если удовлетворяет следующему условию: если (i,j) ℓ, существует k I, такое, что (i,j) = (i,k) + (k,j). I является сильным ℓ-мостовым множеством при выполнении условия: если (i,j) ℓ, существует k I, такое, что (i,j) = (i, k) + (k,j) и (i, j) = (i, k) + (k, j). Заметим, что для графа с дугами единичной стоимости эти множества совпадают. | Обозначим за (i,j) кратчайшее расстояние между i и j, а за n{i,j) – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является ℓ-мостовым множеством, если удовлетворяет следующему условию: если (i,j) ℓ, существует k I, такое, что (i,j) = (i,k) + (k,j). I является сильным ℓ-мостовым множеством при выполнении условия: если (i,j) ℓ, существует k I, такое, что (i,j) = (i, k) + (k,j) и (i, j) = (i, k) + (k, j). Заметим, что для графа с дугами единичной стоимости эти множества совпадают. | ||
Заметим также, что если (2/3) ℓ ≤(i,j) ≤ ℓ и I является сильным ℓ/3-мостовым множеством, существует k I, такое, что (i, j) = (i, k) + (k,j) и (i,j) = (i, k) + (k,j). Если выполняется свойство сильного мостового множества, произведение (n, m)-Романи может быть использовано для решения задачи нахождения кратчайших путей между всеми парами следующим образом. Последовательным применением возведения в квадрат, как в случае алгоритма Алона-Галила-Маргалита, алгоритм вычисляет D(ℓ) для ℓ = 1, 3/2 r, 3/2 3/2 r, ... , n' (где n' – первое значение ℓ, превышающее n), используя различные варианты множества I, описанного ниже. Для вычисления мостового множества алгоритм поддерживает матрицу свидетелей с дополнительным полилогарифмическим коэффициентом в оценке сложности. В источнике [10] предложены три способа выбора множества I. Пусть |I| = nr для некоторого r, 0 ≤ r ≤ 1. | Заметим также, что если (2/3) ℓ ≤(i,j) ≤ ℓ и I является сильным ℓ/3-мостовым множеством, существует k I, такое, что (i, j) = (i, k) + (k,j) и (i,j) = (i, k) + (k,j). Если выполняется свойство сильного мостового множества, произведение (n, m)-Романи может быть использовано для решения задачи нахождения кратчайших путей между всеми парами следующим образом. Последовательным применением возведения в квадрат, как в случае алгоритма Алона-Галила-Маргалита, алгоритм вычисляет D(ℓ) для ℓ = 1, 3/2 r, 3/2 3/2 r, ... , n' (где n' – первое значение ℓ, превышающее n), используя различные варианты множества I, описанного ниже. Для вычисления мостового множества алгоритм поддерживает матрицу свидетелей с дополнительным полилогарифмическим коэффициентом в оценке сложности. В источнике [10] предложены три способа выбора множества I. Пусть |I| = nr для некоторого r, 0 ≤ r ≤ 1. | ||