На перевод: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Показать все непроверенные изменения)
[непроверенная версия][выверенная версия]
(Новая страница: «= Прямая подстановка (вещественный вариант) = == Программная реализация == === Особенности…»)
 
Строка 1: Строка 1:
−
= Прямая подстановка (вещественный вариант) =
+
= Поиск кратчайшего пути от одной вершины (SSSP) =
 +
== Постановка задачи ==
  
−
== Программная реализация ==
+
Пусть задан граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math> и выделенной вершиной-источником <math>u</math>. Последовательность <math>P(u, v)</math> рёбер <math>e_1 = (u, w_1)</math>, <math>e_2 = (w_1, w_2)</math>, …, <math>e_k = (w_{k-1}, v)</math> называется ''путём'', идущим от вершины <math>u</math> к вершине <math>v</math>. Суммарный вес этого пути равен
  
−
=== Особенности реализации последовательного алгоритма ===
+
:<math>
 +
f(P(u, v)) = \sum_{i = 1}^k f(e_i).
 +
</math>
 +
 +
Требуется для каждой вершины <math>v</math>, достижимой из вершины-источника <math>u</math>, указать путь <math>P^*(u, v)</math>, имеющий наименьший возможный суммарный вес:
  
−
В простейшем варианте метод прямой подстановки на Фортране можно записать так:
+
:<math>
 +
f^*(v) = f(P^*(u, v)) = \min f(P(u, v)).
 +
</math>
  
−
<source lang="fortran">
+
Название задачи на английском языке – «Single Source Shortest Path» (SSSP).
−
        Y(1) = B(1)
 
−
DO  I = 2, N-1
 
−
S = B(I)
 
−
DO  J = 1, I-1
 
−
S = S - DPROD(L(I,J), Y(J))
 
−
END DO
 
−
END DO
 
−
</source>
 
−
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.
 
  
−
=== Описание локальности данных и вычислений ===
+
== Варианты задачи ==
−
==== Описание локальности реализации алгоритма ====
 
−
===== Описание структуры обращений в память и качественная оценка локальности =====
 
  
−
[[file:gauss forward 1.PNG|thumb|center|700px|Рисунок 12.1. Прямой ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]]
+
Если требуется найти кратчайшие пути не от одной, а от всех вершин - см. [[Поиск кратчайшего пути для всех пар вершин (APSP)|поиск кратчайшего пути для всех пар вершин]].
  
−
На рисунке 12.1 представлен профиль обращений в память для прямого хода метода Гаусса решения СЛАУ. Из исходного кода, как и из рисунка, видно, что в программе задействовано 2 основных массива: профиль обращений к элементам первого выделен зеленым (фрагмент 1); все остальные обращения происходят к элементам второго массива. Видно, что общий профиль всей программы устроен достаточно сложно. Основное, что можно заметить из данного рисунка, – это итерационная природа профиля, причем каждая следующая итерация содержит меньше обращений. Это особенно хорошо видно по фрагменту  1.  
+
Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.
  
−
Далее, как известно, в прямом ходе Гаусса на каждой итерации отбрасывается из рассмотрения одна из строк СЛАУ. Это отчетливо видно и на рис. 12.1: на каждой итерации (одна из них выделена как фрагмент 2) выполняется серия обращений, связанных с отбрасываемой строкой (фрагмент 3), после чего обращения к этим элементам больше не выполняются. Также можно заметить, что фрагменты, подобные фрагменту 3, на каждой последующей итерации становятся все меньше, как по числу обращений, так и по числу элементов, к которым происходят обращения.
+
В зависимости от ограничений на возможные значения весов различают следующие случаи.
  
−
Однако на основе подобной общей картины очень сложно дать даже качественные оценки локальности. Перейдем к более подробному рассмотрению фрагмента 1, соответствующего обращениям к одному из двух массивов.
+
* '''Единичные веса'''. В этом случае задача существенно упрощается и может быть решена за линейное время [[Поиск в ширину (BFS)|алгоритмом поиска вширь]].
 +
* '''Положительные целые веса'''. Задача также может быть решена за линейное время<ref name=thorup>Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.</ref> (хотя и с большей константой).
 +
* '''Неотрицательные веса'''. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
 +
* '''Произвольные веса'''. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.
  
−
[[file:gauss forward 2.PNG|thumb|center|500px|Рисунок 12.2. Фрагмент 1 (профиль обращений к первому массиву)]]
+
== Свойства задачи ==
  
−
На рис. 12.2 показан отдельно фрагмент 1, выделенный на рис. 12.1 зеленым. Наблюдается довольно интересная картина: исходя из рис. 12.1, складывалось впечатление, что данный профиль образуется чередованием итераций двух разных циклов, причем итерация первого цикла заметно короче итераций второго цикла. На самом же деле, из рис. 12.2 можно увидеть, что профиль состоит из однотипных итераций, в рамках которых производится последовательный перебор элементов массива. При этом на каждой следующей итерации отбрасывается элемент с минимальным индексом. Иллюзия наличия двух разных циклов обусловлена исключительно числом обращений к другому массиву – когда число таких обращений велико, итерация данного фрагмента кажется длиннее. При этом во фрагменте 1 (как видно на рис. 12.2) число обращений всего лишь около 1200, тогда как весь профиль обращений состоит из 34 тысяч. То есть на долю обращений к первому массиву приходится всего 3.5% всех обращений в программе.
+
Решение задачи удовлетворяет принципу оптимальности: если путь <math>P^*(u, w)</math> является частью кратчайшего пути <math>P^*(u, v)</math>, то <math>P^*(u, w)</math> является кратчайшим путём от источника <math>u</math> до вершины <math>w</math>.
  
−
Поскольку основа данного профиля – последовательный перебор элементов массива, можно сказать, что данный фрагмент обладает высокой пространственной локальностью. А поскольку итераций с перебором элементов достаточно много, также видно, что и временна́я локальность достаточно высока.
+
Принцип оптимальности означает, что для каждой вершины <math>v</math> вместо всего кратчайшего пути <math>P^*(u, v)</math> достаточно хранить его последнее ребро <math>e^*_v</math>. Отсюда следует оценка объёма памяти <math>O(m)</math>.
  
−
Теперь перейдем к рассмотрению профиля обращений ко второму массиву, который значительно больше и сложнее первого профиля. На рис. 12.3 отдельно представлен фрагмент 2, выделенный на рис. 12.1. Такой фрагмент устроен из четырех частей, отмеченных на рисунке оранжевым.
+
== Описание входных и выходных данных ==
  
−
[[file:gauss forward 3.PNG|thumb|center|700px|Рисунок 12.3. Фрагмент 2 (итерация профиля обращений ко второму массиву)]]
+
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.
  
−
Часть 1 очень похожа на повторяющийся последовательный перебор одного и того же небольшого числа элементов в цикле. При более близком рассмотрении можно убедиться, что это действительно так. На рис. 12.4 показано приближение фрагмента 2, выделенное на рис. 12.3 синим цветом. Также на этом рисунке видно, что часть 2 представляет собой практически полное подобие последовательного перебора всех элементов данного массива. Таким образом, обе эти части обладают высокой пространственной локальностью (из-за последовательного перебора). При этом часть 1 обладает также высокой временной локальностью, поскольку перебор повторяется в цикле, в отличие от части 2, где к каждому элементу выполняется только одно обращение.
+
'''Объём входных данных''': <math>O(m + n)</math>.
  
−
Часть 3 состоит всего из нескольких обращений и представляет собой перебор всех элементов массива, выполненных с достаточно большим шагом, гораздо большим, чем в части 2. В данном случае, из-за достаточно большого шага,  наблюдается невысокая пространственная локальность и отсутствие временно́й локальности, так как перебор выполняется единожды.
+
'''Выходные данные''' (возможные варианты):
 +
# для каждой вершины <math>v</math> исходного графа – последнее ребро <math>e^*_v = (w, v)</math>, лежащее на кратчайшем пути от вершины <math>u</math> к <math>v</math>, или соответствующая вершина <math>w</math>;
 +
# для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.
 +
 +
'''Объём выходных данных''': <math>O(n)</math>.
  
−
Часть 4 представляет собой последовательный перебор части массива, по размеру соответствующей числу отброшенных из рассмотрения элементов; чем ближе к концу профиля, тем больше обращений расположено в части 4. Эта часть обладает теми же свойствами локальности, что и часть 2. Отличие заключается в числе обращений, однако в данном случае это не оказывает сильное влияние на локальность.
+
=== Преобразование выходных данных и поиск кратчайшего пути ===
  
−
При рассмотрении фрагмента 2 в целом основное влияние оказывают части 1 и 2, поэтому можно утверждать, что это фрагмент обладает достаточно высокой и пространственной, и временно́й локальностью. Однако на последующих итерациях (см. рис. 12.1) локальность в целом будет постепенно снижаться, поскольку на каждой итерации отбрасывается из рассмотрения некоторая часть элементов.
+
Кратчайший путь от <math>u</math> к <math>v</math> может быть восстановлен за время <math>O(\left |P^*(u, v) \right |)</math>, если, начиная с вершины <math>v</math>, проходить рёбра <math>e^*_w</math> в обратном направлении до тех пор, пока не будет посещена вершина <math>u</math>.
  
−
[[file:gauss forward 4.PNG|thumb|center|500px|Рисунок 12.4. Приближение фрагмента 2]]
+
Рёбра <math>e^*_v</math> могут быть восстановлены за время <math>O(m)</math> перебором рёбер для каждой вершины:
 +
:<math>
 +
    e^*_v \in \{ (w, v) \in E \mid f^*(v) = f^*(w) + f((v, w)) \}.
 +
</math>
 +
Перебор может осуществляться параллельно.
  
−
===== Количественная оценка локальности =====
+
Для поиска кратчайших расстояний <math>f^*(v)</math> по набору рёбер <math>e^*_v</math>, необходимо построить из них дерево, на котором выполнить [[Поиск в ширину (BFS)|поиск в ширину]] за время <math>O(m)</math> (с возможностью параллелизации).
  
−
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/gauss_forward/gauss_forward.h здесь] (функция Kernel1). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
+
== Алгоритмы решения задачи ==
  
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
+
* '''[[Поиск в ширину (BFS)]]''' для ориентированных невзвешенных графов, сложность <math>O(m)</math>.
 +
