4431
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 00:09, 19 февраля 2012
, 19 февраля 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с дугами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – <math>O(n^3) \, </math>. Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями дуг. | Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с дугами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – <math>O(n^3) \, </math>. Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями дуг. | ||
Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги (i, j) | |||
Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги <math>(i, j) \in E\, </math> обозначается как <math>d_{ij}\, </math>. Матрица D размера <math>n \times n</math> содержит элемент <math>d_{ij}\, </math> в позиции (i, j). Для простоты предположим, что <math>d_{ij} > 0 \, </math> и <math>d_{ii} = 0 \, </math> для всех <math>i \ne j</math>. Если не существует дуги из i в j, положим <math>d_{ij} = \infty</math>. Стоимость, или расстояние, пути представляет собой сумму стоимостей всех дуг на пути. Длина пути равна количеству дуг на пути. Кратчайшее расстояние между вершинами i и j равняется минимальной стоимости среди всех путей, ведущих от i до j, и обозначается как <math>d_{ij}^*</math>. Пусть <math>D^* = {d_{ij}^*}</math>. Значение n называется размером матрицы. | |||
Пусть A и B – матрицы (n, n). Умножение матриц A и B может производиться одним из трех способов: | Пусть A и B – матрицы (n, n). Умножение матриц A и B может производиться одним из трех способов: | ||
| Строка 18: | Строка 19: | ||
Лучший алгоритм [3] вычисляет произведение (1) за время <math>O(n^ \omega) \, </math>, где <math>\omega \, </math> = 2.376. Далее мы будем учитывать три знака после запятой. Для вычисления произведения (2) булевы значения 0 и 1 в матрицах A и B можно рассматривать как целые числа, применить алгоритм для вычисления (1) и затем заменить ненулевые элементы получившейся матрицы на 1. Следовательно, его сложность также равна <math>O(n^ \omega) \, </math>. ''Свидетели'' произведения (2) задаются матрицей свидетелей <math>W = {w_{ij}} \, </math>, где <math>w_{ij} = k \, </math> для некоторого k, такого, что <math>a_{ik} \wedge b_{kj} = 1</math>. Если такого k не существует, <math>w_{ij} = 0 \, </math>. ''Матрица свидетелей'' <math>W = w_{ij} \, </math> для (3) определяется следующим образом: <math>w_{ij} = k \, </math>, при котором значение <math>c_{ij} \,</math> минимально. Если существует алгоритм для (3) с временем T(n), игнорирующий полилогарифмический коэффициент n, задача поиска кратчайших путей между всеми парами может быть решена за время Õ(T(n)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении <math>D \leftarrow D \times D</math> <math>O(\log n) \,</math> раз. | Лучший алгоритм [3] вычисляет произведение (1) за время <math>O(n^ \omega) \, </math>, где <math>\omega \, </math> = 2.376. Далее мы будем учитывать три знака после запятой. Для вычисления произведения (2) булевы значения 0 и 1 в матрицах A и B можно рассматривать как целые числа, применить алгоритм для вычисления (1) и затем заменить ненулевые элементы получившейся матрицы на 1. Следовательно, его сложность также равна <math>O(n^ \omega) \, </math>. ''Свидетели'' произведения (2) задаются матрицей свидетелей <math>W = {w_{ij}} \, </math>, где <math>w_{ij} = k \, </math> для некоторого k, такого, что <math>a_{ik} \wedge b_{kj} = 1</math>. Если такого k не существует, <math>w_{ij} = 0 \, </math>. ''Матрица свидетелей'' <math>W = w_{ij} \, </math> для (3) определяется следующим образом: <math>w_{ij} = k \, </math>, при котором значение <math>c_{ij} \,</math> минимально. Если существует алгоритм для (3) с временем T(n), игнорирующий полилогарифмический коэффициент n, задача поиска кратчайших путей между всеми парами может быть решена за время Õ(T(n)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении <math>D \leftarrow D \times D</math> <math>O(\log n) \,</math> раз. | ||
Вычисление кратчайших путей будет здесь определяться как нахождение матрицы свидетелей размера n, которой может задаваться кратчайший путь из i в j, за время O(ℓ), где ℓ – длина пути. Говоря более точно, если <math>w_{ij} = k \, </math> в матрице свидетелей <math>W = w_{ij} \, </math>, это означает, что путь из i в j проходит через k. Таким образом, рекурсивная функция path(i,j) задается равной (path(i,k),k, path(k, j)), если <math>w_{ij} = k > 0 \, </math>, и nil в случае <math>w_{ij} = 0 \, </math>, когда путь определяется списком вершин, исключая конечные точки. В дальнейшем изложении k будет записываться в <math>w_{ij} \, </math> в тех случаях, когда будет найден такой элемент k, что путь из i в j модифицируется или задается заново путями из i в k и из k в j. Предшествующие результаты приводятся в качестве схемы получения основных результатов. | Вычисление кратчайших путей будет здесь определяться как нахождение матрицы свидетелей размера n, которой может задаваться кратчайший путь из i в j, за время O(ℓ), где ℓ – длина пути. Говоря более точно, если <math>w_{ij} = k \, </math> в матрице свидетелей <math>W = w_{ij} \, </math>, это означает, что путь из i в j проходит через k. Таким образом, рекурсивная функция path(i,j) задается равной <math>(path(i,k),k, path(k, j))\, </math>, если <math>w_{ij} = k > 0 \, </math>, и <math>nil\, </math> в случае <math>w_{ij} = 0 \, </math>, когда путь определяется списком вершин, исключая конечные точки. В дальнейшем изложении k будет записываться в <math>w_{ij} \, </math> в тех случаях, когда будет найден такой элемент k, что путь из i в j модифицируется или задается заново путями из i в k и из k в j. Предшествующие результаты приводятся в качестве схемы получения основных результатов. | ||
== Алгоритм Алона, Галила и Маргалита == | == Алгоритм Алона, Галила и Маргалита == | ||
