4511
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:13, 23 января 2012
, 23 января 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
Вышеприведенный алгоритм встроен в вычисление произведения (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>. Заметим, что для графа с дугами единичной стоимости эти множества совпадают. | |||
Заметим также, что если (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. | ||
(1) Выберем 9n ln n/ℓ вершин из V случайным образом. В этом случае можно показать, что алгоритм решает задачу нахождения кратчайших путей между всеми парами с высокой вероятностью, т.е. с вероятностью 1 – 1/nc для некоторой константы c > 0; можно показать, что она равна 3. Иными словами, I является сильным ℓ/3—мостовым множеством с высокой вероятностью. Время T в основном определяется произведением (n,m)-Романи. T = Õ(ℓMn((1,r,1)), поскольку элементы матрицы могут иметь величину вплоть до ℓM. Из того, что m = O(n ln n/ℓ) = nr, следует, что ℓ = Õ(n1-r) и, в силу этого, T = O(Mnl-r n((1,r,1)). В случае M = 1 граница на r равна = 0.575, и, следовательно, T = O(n2.575). Если M = nt 1, время оценивается как О(n2+(t)), где t ≤ 3 – = 0.624, а = {t) удовлетворяет равенству (1,,1) = 1 + 2 – t. Это определено из наиболее известного (1,,1) и значения t. Поскольку результат является корректным с высокой вероятностью, этот алгоритм является рандомизированным. | (1) Выберем 9n ln n/ℓ вершин из V случайным образом. В этом случае можно показать, что алгоритм решает задачу нахождения кратчайших путей между всеми парами с высокой вероятностью, т.е. с вероятностью 1 – 1/nc для некоторой константы c > 0; можно показать, что она равна 3. Иными словами, I является сильным ℓ/3—мостовым множеством с высокой вероятностью. Время T в основном определяется произведением (n,m)-Романи. T = Õ(ℓMn((1,r,1)), поскольку элементы матрицы могут иметь величину вплоть до ℓM. Из того, что m = O(n ln n/ℓ) = nr, следует, что ℓ = Õ(n1-r) и, в силу этого, T = O(Mnl-r n((1,r,1)). В случае M = 1 граница на r равна = 0.575, и, следовательно, T = O(n2.575). Если M = nt 1, время оценивается как О(n2+(t)), где t ≤ 3 – = 0.624, а = {t) удовлетворяет равенству (1,,1) = 1 + 2 – t. Это определено из наиболее известного (1,,1) и значения t. Поскольку результат является корректным с высокой вероятностью, этот алгоритм является рандомизированным. | ||