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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 22: Строка 22:
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
  
 +
* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
 
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
 
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
  

Версия 02:32, 11 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

  1. Moore, Edward F. “The Shortest Path Through a Maze,” 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.