* '''[[Алгоритм Дейкстры]]'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref><ref>Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.</ref> для ориентированных графов с неотрицательными весами, сложность <math>O(m + n \ln n)</math>.
 +
* '''[[Алгоритм Беллмана-Форда]]'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> для ориентированных графов с произвольными весами, сложность <math>O(mn)</math>.
 +
* '''[[Алгоритм Δ-шагания]]'''<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами <math>O(n + m + dL)</math>, параллельная сложность <math>O((dL + \ln n) \ln n</math> со средней работой <math>O(n + m + dL \ln n)</math>.
 +
* '''Алгоритм Торупа'''<ref name=thorup /> представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время <math>O(m)</math>.
 +
* В ориентированном ациклическом графе с произвольными весами время поиска кратчайших путей линейное – <math>O(m + n)</math>, алгоритм основан на топологической сортировке графа.
  
−
На рисунке 12.5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что отмеченный синий столбец, соответствующий прямому ходу метода Гаусса, расположен в правой части и показывает достаточно высокую производительность, немного ниже производительности теста Линпак. Также отметим, что значение daps для данной задачи практически совпадает со значением daps для всего метода Гаусса (столбец «gauss»), объединяющего как прямой, так и обратный ход. Это связано с тем, что обратный ход состоит из гораздо меньшего числа обращений, нежели прямой ход, поэтому оказывает меньшее влияние.
+
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>d</math> – максимальная степень вершины, <math>L</math> – максимальный суммарный вес кратчайшего пути.
  
−
[[file:gauss forward daps ru.PNG|thumb|center|700px|Рисунок 12.5. Сравнение значений оценки daps]]
+
Перечисленные алгоритмы могут использоваться и для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска кратчайшего пути для всех пар вершин графа]] (для этого необходимо запустить соответствующий алгоритм для каждой вершины графа, что при необходимости можно сделать параллельно), при этом оценка сложности умножается на <math>n</math>.
  
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
  
−
На рисунке 12.6 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, как и в случае с оценкой daps, прямой ход метода Гаусса обладает высокой локальностью. Причем согласно данной оценке тест Линпак показывает практически те же результаты. Отметим, что снова значение оценки для отдельно прямого хода и совокупности прямого и обратного ходов (столбец «gauss») совпадают.
+
= Поиск кратчайшего пути для всех пар вершин (APSP) =
  
−
[[file:gauss forward cvg.PNG|thumb|center|700px|Рисунок 12.6. Сравнение значений оценки cvg]]
+
== Постановка задачи ==
  
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
Пусть задан граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>, <math>e \in E</math>. Последовательность <math>P(u, v)</math> рёбер <math>e_1 = (u, w_1)</math>, <math>e_2 = (w_1, w_2)</math>, …, <math>e_k = (w_{k-1}, v)</math> называется ''путём'', идущим от вершины <math>u</math> к вершине <math>v</math>. Вершина <math>v</math> называется ''достижимой'' из вершины <math>u</math>, если существует хотя бы один путь <math>P(u, v)</math>. Суммарный вес этого пути равен
−
=== Масштабируемость алгоритма и его реализации ===
 
−
==== Описание масштабируемости алгоритма ====
 
−
==== Описание масштабируемости реализации алгоритма ====
 
−
[[file:Масштабируемость параллельной реализации метода Гаусса Производительность.png|thumb|center|700px|Рисунок 1. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная производительность. ]]
 
−
[[file:Масштабируемость метод Гаусса.png|thumb|center|700px|Рисунок 2. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная эффективность. ]]
 
−
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 
−
* число процессоров [4 : 256]
 
−
* размер матрицы [1024 : 5120]
 
−
Эффективность выполнения реализации алгоритма
 
−
* Минимальная эффективность 0,11 %
 
−
* Максимальная эффективность 6.65%
 
−
Оценка масштабируемости
 
−
* По числу процессов: -0.000101 – при увеличении числа процессов эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Учитывая разницу между максимальным и минимальным значением эффективности в 6,5% можно сделать вывод, что на рассмотренной области снижение эффективности, скорее всего, достаточно равномерное. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Могут присутствовать области возрастания эффективности, на всех рассмотренных размерах матрицы. Это может объясняться увеличением вычислительной сложности задачи, что при постоянных накладных расходах на организацию параллельного взаимодействия приводит к общему увеличению эффективности работы.
 
−
* По размеру задачи:-0.00674– при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это может свидетельствовать о том, что при увеличении размера задачи возрастают и накладные расходы на организацию параллельного взаимодействия. Так как интенсивность снижения эффективности по этому направлению выше, чем по направлению числа процессов, скорее всего падение интенсивности значительно при малом числе процессов более интенсивное, чем в присутствующих областях возрастания эффективности при большом числе процессов.
 
−
* По двум направлениям: -6.621e-05 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности очень мала. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 6,5 % говорит о том, что если на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.
 
  
−
[http://git.algowiki-project.org/Teplov/Scalability/blob/master/Gauss_elimination/Gauss_ACES.c Исследованная параллельная реализация на языке C]
+
:<math>
 +
f(P(u, v)) = \sum_{i = 1}^k f(e_i).
 +
</math>
 +
 +
Требуется для каждой пары вершины <math>(u, v)</math>, для которой вершина <math>v</math> достижима из вершины <math>u</math>, указать путь <math>P^*(u, v)</math>, имеющий наименьший возможный суммарный вес:
  
−
= Перемножение плотных неособенных матриц (последовательный вещественный вариант) =
+
:<math>
 +
f^*(u, v) = f(P^*(u, v)) = \min f(P(u, v)).
 +
</math>
 +
 +
Название задачи на английском языке – «All Pairs Shortest Path» (APSP).
  
−
== Программная реализация ==
+
== Варианты задачи ==
  
−
=== Особенности реализации последовательного алгоритма ===
+
Если требуется найти кратчайшие пути лишь от одной, а не от всех вершин – см. [[Поиск кратчайшего пути от одной вершины (SSSP)|поиск кратчайшего пути от одной вершины]].
  
−
В простейшем варианте алгоритм умножения матриц на Фортране можно записать так:
+
Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.
  
−
<source lang="fortran">
+
В зависимости от ограничений на возможные значения весов различают следующие случаи.
−
       
 
−
DO  I = 1, M
 
−
        DO  J = 1, L
 
−
S = 0.
 
−
DO  K = 1, N
 
−
S = S + DPROD(A(I,K), B(K,J))
 
−
END DO
 
−
        C(I, J) = S
 
−
        END DO
 
−
END DO
 
−
</source>
 
−
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.
 
  
−
=== Описание локальности данных и вычислений ===
+
* '''Единичные веса'''. В этом случае задача существенно упрощается и может быть решена за квадратичное время [[Поиск в ширину (BFS)|алгоритмом поиска вширь]].
−
==== Описание локальности реализации алгоритма ====
+
* '''Положительные целые веса'''. Задача также может быть решена за квадратичное время<ref name=thorup>Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.</ref> (хотя и с большей константой).
−
===== Описание структуры обращений в память и качественная оценка локальности =====
+
* '''Неотрицательные веса'''. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
 +
* '''Произвольные веса'''. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.
  
−
[[file:matrmult 1.PNG|thumb|center|700px|Рисунок 12.1. Профили обращений для 6 вариантов перемножения матриц]]
+
В зависимости от способа организации вычислений возможны следующие варианты:
  
−
На рисунке 12.1 представлены 6 профилей обращений для различных вариантов классического перемножения матриц (в зависимости от выбранного порядка циклов). На каждом профиле хорошо выделяются фрагменты профилей для 3-х массивов, используемых в программе. При этом порядок обращений к разным массивам во всех 6 вариантах один и тот же; т.е. взаимодействие между  массивами везде устроен одинаково. В этом случае отличия в локальности задаются внутренним строением фрагментов профиля для каждого массива в отдельности.
+
* статический граф, полное вычисление всех кратчайших путей (классический подход);
 +
* вычисление онлайн<ref>Djidjev, Hristo N, Grammati E Pantziou, and Christos D Zaroliagis. “On-Line and Dynamic Algorithms for Shortest Path Problems.” In Proceedings of STACS 95, 193–204. Lecture Notes in Computer Science Vol. 900, Berlin, Heidelberg: Springer, 1995. doi:10.1007/3-540-59042-0_73.</ref>: производятся предварительные вычисления, далее путь между парой вершин вычисляется по запросу (такой подход уместен, если в реальности потребуется вычислить кратчайшие пути только для некоторых пар, но заранее набор этих пар неизвестен);
 +
* динамический граф<ref>Demetrescu, Camil, and Giuseppe F Italiano. “Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.” Journal of Computer and System Sciences 72, no. 5 (August 2006): 813–37. doi:10.1016/j.jcss.2005.05.005.</ref>: рёбра и вершины могут добавляться и удаляться, при этом происходит пересчёт кратчайших расстояний (вариант подходит для постоянно меняющихся графов, например, для социальных сетей).
  
−
Исходя из исходного кода, можно увидеть, что всего встречается 6 разных видов фрагментов для отдельных массивов (эти виды выделены на рис. 12.1 зеленым). Стоит сделать два уточнения: 1) профиль для результирующего массива С всегда в 2 раза больше, поскольку к элементам этого массива всегда происходят по два обращения подряд; 2) если во внутреннем цикле используется элементы массива, то обращение к этому элементу выносится за пределы внутреннего цикла (в цикле используется скалярная переменная вместо него).
+
== Описание входных и выходных данных ==
  
−
Также заранее отметим, что рисунки по профилям получаются следующим образом: строится рисунок по общему профилю, после чего из него оставляется только часть для рассматриваемого массива. Доля обращений к одному массиву может меняться, поэтому и частота обращений на каждом рисунке может в значительной степени отличаться.
+
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>).
  
−
Рассмотрим подробнее каждый из данных 6 фрагментов на примере массива С.
+
'''Объём входных данных''': <math>O(m + n)</math>.
  
−
'''Фрагмент 1.''' На рисунке 12.2 показано начало фрагмента 1 (здесь и далее начало фрагмента соответствует выделенной оранжевой области на рис. 12.1). Можно увидеть, что данный фрагмент устроен достаточно просто: выполняется перебор некоторого блока элементов массива, затем данный перебор циклически повторяется. После этого происходит переход к следующему блоку элементов массива, и выполняется тот же перебор в цикле.
+
'''Выходные данные''' (возможные варианты):
 +
