Поиск в ширину (BFS): различия между версиями

[непроверенная версия]

Версия от 19:04, 11 июня 2015

Свойства и структура алгоритмов

Поиск в ширину (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Алгоритм решает задачу поиска кратчайшего пути на графе в случае одинаковых весов рёбер. Впервые алгоритм поиска в ширину описан в работах Мура^[1] и Ли^[2].

Общее описание алгоритма

Математическое описание

Вычислительное ядро алгоритма

Макроструктура алгоритма

Описание схемы реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Описание ресурса параллелизма алгоритма

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

Свойства алгоритма

Программная реализация алгоритмов

Особенности реализации последовательного алгоритма

Описание локальности данных и вычислений

Возможные способы и особенности реализации параллельного алгоритма

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка Graph500.
C++: Boost Graph Library (функции breadth_first_search, breadth_first_visit).
C++, MPI: Parallel Boost Graph Library (функция breadth_first_search).
Java: WebGraph (класс ParallelBreadthFirstVisit), многопоточная реализация.

Литература

↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
↑ Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.

[1] Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.

[2] Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.

[1]

[2]

@@ Строка 1: / Строка 1: @@
 == Свойства и структура алгоритмов ==
-'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Алгоритм решает [[Поиск кратчайшего пути от одной вершины (SSSP)|задачу поиска кратчайшего пути на графе]] в случае одинаковых весов рёбер. Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” 285–92, 1959.</ref> и Ли<ref>Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.</ref>.
+'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Алгоритм решает [[Поиск кратчайшего пути от одной вершины (SSSP)|задачу поиска кратчайшего пути на графе]] в случае одинаковых весов рёбер. Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> и Ли<ref>Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.</ref>.
 === Общее описание алгоритма ===