# для каждой пары вершины <math>(u, v)</math> исходного графа – последнее ребро <math>e^*_{uv} = (w, v)</math>, лежащее на кратчайшем пути от вершины <math>u</math> к <math>v</math>, или соответствующая вершина <math>w</math>;
 +
# для каждой пары вершин <math>(u, v)</math> исходного графа – суммарный вес <math>f^*(u, v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.
 +
 +
'''Объём выходных данных''': <math>O(n^2)</math>.
  
−
Если рассмотреть фрагмент более подробно (рисунок 12.3), можно увидеть, что каждый перебор является на самом деле последовательным перебором, при этом к каждому элементу происходит обращение дважды.
+
=== Преобразование выходных данных и поиск кратчайшего пути ===
  
−
В результате можно сделать вывод, что фрагмент 1 обладает высокой пространственной локальностью (из-за последовательного перебора и последовательной смены блоков перебора), а также высокой временно́й локальностью (из-за двойного обращения к элементам, а также сгруппированности всех обращений к одному элементу в рамках одного блока перебора).  
+
Кратчайший путь от <math>u</math> к <math>v</math> может быть восстановлен за время <math>O(\left |P^*(u, v) \right |)</math>, если, начиная с вершины <math>v</math>, проходить рёбра <math>e^*_{uw}</math> в обратном направлении до тех пор, пока не будет посещена вершина <math>u</math>.
  
−
[[file:matrmult 2.PNG|thumb|center|700px|Рисунок 12.2. Начало фрагмента 1]]
+
Рёбра <math>e^*_{uv}</math> могут быть восстановлены за время <math>O(mn)</math> перебором рёбер для каждой вершины:
−
[[file:matrmult 3.PNG|thumb|center|700px|Рисунок 12.3. Начало фрагмента 1, первые 3 итерации]]
+
:<math>
 +
    e^*_{uv} \in \{ (w, v) \in E \mid f^*(u, v) = f^*(u, w) + f((v, w)) \}.
 +
</math>
 +
Перебор может осуществляться параллельно.
  
−
'''Фрагмент 2.''' На рисунке 12.4 представлено начало фрагмента 2. Видно, что данный фрагмент также представляет собой перебор элементов массива в цикле, однако в данном случае на каждой итерации цикла перебираются сразу все элементы массива, а не только элементы одного блока. При более подробном рассмотрении итерации (рис. 12.5) видно, что здесь также происходит именно последовательный перебор, и также к каждому элементу обращение происходит дважды (поскольку это массив С).
+
Для поиска кратчайших расстояний <math>f^*(u, v)</math> по набору рёбер <math>e^*_{uv}</math>, необходимо для данной вершины <math>u</math> построить дерево из рёбер <math>e^*_{uv}</math> и выполнить на нём [[Поиск в ширину (BFS)|поиск в ширину]] за время <math>O(m)</math> (с возможностью параллелизации), общее время для всех пар вершин – <math>O(mn)</math>.
  
−
[[file:matrmult 4.PNG|thumb|center|700px|Рисунок 12.4. Начало фрагмента 2]]
+
== Алгоритмы решения задачи ==
−
[[file:matrmult 5.PNG|thumb|center|700px|Рисунок 12.5. Начало фрагмента 2, часть первой итерации]]
 
  
−
Такой фрагмент также обладает высокой пространственной локальностью, однако временна́я локальность несколько ниже, чем во фрагменте 1. Это связано с тем, что на каждой итерации цикла перебираются все элементы массива, а не только отдельный блок, т.е. повторные обращения происходят реже.
+
* '''[[Алгоритм Джонсона]]'''<ref>Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.</ref> для ориентированных графов с произвольными весами, сложность <math>O(mn+ n^2 \ln n)</math>.
 +
* '''[[Алгоритм Флойда-Уоршелла]]'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> для ориентированных графов с произвольными весами, сложность <math>O(n^3)</math>.
 +
* Многократное применение любого алгоритма [[Поиск кратчайшего пути от одной вершины (SSSP)|поиска кратчайшего пути от одной вершины]]:
 +
** '''[[Поиск в ширину (BFS)]]''' для ориентированных невзвешенных графов, сложность <math>O(mn)</math>.
 +
** '''[[Алгоритм Дейкстры]]'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref><ref>Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.</ref> для ориентированных графов с неотрицательными весами, сложность <math>O(mn + n^2 \ln n)</math>.
 +
** '''[[Алгоритм Беллмана-Форда]]'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> для ориентированных графов с произвольными весами, сложность <math>O(mn^2)</math>.
 +
** '''[[Алгоритм Δ-шагания]]'''<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами <math>O(n(n + m + dL))</math>, параллельная сложность <math>O((dL + \ln n) n \ln n</math> со средней работой <math>O(n (n + m + dL \ln n))</math>.
 +
** '''Алгоритм Торупа'''<ref name=thorup /> представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время <math>O(mn)</math>.
 +
** В ориентированном ациклическом графе с произвольными весами алгоритм основан на топологической сортировке графа, сложность <math>O(mn)</math>.
  
−
'''Фрагмент 3.''' Начало данного фрагмента представлено на рисунке 12.6. Данный профиль является последовательным перебором всех элементов массива, однако более подробное рассмотрение показывает, что к каждому элементу происходит обращение дважды, при этом между обращениями происходит достаточно много других обращений. Это связано с указанным ранее замечанием касательно вынесения повторяющегося обращения за предел внутреннего цикла.
+
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>d</math> – максимальная степень вершины, <math>L</math> – максимальный суммарный вес кратчайшего пути.
  
−
[[file:matrmult 6.PNG|thumb|center|700px|Рисунок 12.6. Начало фрагмента 3]]
+
== Ресурс параллелизма ==
−
[[file:matrmult 7.PNG|thumb|center|700px|Рисунок 12.7. Начало фрагмента 3, первые несколько обращений]]
 
  
−
Такой фрагмент также обладает высокой пространственной локальностью, однако очень низкой временно́й, поскольку к каждому элементу обращение происходит только два раза.
+
Задача может быть решена путём применения любого алгоритма [[Поиск кратчайшего пути от одной вершины (SSSP)|поиска кратчайшего пути от одной вершины]] для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.
  
−
'''Фрагмент 4.''' По началу фрагмента 4 видно, что профиль снова состоит из перебора всех элементов массива, однако на этот раз перебор не последовательный, а с некоторым шагом. Также можно заметить, что на каждой новой итерации перебор с шагом начинается с элемента, индекс которого немного больше, чем на предыдущей итерации. В данном случае нет нужды рассматривать профиль более подробно, поскольку из данного рисунка можно получить всю необходимую информацию.
+
В связи с квадратичной сложностью выходных данных и более чем квадратичной сложностью вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров<ref>Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.</ref>:
 +
* [[Алгоритм Шилоаха-Вишкина поиска компонент связности|выделение компонент связности]];
 +
* [[Алгоритм Тарьяна поиска «мостов» в графе|выделение подграфов, связанных только «мостами»]] (рёбрами, удаление которых нарушает связность графа);
 +
* [[Алгоритм Тарьяна поиска компонент двусвязности|выделение компонент двусвязности]], связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
 +
* удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).
  
−
По сравнению с предыдущим фрагментом, данный профиль обладает более низкой пространственной локальностью, поскольку перебор элементов идет с шагом, и также очень низкой временно́й локальностью, поскольку на каждой итерации происходят обращения к новым элементам.
+
Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.
  
−
[[file:matrmult 8.PNG|thumb|center|700px|Рисунок 12.8. Начало фрагмента 4]]
 
  
−
'''Фрагмент 5.''' В отличие от предыдущих фрагментов, исходя из визуализации начала данного фрагмента (рис. 12.8), сложно сделать выводы относительно структуры обращения в память. Однако более подробное рассмотрение (рис. 12.9) показывает, что данный профиль практически идентичен профилю предыдущего фрагмента. Более того, фрагмент 5 на самом деле состоит из итерационно повторяющихся фрагментов 4.
+
= Поиск транзитивного замыкания орграфа =
  
−
[[file:matrmult 9.PNG|thumb|center|700px|Рисунок 12.9. Начало фрагмента 5]]
+
== Постановка задачи ==
−
[[file:matrmult 10.PNG|thumb|center|700px|Рисунок 12.10. Начало фрагмента 5, первые несколько итераций]]
 
  
−
Данный фрагмент обладает по сравнению с фрагментом 4 практически такой же пространственной локальностью, однако более высокой временной локальностью. Причина в обоих случаях одна – в данном случае тот же набор обращений повторяется несколько раз.
+
Пусть задан ориентированный граф <math>G = (V, E)</math>. Последовательность <math>P(u, v)</math> рёбер <math>e_1 = (u, w_1)</math>, <math>e_2 = (w_1, w_2)</math>, …, <math>e_k = (w_{k-1}, v)</math> называется ''путём'', идущим от вершины <math>u</math> к вершине <math>v</math>. Вершина <math>v</math> называется ''достижимой'' из вершины <math>u</math>, если существует хотя бы один путь <math>P(u, v)</math>. Каждая вершина достижима сама из себя.
  
−
'''Фрагмент 6.''' Данный фрагмент, представленный на рис. 12.11 и 12.12, так же сильно напоминает фрагмент 5, но с одним отличием. Во фрагменте 5 несколько раз повторяется фрагмент 4, в рамках которого выполняется несколько итераций, и на каждой итерации внутри фрагмента 4 используются разные элементы (поскольку первый элемент сдвигается на 1). В случае данного фрагмента выполняются все те же итерации, но в перемешанном виде. Сначала выполняются все итерации, начинающиеся с одного и того же элемента; затем все итерации, который начинаются с элемента, чей индекс идет следующим; и т.д.
+
Требуется построить '''транзитивное замыкание''' <math>G^+ = (V, E^+)</math> графа <math>G</math>: ребро <math>(v, w) \in E^+</math> тогда и только тогда, когда в графе <math>G</math> вершина <math>w</math> достижима из вершины <math>v</math>.
  
−
Такой фрагмент обладает более высокой и пространственной, и временно́й локальностью по сравнению с фрагментом 5, поскольку обращения в одним и тем же элементам расположены ближе друг к другу в профиле.
+
Эквивалентная формулировка: для данного рефлексивного бинарного отношения <math>R</math> требуется построить наименьшее по включению отношение <math>R^+</math>, содержащее <math>R</math> и облагающее свойством транзитивности: если <math>aR^+b</math> и <math>bR^+c</math>, то <math>aR^+c</math>. Если исходное отношение <math>R</math> было симметричным, то <math>R^+</math> будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.
  
−
[[file:matrmult 11.PNG|thumb|center|700px|Рисунок 12.11. Начало фрагмента 6]]
+
== Свойства задачи ==
−
[[file:matrmult 12.PNG|thumb|center|700px|Рисунок 12.12. Начало фрагмента 6, первые несколько итераций]]
 
  
−
В итоге можно сказать, что наиболее низкой локальностью в целом обладают фрагменты 5 и 6. Фрагмент 4 также обладает низкой локальностью, однако содержит значительно меньшее число обращений, а значит, привносит меньший вклад в общий профиль обращений. Это позволяет определить, что наименее эффективными с точки зрения работы с памятью являются варианты kji и jki, поскольку каждый из них содержит фрагменты 5 и 6. Далее идут варианты ijk и jik – в них по одному такому фрагменту. Самые лучшие варианты – ikj и kij.
+
Если вершины <math>v</math> и <math>w</math> принадлежат одной [[Связность в графах|компоненте сильной связности]] графа <math>G</math>, то транзитивное замыкание содержит рёбра <math>(v, w)</math> и <math>(w, v)</math>. В неориентированном графе ребро <math>(v, w)</math> принадлежит транзитивному замыканию в том и только в том случае, когда вершины <math>v</math> и <math>w</math> принадлежат одной и той же компоненте связности. Следовательно, для неориентированного графа поиск транзитивного замыкания эквивалентен поиску компонент связности.
  
−
===== Количественная оценка локальности =====
+
Если вершины <math>x</math> и <math>y</math> принадлежат одной компоненте сильной связности графа <math>G</math>, а вершины <math>z</math> и <math>t</math> – другой, то рёбра <math>(x, z)</math>, <math>(x, t)</math>, <math>(y, z)</math>, <math>(y, t)</math> принадлежат или не принадлежат транзитивному замыканию <math>G^+</math> одновременно. Следовательно, поиск транзитивного замыкания графа <math>G</math> можно свести к поиску транзитивного замыкания ациклического графа, полученного из <math>G</math> схлопыванием каждой компоненты сильной связности в одну вершину; на этом принципе основан [[алгоритм Пурдома]].
  
−
Основные фрагменты реализации, на основе которых были получены количественные оценки, приведены [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/matrix_mult/matrix_mult.h здесь] (функция Kernel***, где *** - порядок циклов (напр., KernelIJK) ). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
+
Граф <math>G</math> и его транзитивное замыкание <math>G^+</math> имеют одни и те же компоненты сильной связности (в терминах вершин).
  
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
+
== Алгоритмы решения задачи ==
  
−
На рисунке 12.13 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, как и предполагалось  наиболее эффективными являются варианты kij,ikj. Заметно хуже результат у вариантов jik,ijk, при этом эти варианты практически равны между собой. Самый плохой результат ожидаемо у вариантов jki,kji.
+
В '''неориентированном''' графе вершина <math>w</math> достижима из вершины <math>v</math> тогда и только тогда, когда они обе принадлежат одной и той же компоненте связности. Транзитивное замыкание сводится к поиску [[Связность в графах|компонент связности]] графа и может быть найдено следующими алгоритмами:
 +
* последовательным применением алгоритма [[Поиск в ширину (BFS)|поиска в ширину]] за время <math>O(m)</math>;
 +
* с помощью [[Система непересекающихся множеств|системы непересекающихся множеств]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.</ref>;
 +
* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности|Шилоаха-Вишкина]]<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.
  
−
[[file:matrmult daps ru.PNG|thumb|center|700px|Рисунок 12.13. Сравнение значений оценки daps]]
+
В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
 +
* '''[[Алгоритм Флойда-Уоршелла|алгоритм Флойда-Уоршелла]]'''<ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref>, сложность <math>O(n^3)</math> (первый опубликованный алгоритм поиска транзитивного замыкания<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
 +
* многократное применение '''[[Поиск в ширину (BFS)|поиска в ширину]]''', сложность <math>O(mn)</math>;
 +
* '''[[алгоритм Пурдома]]'''<ref name=Purdom>Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.</ref>, сложность <math>O(m + \mu n)</math>.
  
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.  
+
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>\mu \le m</math> – число рёбер, соединяющих [[Связность в графах|компоненты сильной связности]].
  
−
На рисунке 12.14 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Относительное сравнение результатов по cvg в целом повторяет результаты daps.
+
== Ресурс параллелизма ==
  
−
[[file:matrmult cvg.PNG|thumb|center|700px|Рисунок 12.14. Сравнение значений оценки cvg]]
+
Задача может быть решена путём алгоритма [[Поиск в ширину (BFS)|поиска в ширину]] для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.
  
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров<ref>Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.</ref>:
−
=== Масштабируемость алгоритма и его реализации ===
+
* [[Алгоритм Шилоаха-Вишкина поиска компонент связности|выделение компонент связности]];
−
==== Описание масштабируемости алгоритма ====
+
* [[Алгоритм Тарьяна поиска «мостов» в графе|выделение подграфов, связанных только «мостами»]] (рёбрами, удаление которых нарушает связность графа);
−
==== Описание масштабируемости реализации алгоритма ====
+
* [[Алгоритм Тарьяна поиска компонент двусвязности|выделение компонент двусвязности]], связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
 +
* удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).
  
−
[[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рисунок 1. Параллельная реализация произведения матриц Максимальная производительность. ]]
+
Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.
−
[[file:Масштабируемость параллельной реализации перемножения матриц Эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация произведения матриц Максимальная эффективность. ]]
 
−
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 
−
* число процессоров [4 : 1024]
 
−
* размерность матрицы [1024 : 20480]
 
−
Эффективность выполнения реализации алгоритма
 
−
* Минимальная эффективность 4,71%
 
−
* Максимальная эффективность 31,72%
 
−
Оценка масштабируемости
 
−
* По числу процессов: -0.0436 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
 
−
* По размеру задачи: -0.0255 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
 
−
* По двум направлениям: -0.000968 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 25% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.
 
  
−
[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrixmult/matrixmult.c Реализация алгоритма на языке C]
 
  
−
= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =
+
= Построение минимального остовного дерева (MST) =
  
−
== Программная реализация ==
+
== Постановка задачи ==
−
=== Особенности реализации последовательного алгоритма ===
 
−
В простейшем варианте алгоритм на Фортране можно записать так, что входной и выходной массивы совпадают (здесь использован массив X):
 
  
−
<source lang="fortran">
+
Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Подграф, являющийся деревом и проходящий через все вершины
−
       
+
<math>G</math>, называется ''основным деревом''. Остовное дерево называется ''минимальным'', если суммарный вес его рёбер является минимальным среди всех остовных
−
        subroutine STEP2(x,y,pov)
+
деревьев.
−
        complex x, y, pov, u, v
 
−
        u = x + y
 
−
        v = (x-y)*pov
 
−
        x = u
 
−
        y = v
 
−
        return
 
−
        end
 
−
        subroutine FFT2(X, POV, N, N2, L)
 
−
C
 
−
C L = Log2N
 
−
C N2 = N/2
 
−
C
 
−
        complex X(0:N-1), POV(0:N2-1)
 
−
        DO I = 0, L-1
 
−
            DO J = 0, N2/2**I-1
 
−
            DO K = 0, 2**I-1
 
−
                call STEP2(X(2*J*2**I+K)), X(2*J*2**I+2**I+K), POV(J*2**I-1))
 
−
            END DO
 
−
            END DO
 
−
        END DO
 
−
        return
 
−
        end
 
  
−
</source>
+
Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки<ref name=boruvka>Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.</ref>. Английское название задачи – Minimum Spanning Tree (MST).
  
−
Здесь предполагается, что поворотные множители первого шага (они потом используются и на последующих шагах) предвычислены заранее и лежат в элементах массива POV (а в его нулевом элементе - единица). К сожалению, подавляющее большинство реализаций простого алгоритма Кули-Тьюки вычисляет поворотные множители одновременно с вычислением "бабочки", что её значительно замедляет.
+
== Варианты задачи ==
  
−
=== Описание локальности данных и вычислений ===
+
Если исходный граф <math>G</math> несвязный, то набор минимальных остовных деревьев для всех компонент связности называется ''минимальным остовным лесом'' (Minimum
−
==== Описание локальности реализации алгоритма ====
+
Spanning Forest, MSF).
−
===== Описание структуры обращений в память и качественная оценка локальности =====
 
  
−
[[file:fft 1.PNG|thumb|center|700px|Рисунок 12.1. Нерекурсивная реализация БПФ для степеней двойки. Общий профиль обращений в память]]
+
Для графа с целочисленными весами возможно использование специальных приёмов, таких как [[wikipedia:ru:Поразрядная сортировка|поразрядная сортировка]], что приводит к
 +
алгоритмам, решающим задачу за линейное время.
  
−
На рисунке 12.1 представлен профиль обращений в память для нерекурсивной реализации быстрого преобразования Фурье. Исходя из исходного кода, можно увидеть, что в программе задействовано 3 массива. Фрагменты двух из них отмечены на рис. 12.1 зеленым, к третьему массиву относится вся остальная часть профиля.
+
В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.
  
−
Фрагменты 1 и 2 образованы обращениями соответственно к входному и выходному массиву. Из рисунка видно, что в обоих случаях фрагменты представляют собой аналог последовательного перебора. Анализ исходного кода показывает, что это действительно так: в обоих случаях в рамках одного цикла последовательно перебираются все элементы массива. Такие профили обладают высокой пространственной локальностью и очень низкой временной, поскольку повторные обращения просто отсутствуют.
+
== Свойства задачи ==
  
−
Гораздо интереснее устроен последний фрагмент. Его можно разбить на 4 этапа, которые выделены на рис. 12.1 оранжевым цветом. Первый этап по времени совпадает с фрагментом 1, и сам профиль также похож на последовательный перебор. Из исходного кода видно, что обращения этапа 1 – это запись в массив data либо 0, либо значений, считываемых во фрагменте 1 из массива dIn:
+
'''Веса'''. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, <math>[0, 1]</math>.
−
<source lang="C">
 
−
for( i = 0; i < nn; i++ ) {
 
−
data [ i ] = 0;
 
−
data[ i * 2 + 1 ] = dIn[ i ];
 
−
}
 
−
</source>
 
  
−
Видно, что обращения этапа 1 также образуют последовательный перебор. Аналогична ситуация с этапом 4, однако там на каждое 1 обращение фрагмента 1 приходится 4 последовательных обращений этапа 4.
+
'''Существование и единственность'''. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.
  
−
Рассмотрим более подробно этап 2 (рис. 12.2). Можно увидеть, что в начале этого этапа происходят обращения по всему массиву, но чем ближе к концу этапа, тем ближе к концу массива происходят обращения. Видно, что часть обращений (кривая внизу рисунка) расположены близко друг к другу, а остальные обращения разбросаны достаточно далеко и образуют нечто похожее на случайный доступ.  
+
'''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих
 +
<math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.
  
−
[[file:fft 2.PNG|thumb|center|700px|Рисунок 12.2. Основной фрагмент, этап 2]]
+
'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].
  
−
Исходный код, в котором происходят обращения данного этапа, устроен следующим образом:
+
'''Минимальное ребро графа'''. Если <math>e^*</math> – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан [[алгоритм Крускала]].
  
−
<source lang="C">
+
'''Ассоциативность по рёбрам'''. Пусть <math>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда
−
while( i < n ) {
 
−
if( j > i ) {
 
−
tempr = data[ i ]; data[ i ] = data[ j ]; data[ j ] = tempr;
 
−
tempr = data[ i + 1 ]; data[ i + 1 ] = data[ j + 1 ];
 
−
data[ j + 1 ] = tempr;
 
−
}
 
−
m = n >> 1;
 
−
while( ( m >= 2 ) && ( j > m ) ) {
 
−
j = j - m;
 
−
m = m >> 1;
 
−
}
 
−
j = j + m;
 
−
i = i + 2;
 
−
}
 
−
</source>
 
  
−
Можно увидеть, что действительно обращения выполняются по двум независимым индексам – на основе переменных i и j; при этом обращения на основе индекса i образуют кривую внизу рис. 12.2, а обращения на основе индекса j – остальные, разбросанные по всему массиву обращения.  
+
:<math>
 +
        MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
 +
</math>
  
−
Стоит заметить, что обращения на основе индекса j не образуют случайный доступ, а подчиняются определенному закону выбора следующего элемента. Однако с точки зрения качественной оценки локальности подобные фрагменты похожи.  
+
'''Количество рёбер''' остовного леса для графа с <math>n</math> вершинами и <math>c</math> компонентами связности равно <math>n-c</math>. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.
  
−
Таким образом, этап 2 состоит из двух фрагментов на основе двух разных индексов. Первый из них которых обладает высокой пространственной локальностью (последовательный перебор элементов) и низкой временной (к каждому элементу происходит только два обращения). Второй обладает и достаточно низкой пространственной (элементы расположены далеко друг от друга, за исключением конца этапа), и низкой временной (к каждому элементу происходит только два обращения) локальностью.
+
== Описание входных и выходных данных ==
  
−
Теперь перейдем к рассмотрению самого длительного этапа 3. Отдельно данный фрагмент представлен на рис. 12.3. Исходя из рисунка, можно увидеть, что данный фрагмент состоит из нескольких итераций, причем первая итерация состоит из единичного перебора элементов массивов с некоторым шагом, вторая итерация состоит из двух проходов с одинаковым шагом (большим, чем на первой итерации), третья – из 4-х проходов и т.д., пока число проходов на итерации не начинает уменьшаться в обратную сторону. Итерации разделены на рис. 12.3 оранжевыми линиями.
+
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j},
 +
v^{(2)}_{j})</math> с весами <math>f_j</math>).
  
−
[[file:fft 3.PNG|thumb|center|700px|Рисунок 12.3. Основной фрагмент, этап 3]]
+
'''Объём входных данных''': <math>O(m + n)</math>.
  
−
Видно, что внутри каждой итерации проходы обладают одинаковой структурой, а также можно предположить, что при переходе к новой итерации шаг изменяется в два раза, что и подтверждает анализ исходного кода. Также можно увидеть, что каждая итерация состоит из примерно одного числа обращений (размер выделенных оранжевыми линиями частей одинаковы).  
+
'''Выходные данные''': список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).
  
−
Первая итерация похожа на последовательный перебор элементов массива, поэтому она обладает высокой пространственной и низкой временной локальностью. При увеличении шага пространственная локальность становится хуже, однако неясно, каким образом меняется временная локальность – это зависит от того, происходит ли повторный проход по тем же элементам или нет. Анализ исходного кода показывает, что каждый проход выполняется над своими элементами, поэтому временная локальность остается такой же низкой. Однако отметим, что на каждой итерации используются один и те же элементы, поэтому в целом повышает временную локальность.
+
'''Объём выходных данных''': <math>O(n)</math>.
  
−
Более подробное изучение каждого прохода (рис. 12.4, на которой приближена выделенная зеленым часть рис. 12.3) показывает, что он обладает более сложной структурой, чем просто перебор элементов массива с некоторым шагом: в данном случае происходит серия близких друг к другу обращений, и затем сдвиг на некоторый шаг. Это приводит к некоторому улучшению как пространственной, так и временной локальности.
+
== Алгоритмы решения задачи ==
  
−
[[file:fft 4.PNG|thumb|center|700px|Рисунок 12.4. Основной фрагмент, небольшая часть этапа 3]]
+
Существует три классических подхода к решению задачи:
 +
* '''[[Алгоритм Борувки]]''';<ref name=boruvka /><ref>Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.</ref>
 +
* '''[[Алгоритм Крускала]]''';<ref>Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (January 1956): 48–50. doi:10.1090/S0002-9939-1956-0078686-7.</ref>
 +
* '''[[Алгоритм Прима]]'''.<ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref><ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref>
 +
Во всех случаях последовательная сложность алгоритма <math>O(m \ln m)</math> при использовании обычных структур данных. (Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.)
  
−
===== Количественная оценка локальности =====
+
Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.
 +
* '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> и его последующие версии<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref> являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
 +
* '''Алгоритм Габова''' и др.<ref>Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.</ref> использует [[wikipedia:ru:Фибоначчиева куча|фибоначчиеву кучу]] для упорядочения рёбер в алгоритме Борувки. Сложность <math>O(m \ln \beta (m, n))</math>.
 +
* '''Алгоритм Фредмана и Уилларда'''<ref>Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.</ref> предназначен для графов с целочисленными весами и имеет линейную оценку сложности <math>O(m)</math>. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи ([[wikipedia:AF-heap|AF-heap]]).
 +
* '''Алгоритм Каргера''' и др.<ref>Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.</ref> решает задачу ''в среднем'' за линейное время <math>O(m)</math>. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)
  
−
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/fft/fft.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
+
Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем <math>O(m \ln n)</math>, как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.
  
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
+
== Ресурс параллелизма ==
  
−
На рисунке 12.5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что данная оценка показывает низкую производительность, на уровне случайного доступа в память (rand).
+
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
 +
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
 +
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.  
  
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность
+
= Поиск изоморфных подграфов =
  
−
[[file:fft daps ru.PNG|thumb|center|700px|Рисунок 12.5. Сравнение значений оценки daps]]
+
== Постановка задачи ==
  
−
На рисунке 12.6 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, данная реализация БПФ демонстрирует несколько лучшую локальность по сравнению со случайным доступом или рекурсивной версией, в отличие от оценки daps, результаты которой для данных программ практически совпадали. На данный момент остается неясным, чем обусловлено это различие. Однако стоит отметить, что значение локальности cvg также остается в нижней части таблицы.
+
Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфный <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.
  
−
[[file:fft cvg.PNG|thumb|center|700px|Рисунок 12.6. Сравнение значений оценки cvg]]
+
== Свойства задачи ==
  
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.
−
=== Масштабируемость алгоритма и его реализации ===
 
−
==== Описание масштабируемости алгоритма ====
 
−
==== Описание масштабируемости реализации алгоритма ====
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
−
=== Выводы для классов архитектур ===
 
  
−
Граф простого алгоритма Кули-Тьюки лучше всего из коммуникационных сетей отображается на сеть типа [[гиперкуб]]. Распространённость БПФ в методах решения различных задач поэтому привела к популярности идеи вычислительных систем с сетью типа гиперкуб в начале развития различных параллельных вычислительных систем. В настоящее время, однако, массово такие вычислительные системы не используются по физическим причинам, делающим гиперкуб большой размерности труднореализуемым на практике.
+
== Алгоритмы решения задачи ==
−
Как видно из графа, при простом его разбиении на части прямыми, параллельными оси шагов, на первых шагах алгоритма обмены между разными частями будут отсутствовать, но, начиная с некоторого момента, они станут составлять величину, сопоставимую с количеством арифметических операций. Этого, однако, можно избежать, если примерно посередине алгоритма переупорядочить все данные. В графе это будет соответствовать смене разбиения на части.
 
−
При выполнении указанных рекомендаций, алгоритм можно будет реализовать более эффективно, чем в настоящее время, и на архитектурах типа кластерной и на других архитектурах, реализующих разбиение процесса на независимые ветви.
 
  
−
=== Существующие реализации алгоритма ===
+
'''[[Алгоритм Ульмана]]'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
 +
* для фиксированного графа <math>H</math> время полиномиальное;
 +
* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).
  
−
Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки весьма распространён среди начинающих, использующих БПФ, и его сравнительно легко можно найти в Интернете с помощью поисковых сайтов. Как правило, эти реализации не используют описанных выше приёмов улучшения эффективности вычислений - ни для последовательной, ни для параллельной архитектуры. Связано это с тем, что сам по себе простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки проигрывает другим алгоритмам Кули-Тьюки, которые используют специфику, например, чётных степеней двойки, и потому более экономичны. Поэтому большинство исследователей, которым нужны более быстрые программы БПФ, не улучшают эффективность этого алгоритма, а меняют его на другой.  
+
'''[[Алгоритм VF2]]'''<ref>Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.</ref> разработан специально для применения на больших графах.
−
Это же рекомендуем делать и читателям.
+
 
 +
= Связность в графах =
 +
 
 +
== Основные определения ==
 +
 
 +
Пусть задан (ориентированный или неориентированный) граф <math>G = (V, E)</math>. Последовательность <math>P(u, v)</math> рёбер <math>e_1 = (u, w_1)</math>, <math>e_2 = (w_1, w_2)</math>, …, <math>e_k = (w_{k-1}, v)</math> называется ''путём'', идущим от вершины <math>u</math> к вершине <math>v</math>. В этом случае вершина <math>v</math> ''достижима'' из вершины <math>u</math>. Считается, что от вершины <math>u</math> к себе самой ведёт пустой путь <math>P(u, u)</math>, то есть каждая вершина достижима из самой себя. Непустой путь <math>P(u, u)</math> называется ''циклом'' (''замкнутым обходом'').
 +
 
 +
''Неориентированный'' граф называется ''связным'', если все его вершины достижимы из некоторой вершины (эквивалентно, из любой его вершины).
 +
 
 +
''Ориентированный'' граф называется
 +
* ''слабо связным'', если соответствующий неориентированный граф является связным;
 +
* ''сильно связным'', если всякая вершина <math>v</math> достижима из любой другой вершины <math>v</math>.
 +
 
 +
''Компонентой связности'' неориентированного графа называется максимальный по включению связный подграф.
 +
 
 +
''Компонентой сильной связности'' ориентированного графа называется максимальный по включению сильно связный подграф. Другими словами, это подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.
 +
 
 +
''Мостом'' в графе называется ребро, удаление которого увеличивает число компонент связности.
 +
 
 +
''Шарниром'' в графе называется вершина, удаление которой увеличивает число компонент связности.
 +
 
 +
Связный граф называется ''вершинно-<math>k</math>-связным'' (или просто <math>k</math>-связным), если он имеет более <math>k</math> вершин и после удаления любых <math>k-1</math> из них остаётся связным. Максимальное такое число <math>k</math> называется ''вершинной связностью'' (или просто ''связностью'') графа. 1-связный граф называется связным, 2-связный граф – двусвязным.
 +
 
 +
Связный граф называется ''рёберно-<math>k</math>-связным'', если он остаётся связным после удаления любых <math>k-1</math> рёбер. Максимальное такое число <math>k</math> называется ''рёберной связностью'' графа.
 +
 
 +
''Компонентой двусвязности'' графа называется максимальный по включению двусвязный подграф.
 +
 
 +
== Свойства ==
 +
 
 +
Эквивалентные определения компоненты связности:
 +
* все вершины, достижимые из какой-либо выбранной вершины;
 +
* набор вершин, достижимых друг из друга, и не достижимых из других вершин.
 +
 
 +
Отношение «вершина <math>v</math> достижима из вершины <math>u</math>» является отношением эквивалентности. Таким образом, поиск связных компонент графа это то же самое, что восстановление полного отношения эквивалентности по его части.
 +
 
 +
Альтернативные определения моста:
 +
* ребро является мостом, если не участвует ни в одном цикле;
 +
* ребро <math>e</math> является мостом, если существует пара вершин <math>(u, v)</math> из одной компоненты связности, любой путь <math>P(u, v)</math> между которыми проходит через ребро <math>e</math>.
 +
 
 +
Шарнир разделяет компоненты двусвязности (если две компоненты двусвязности имеют общую вершину, то это шарнир).
 +
 
 +
Каждая из вершин моста является шарниром (кроме случая, когда мост является единственным ребром этой вершины).
 +
 
 +
Компонента сильной связности является объединением всех циклом, проходящих через её вершины.
 +
 
 +
== Алгоритмы ==
 +
 
 +
Компоненты связности могут быть найдены:
 +
* последовательным применением алгоритма [[Поиск в ширину (BFS)|поиска в ширину]] за время <math>O(m)</math>;
 +
* с помощью [[Система непересекающихся множеств|системы непересекающихся множеств]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.</ref>;
 +
* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности|Шилоаха-Вишкина]]<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.
 +
 
 +
Компоненты сильной связности могут быть найдены:
 +
* [[Алгоритм Тарьяна поиска компонент сильной связности|алгоритмом Тарьяна]]<ref name=DFS>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math>;
 +
* [[Алгоритм DCSC поиска компонент сильной связности|параллельным алгоритмом DCSC]]<ref>Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.</ref><ref>McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.</ref><ref>Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.</ref> с работой <math>O(n \ln n)</math>.
 +
 
 +
Мосты могут быть найдены:
 +
* [[Алгоритм Тарьяна поиска «мостов» в графе|алгоритмом Тарьяна]]<ref>Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.</ref> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math>;
 +
* параллельным [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;
 +
* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>Westbrook, Jeffery, and Robert Endre Tarjan. “Maintaining Bridge-Connected and Biconnected Components on-Line.” Algorithmica 7, no. 1 (June 1992): 433–64. doi:10.1007/BF01758773.</ref> за время <math>O(m \alpha(m, n))</math>.
 +
 
 +
Компоненты двусвязности могут быть найдены:
 +
* [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);
 +
* параллельным [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах (алгоритм также может находить и мосты);
 +
* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.
 +
 +
Задача [[Определение вершинной связности графа|определения вершинной связности графа]] сводится к [[Поиск максимального потока в нагруженном графе|поиску максимальных потоков]] и может быть решена за время <math>O(\min\{k^3 + n, kn\} m)</math><ref>Henzinger, Monika R, Satish Rao, and Harold N Gabow. “Computing Vertex Connectivity: New Bounds From Old Techniques.” Journal of Algorithms 34, no. 2 (February 2000): 222–50. doi:10.1006/jagm.1999.1055.</ref>.
 +
 
 +
Рёберная связность графа может быть найдена [[Алгоритм Габова определения рёберной связности графа|алгоритмом Габова]]<ref>Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.</ref> за время <math>O(k m \ln (n^2/m))</math> для ориентированного и <math>O(m + k^2 n \ln (n/k))</math> неориентированного графа. Проверка свойства <math>k</math>-связности тем же алгоритмом может быть выполнена за время <math>O(m + n \ln n)</math>.
 +
 
 +
= Поиск максимального потока в транспортной сети =
 +
 
 +
== Постановка задачи ==
 +
 
 +
''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана неотрицательная пропускная способность <math>c(e) \ge 0</math>. Будем считать, что вместе с каждым ребром <math>e = (v, w) \in E</math> граф содержит и обратное к нему <math>e^R = (w, v)</math> (при необходимости приписывая ему нулевую пропускную способность).
 +
 
 +
Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>f: E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:
 +
* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;
 +
* антисимметричность: <math>f(e^R) = -f(e)</math>;
 +
* закон сохранения потока:
 +
 
 +
:<math>
 +
        \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e).
 +
</math>
 +
 
 +
''Величиной потока'' называется суммарный поток из источника:
 +
 
 +
:<math>
 +
        \lvert f \rvert = \sum_{e = (s, v)} f(e).
 +
</math>
 +
 
 +
'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:
 +
:<math>\lvert f \rvert \to \max.</math>
 +
 
 +
== Свойства задачи ==
 +
 
 +
Суммарный поток из источника равен суммарному потоку в сток:
 +
:<math>
 +
        \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e).
 +
</math>
 +
(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)
 +
 
 +
== Варианты задачи ==
 +
 
 +
В зависимости от ограничений на значения пропускной способности:
 +
* произвольная положительная пропускная способность;
 +
* целая пропускная способность;
 +
* единичная пропускная способность (в этом случае максимальный поток равен [[Связность в графах|рёберной связности]] графа).
 +
 
 +
== Алгоритмы решения задачи ==
 +
 
 +
* [[Алгоритм Форда-Фалкерсона]]<ref>Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.</ref> и его варианты<ref>Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.</ref><ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref> со сложностью <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math>.
 +
* [[Алгоритм проталкивания предпотока]]<ref>Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.</ref> со сложностью <math>O(mn \ln n)</math> (при использовании динамических деревьев Тарьяна-Слитора<ref>Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.</ref><ref>Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.</ref>).
 +
 
 +
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.
 +
 
 +
= Задача о назначениях =
 +
 
 +
== Постановка задачи ==
 +
 
 +
Пусть имеется <math>n</math> агентов и <math>m</math> задач, которые могут быть распределены между этими агентами. Каждому агенту может быть выделена только одна задача, и каждая задача может быть выделена только одному агенту. Стоимость присвоения <math>i</math>-й задачи <math>j</math>-му агенту равна <math>c(i, j)</math>. В случае <math>c(i, j) = \infty</math> задача <math>j</math> не может быть назначена агенту <math>i</math>.
 +
 
 +
'''Задача о назначениях''': сформировать допустимое множество назначений <math>A = \{ (i_1, j_1), \ldots, (i_k, j_k) \}</math>, <math>k = \min \{m, n\}</math>, имеющее макисмальную суммарную стоимость:
 +
 
 +
:<math>
 +
        C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max.
 +
</math>
 +
 
 +
== Варианты задачи ==
 +
 
 +
При <math>m = n</math> задача называется ''линейной'': каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.
 +
 
 +
В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.
 +
 
 +
== Алгоритмы решения задачи ==
 +
 
 +
* [[Венгерский алгоритм]]<ref>Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.</ref><ref>Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.</ref><ref>Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.</ref> для линейной задачи, сложность <math>O(n^4)</math> (может быть уменьшена<ref>Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.</ref> до <math>O(n^3)</math>);
 +
* [[Алгоритм аукциона]]<ref>Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.</ref><ref>Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.</ref>;
 +
* [[Алгоритм Гопкрофта-Карпа]]<ref>Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.</ref> для задачи с единичными ценами, сложность <math>O(m \sqrt{n})</math>.

Версия 17:11, 29 июля 2015

Содержание

1 Поиск кратчайшего пути от одной вершины (SSSP)

1.1 Постановка задачи

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Суммарный вес этого пути равен

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

Требуется для каждой вершины [math]v[/math], достижимой из вершины-источника [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:

[math] f^*(v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

Название задачи на английском языке – «Single Source Shortest Path» (SSSP).

1.2 Варианты задачи

Если требуется найти кратчайшие пути не от одной, а от всех вершин - см. поиск кратчайшего пути для всех пар вершин.

Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.

В зависимости от ограничений на возможные значения весов различают следующие случаи.

  • Единичные веса. В этом случае задача существенно упрощается и может быть решена за линейное время алгоритмом поиска вширь.
  • Положительные целые веса. Задача также может быть решена за линейное время[1] (хотя и с большей константой).
  • Неотрицательные веса. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
  • Произвольные веса. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.

1.3 Свойства задачи

Решение задачи удовлетворяет принципу оптимальности: если путь [math]P^*(u, w)[/math] является частью кратчайшего пути [math]P^*(u, v)[/math], то [math]P^*(u, w)[/math] является кратчайшим путём от источника [math]u[/math] до вершины [math]w[/math].

Принцип оптимальности означает, что для каждой вершины [math]v[/math] вместо всего кратчайшего пути [math]P^*(u, v)[/math] достаточно хранить его последнее ребро [math]e^*_v[/math]. Отсюда следует оценка объёма памяти [math]O(m)[/math].

1.4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]), вершина-источник [math]u[/math].

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

  1. для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
  2. для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n)[/math].

1.4.1 Преобразование выходных данных и поиск кратчайшего пути

Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_w[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].

Рёбра [math]e^*_v[/math] могут быть восстановлены за время [math]O(m)[/math] перебором рёбер для каждой вершины:

[math] e^*_v \in \{ (w, v) \in E \mid f^*(v) = f^*(w) + f((v, w)) \}. [/math]

Перебор может осуществляться параллельно.

Для поиска кратчайших расстояний [math]f^*(v)[/math] по набору рёбер [math]e^*_v[/math], необходимо построить из них дерево, на котором выполнить поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации).

1.5 Алгоритмы решения задачи

  • Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(m)[/math].
  • Алгоритм Дейкстры[2][3] для ориентированных графов с неотрицательными весами, сложность [math]O(m + n \ln n)[/math].
  • Алгоритм Беллмана-Форда[4][5][6] для ориентированных графов с произвольными весами, сложность [math]O(mn)[/math].
  • Алгоритм Δ-шагания[7] для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n + m + dL)[/math], параллельная сложность [math]O((dL + \ln n) \ln n[/math] со средней работой [math]O(n + m + dL \ln n)[/math].
  • Алгоритм Торупа[1] представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(m)[/math].
  • В ориентированном ациклическом графе с произвольными весами время поиска кратчайших путей линейное – [math]O(m + n)[/math], алгоритм основан на топологической сортировке графа.

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.

Перечисленные алгоритмы могут использоваться и для решения задачи поиска кратчайшего пути для всех пар вершин графа (для этого необходимо запустить соответствующий алгоритм для каждой вершины графа, что при необходимости можно сделать параллельно), при этом оценка сложности умножается на [math]n[/math].


2 Поиск кратчайшего пути для всех пар вершин (APSP)

2.1 Постановка задачи

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math], [math]e \in E[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Вершина [math]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Суммарный вес этого пути равен

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

Требуется для каждой пары вершины [math](u, v)[/math], для которой вершина [math]v[/math] достижима из вершины [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:

[math] f^*(u, v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

Название задачи на английском языке – «All Pairs Shortest Path» (APSP).

2.2 Варианты задачи

Если требуется найти кратчайшие пути лишь от одной, а не от всех вершин – см. поиск кратчайшего пути от одной вершины.

Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.

В зависимости от ограничений на возможные значения весов различают следующие случаи.

  • Единичные веса. В этом случае задача существенно упрощается и может быть решена за квадратичное время алгоритмом поиска вширь.
  • Положительные целые веса. Задача также может быть решена за квадратичное время[1] (хотя и с большей константой).
  • Неотрицательные веса. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
  • Произвольные веса. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.

В зависимости от способа организации вычислений возможны следующие варианты:

  • статический граф, полное вычисление всех кратчайших путей (классический подход);
  • вычисление онлайн[8]: производятся предварительные вычисления, далее путь между парой вершин вычисляется по запросу (такой подход уместен, если в реальности потребуется вычислить кратчайшие пути только для некоторых пар, но заранее набор этих пар неизвестен);
  • динамический граф[9]: рёбра и вершины могут добавляться и удаляться, при этом происходит пересчёт кратчайших расстояний (вариант подходит для постоянно меняющихся графов, например, для социальных сетей).

2.3 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

  1. для каждой пары вершины [math](u, v)[/math] исходного графа – последнее ребро [math]e^*_{uv} = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
  2. для каждой пары вершин [math](u, v)[/math] исходного графа – суммарный вес [math]f^*(u, v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n^2)[/math].

2.3.1 Преобразование выходных данных и поиск кратчайшего пути

Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_{uw}[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].

Рёбра [math]e^*_{uv}[/math] могут быть восстановлены за время [math]O(mn)[/math] перебором рёбер для каждой вершины:

[math] e^*_{uv} \in \{ (w, v) \in E \mid f^*(u, v) = f^*(u, w) + f((v, w)) \}. [/math]

Перебор может осуществляться параллельно.

Для поиска кратчайших расстояний [math]f^*(u, v)[/math] по набору рёбер [math]e^*_{uv}[/math], необходимо для данной вершины [math]u[/math] построить дерево из рёбер [math]e^*_{uv}[/math] и выполнить на нём поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации), общее время для всех пар вершин – [math]O(mn)[/math].

2.4 Алгоритмы решения задачи

  • Алгоритм Джонсона[10] для ориентированных графов с произвольными весами, сложность [math]O(mn+ n^2 \ln n)[/math].
  • Алгоритм Флойда-Уоршелла[11][12][13] для ориентированных графов с произвольными весами, сложность [math]O(n^3)[/math].
  • Многократное применение любого алгоритма поиска кратчайшего пути от одной вершины:
    • Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(mn)[/math].
    • Алгоритм Дейкстры[14][15] для ориентированных графов с неотрицательными весами, сложность [math]O(mn + n^2 \ln n)[/math].
    • Алгоритм Беллмана-Форда[16][17][18] для ориентированных графов с произвольными весами, сложность [math]O(mn^2)[/math].
    • Алгоритм Δ-шагания[19] для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n(n + m + dL))[/math], параллельная сложность [math]O((dL + \ln n) n \ln n[/math] со средней работой [math]O(n (n + m + dL \ln n))[/math].
    • Алгоритм Торупа[1] представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(mn)[/math].
    • В ориентированном ациклическом графе с произвольными весами алгоритм основан на топологической сортировке графа, сложность [math]O(mn)[/math].

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.

2.5 Ресурс параллелизма

Задача может быть решена путём применения любого алгоритма поиска кратчайшего пути от одной вершины для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.

В связи с квадратичной сложностью выходных данных и более чем квадратичной сложностью вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[20]:

Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.


3 Поиск транзитивного замыкания орграфа

3.1 Постановка задачи

Пусть задан ориентированный граф [math]G = (V, E)[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Вершина [math]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Каждая вершина достижима сама из себя.

Требуется построить транзитивное замыкание [math]G^+ = (V, E^+)[/math] графа [math]G[/math]: ребро [math](v, w) \in E^+[/math] тогда и только тогда, когда в графе [math]G[/math] вершина [math]w[/math] достижима из вершины [math]v[/math].

Эквивалентная формулировка: для данного рефлексивного бинарного отношения [math]R[/math] требуется построить наименьшее по включению отношение [math]R^+[/math], содержащее [math]R[/math] и облагающее свойством транзитивности: если [math]aR^+b[/math] и [math]bR^+c[/math], то [math]aR^+c[/math]. Если исходное отношение [math]R[/math] было симметричным, то [math]R^+[/math] будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.

3.2 Свойства задачи

Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то транзитивное замыкание содержит рёбра [math](v, w)[/math] и [math](w, v)[/math]. В неориентированном графе ребро [math](v, w)[/math] принадлежит транзитивному замыканию в том и только в том случае, когда вершины [math]v[/math] и [math]w[/math] принадлежат одной и той же компоненте связности. Следовательно, для неориентированного графа поиск транзитивного замыкания эквивалентен поиску компонент связности.

Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно. Следовательно, поиск транзитивного замыкания графа [math]G[/math] можно свести к поиску транзитивного замыкания ациклического графа, полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину; на этом принципе основан алгоритм Пурдома.

Граф [math]G[/math] и его транзитивное замыкание [math]G^+[/math] имеют одни и те же компоненты сильной связности (в терминах вершин).

3.3 Алгоритмы решения задачи

В неориентированном графе вершина [math]w[/math] достижима из вершины [math]v[/math] тогда и только тогда, когда они обе принадлежат одной и той же компоненте связности. Транзитивное замыкание сводится к поиску компонент связности графа и может быть найдено следующими алгоритмами:

В ориентированном графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности.

3.4 Ресурс параллелизма

Задача может быть решена путём алгоритма поиска в ширину для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.

В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[28]:

Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.


4 Построение минимального остовного дерева (MST)

4.1 Постановка задачи

Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Подграф, являющийся деревом и проходящий через все вершины [math]G[/math], называется основным деревом. Остовное дерево называется минимальным, если суммарный вес его рёбер является минимальным среди всех остовных деревьев.

Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки[29]. Английское название задачи – Minimum Spanning Tree (MST).

4.2 Варианты задачи

Если исходный граф [math]G[/math] несвязный, то набор минимальных остовных деревьев для всех компонент связности называется минимальным остовным лесом (Minimum Spanning Forest, MSF).

Для графа с целочисленными весами возможно использование специальных приёмов, таких как поразрядная сортировка, что приводит к алгоритмам, решающим задачу за линейное время.

В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.

4.3 Свойства задачи

Веса. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, [math][0, 1][/math].

Существование и единственность. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.

Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].

Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.

Минимальное ребро графа. Если [math]e^*[/math] – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан алгоритм Крускала.

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

Количество рёбер остовного леса для графа с [math]n[/math] вершинами и [math]c[/math] компонентами связности равно [math]n-c[/math]. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.

4.4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные: список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).

Объём выходных данных: [math]O(n)[/math].

4.5 Алгоритмы решения задачи

Существует три классических подхода к решению задачи:

Во всех случаях последовательная сложность алгоритма [math]O(m \ln m)[/math] при использовании обычных структур данных. (Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.)

Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.

  • Алгоритм GHS (Gallager, Humblet, Spira)[34] и его последующие версии[35][36] являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
  • Алгоритм Габова и др.[37] использует фибоначчиеву кучу для упорядочения рёбер в алгоритме Борувки. Сложность [math]O(m \ln \beta (m, n))[/math].
  • Алгоритм Фредмана и Уилларда[38] предназначен для графов с целочисленными весами и имеет линейную оценку сложности [math]O(m)[/math]. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи (AF-heap).
  • Алгоритм Каргера и др.[39] решает задачу в среднем за линейное время [math]O(m)[/math]. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)

Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем [math]O(m \ln n)[/math], как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.

4.6 Ресурс параллелизма

  1. Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
  2. Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
  3. Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

5 Поиск изоморфных подграфов

5.1 Постановка задачи

Пусть заданы два графа [math]G[/math] и [math]H[/math]. Задача поиска изоморфных подграфов состоит в том, чтобы определить, существует ли у графа [math]G[/math] подграф, изоморфный [math]H[/math], и в случае положительного ответа – предъявить хотя бы один такой подграф.

5.2 Свойства задачи

Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.

5.3 Алгоритмы решения задачи

Алгоритм Ульмана[40][41] решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом

  • для фиксированного графа [math]H[/math] время полиномиальное;
  • для планарного графа [math]G[/math] время работы линейное (при фиксированном графе [math]H[/math]).

Алгоритм VF2[42] разработан специально для применения на больших графах.

6 Связность в графах

6.1 Основные определения

Пусть задан (ориентированный или неориентированный) граф [math]G = (V, E)[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. В этом случае вершина [math]v[/math] достижима из вершины [math]u[/math]. Считается, что от вершины [math]u[/math] к себе самой ведёт пустой путь [math]P(u, u)[/math], то есть каждая вершина достижима из самой себя. Непустой путь [math]P(u, u)[/math] называется циклом (замкнутым обходом).

Неориентированный граф называется связным, если все его вершины достижимы из некоторой вершины (эквивалентно, из любой его вершины).

Ориентированный граф называется

  • слабо связным, если соответствующий неориентированный граф является связным;
  • сильно связным, если всякая вершина [math]v[/math] достижима из любой другой вершины [math]v[/math].

Компонентой связности неориентированного графа называется максимальный по включению связный подграф.

Компонентой сильной связности ориентированного графа называется максимальный по включению сильно связный подграф. Другими словами, это подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.

Мостом в графе называется ребро, удаление которого увеличивает число компонент связности.

Шарниром в графе называется вершина, удаление которой увеличивает число компонент связности.

Связный граф называется вершинно-[math]k[/math]-связным (или просто [math]k[/math]-связным), если он имеет более [math]k[/math] вершин и после удаления любых [math]k-1[/math] из них остаётся связным. Максимальное такое число [math]k[/math] называется вершинной связностью (или просто связностью) графа. 1-связный граф называется связным, 2-связный граф – двусвязным.

Связный граф называется рёберно-[math]k[/math]-связным, если он остаётся связным после удаления любых [math]k-1[/math] рёбер. Максимальное такое число [math]k[/math] называется рёберной связностью графа.

Компонентой двусвязности графа называется максимальный по включению двусвязный подграф.

6.2 Свойства

Эквивалентные определения компоненты связности:

  • все вершины, достижимые из какой-либо выбранной вершины;
  • набор вершин, достижимых друг из друга, и не достижимых из других вершин.

Отношение «вершина [math]v[/math] достижима из вершины [math]u[/math]» является отношением эквивалентности. Таким образом, поиск связных компонент графа это то же самое, что восстановление полного отношения эквивалентности по его части.

Альтернативные определения моста:

  • ребро является мостом, если не участвует ни в одном цикле;
  • ребро [math]e[/math] является мостом, если существует пара вершин [math](u, v)[/math] из одной компоненты связности, любой путь [math]P(u, v)[/math] между которыми проходит через ребро [math]e[/math].

Шарнир разделяет компоненты двусвязности (если две компоненты двусвязности имеют общую вершину, то это шарнир).

Каждая из вершин моста является шарниром (кроме случая, когда мост является единственным ребром этой вершины).

Компонента сильной связности является объединением всех циклом, проходящих через её вершины.

6.3 Алгоритмы

Компоненты связности могут быть найдены:

Компоненты сильной связности могут быть найдены:

Мосты могут быть найдены:

Компоненты двусвязности могут быть найдены:

Задача определения вершинной связности графа сводится к поиску максимальных потоков и может быть решена за время [math]O(\min\{k^3 + n, kn\} m)[/math][54].

Рёберная связность графа может быть найдена алгоритмом Габова[55] за время [math]O(k m \ln (n^2/m))[/math] для ориентированного и [math]O(m + k^2 n \ln (n/k))[/math] неориентированного графа. Проверка свойства [math]k[/math]-связности тем же алгоритмом может быть выполнена за время [math]O(m + n \ln n)[/math].

7 Поиск максимального потока в транспортной сети

7.1 Постановка задачи

Транспортной сетью называется ориентированный граф [math]G = (V, E)[/math], каждому ребру [math]e \in E[/math] которого приписана неотрицательная пропускная способность [math]c(e) \ge 0[/math]. Будем считать, что вместе с каждым ребром [math]e = (v, w) \in E[/math] граф содержит и обратное к нему [math]e^R = (w, v)[/math] (при необходимости приписывая ему нулевую пропускную способность).

Пусть в графе [math]G[/math] выделены две вершины: источник [math]s[/math] и сток [math]t[/math]. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из [math]s[/math] в [math]t[/math]. Потоком называется функция [math]f: E \to \mathbb{R}[/math], удовлетворяющая следующим требованиям:

  • ограничение по пропускной способности: [math]f(e) \le c(e)[/math];
  • антисимметричность: [math]f(e^R) = -f(e)[/math];
  • закон сохранения потока:
[math] \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). [/math]

Величиной потока называется суммарный поток из источника:

[math] \lvert f \rvert = \sum_{e = (s, v)} f(e). [/math]

Задача о максимальном потоке в транспортной сети. Требуется найти поток максимальной величины:

[math]\lvert f \rvert \to \max.[/math]

7.2 Свойства задачи

Суммарный поток из источника равен суммарному потоку в сток:

[math] \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). [/math]

(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

7.3 Варианты задачи

В зависимости от ограничений на значения пропускной способности:

  • произвольная положительная пропускная способность;
  • целая пропускная способность;
  • единичная пропускная способность (в этом случае максимальный поток равен рёберной связности графа).

7.4 Алгоритмы решения задачи

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.

8 Задача о назначениях

8.1 Постановка задачи

Пусть имеется [math]n[/math] агентов и [math]m[/math] задач, которые могут быть распределены между этими агентами. Каждому агенту может быть выделена только одна задача, и каждая задача может быть выделена только одному агенту. Стоимость присвоения [math]i[/math]-й задачи [math]j[/math]-му агенту равна [math]c(i, j)[/math]. В случае [math]c(i, j) = \infty[/math] задача [math]j[/math] не может быть назначена агенту [math]i[/math].

Задача о назначениях: сформировать допустимое множество назначений [math]A = \{ (i_1, j_1), \ldots, (i_k, j_k) \}[/math], [math]k = \min \{m, n\}[/math], имеющее макисмальную суммарную стоимость:

[math] C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max. [/math]

8.2 Варианты задачи

При [math]m = n[/math] задача называется линейной: каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.

В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.

8.3 Алгоритмы решения задачи

  • ↑ 1,0 1,1 1,2 1,3 Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.
  • ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
  • ↑ Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.
  • ↑ Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
  • ↑ Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
  • ↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
  • ↑ Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.
  • ↑ Djidjev, Hristo N, Grammati E Pantziou, and Christos D Zaroliagis. “On-Line and Dynamic Algorithms for Shortest Path Problems.” In Proceedings of STACS 95, 193–204. Lecture Notes in Computer Science Vol. 900, Berlin, Heidelberg: Springer, 1995. doi:10.1007/3-540-59042-0_73.
  • ↑ Demetrescu, Camil, and Giuseppe F Italiano. “Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.” Journal of Computer and System Sciences 72, no. 5 (August 2006): 813–37. doi:10.1016/j.jcss.2005.05.005.
  • ↑ Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.
  • ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  • ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  • ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
  • ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
  • ↑ Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.
  • ↑ Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
  • ↑ Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
  • ↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
  • ↑ Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.
  • ↑ Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.
  • ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
  • ↑ Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.
  • ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.
  • ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
  • ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  • ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  • ↑ Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.
  • ↑ Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.
  • ↑ 29,0 29,1 Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.
  • ↑ Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.
  • ↑ Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (January 1956): 48–50. doi:10.1090/S0002-9939-1956-0078686-7.
  • ↑ Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.
  • ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
  • ↑ Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
  • ↑ Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
  • ↑ Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
  • ↑ Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.
  • ↑ Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.
  • ↑ Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.
  • ↑ Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
  • ↑ Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.
  • ↑ Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.
  • ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
  • ↑ Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.
  • ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.
  • ↑ 46,0 46,1 Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
  • ↑ Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.
  • ↑ McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.
  • ↑ Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.
  • ↑ Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.
  • ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  • ↑ 52,0 52,1 Westbrook, Jeffery, and Robert Endre Tarjan. “Maintaining Bridge-Connected and Biconnected Components on-Line.” Algorithmica 7, no. 1 (June 1992): 433–64. doi:10.1007/BF01758773.
  • ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  • ↑ Henzinger, Monika R, Satish Rao, and Harold N Gabow. “Computing Vertex Connectivity: New Bounds From Old Techniques.” Journal of Algorithms 34, no. 2 (February 2000): 222–50. doi:10.1006/jagm.1999.1055.
  • ↑ Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.
  • ↑ Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.
  • ↑ Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
  • ↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
  • ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.
  • ↑ Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.
  • ↑ Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.
  • ↑ Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.
  • ↑ Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.
  • ↑ Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.
  • ↑ Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.
  • ↑ Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
  • ↑ Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.
  • ↑ Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.
    • Источник — https://algowiki-project.org/w/ru/index.php?title=На_перевод&oldid=2295