Поиск в ширину (BFS) - История изменений

ASA: /* Программная реализация алгоритма */

2022-07-01T07:59:43Z

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

← Предыдущая версия		Версия от 07:59, 1 июля 2022
Строка 167:		Строка 167:
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
			=== Результаты прогонов ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

ASA: /* Программная реализация алгоритма */

2022-06-28T13:24:48Z

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

@@ Строка 166: / Строка 166: @@
 == Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
 === Возможные способы и особенности параллельной реализации алгоритма ===
 === Выводы для классов архитектур ===
 == Литература ==

Apaokin в 11:11, 19 июня 2018

2018-06-19T11:11:50Z

← Предыдущая версия		Версия от 11:11, 19 июня 2018
Строка 179:		Строка 179:

	* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].		* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
			** MPI: {{Buttonlinkimp\|12}}
	* C++: [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/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).		* C++: [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/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).{{Buttonlinkimp\|11}}
	* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.		* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).
	* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).
			* RCC for CPU {{Buttonlinkimp\|9}}
			* RCC for GPU {{Buttonlinkimp\|26}}
			* Gap {{Buttonlinkimp\|36}}
			* Litra {{Buttonlinkimp\|39}}
	== Литература ==		== Литература ==

Ikramov: /* Ресурс параллелизма алгоритма */

2017-11-16T12:54:29Z

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

← Предыдущая версия		Версия от 12:54, 16 ноября 2017
Строка 147:		Строка 147:
	В ходе работы классический вариант алгоритма обходит граф по слоям. В каждый слой добавляются еще не посещенные вершины, достижимые из вершин предыдущего слоя. Обход вершин каждого слоя, как и их соседей, может производиться параллельно. Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа. Аналогично невозможно оценить число шагов алгоритма, за которое будут найдены все кратчайшие пути.		В ходе работы классический вариант алгоритма обходит граф по слоям. В каждый слой добавляются еще не посещенные вершины, достижимые из вершин предыдущего слоя. Обход вершин каждого слоя, как и их соседей, может производиться параллельно. Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа. Аналогично невозможно оценить число шагов алгоритма, за которое будут найдены все кратчайшие пути.

	Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при ~~том~~ для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме, и может быть оценена только сверху (не более <math>\|V\|</math>).		Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более <math>\|V\|</math>).

	При квадратичном подходе к параллельной реализации алгоритма на каждом шаге ~~алгоритма~~ выполняется <math>O(\|E\|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(\|E\|)</math>. Число шагов алгоритма как и в классическом случае зависит от структуры графа, и может быть оценено сверху как <math>O(\|V\|)</math>.		При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется <math>O(\|E\|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(\|E\|)</math>. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как <math>O(\|V\|)</math>.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Ikramov: /* Информационный граф */

2017-11-16T10:05:11Z

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

← Предыдущая версия		Версия от 10:05, 16 ноября 2017
Строка 137:		Строка 137:
	[1] - инициализация расстояний до вершины-источника		[1] - инициализация расстояний до вершины-источника

	[2] - ~~инициалищация~~ расстояний до остальных вершин графа		[2] - инициализация расстояний до остальных вершин графа

	[3] - загрузка информации об очередном ребре и ~~обновления~~ дистанций до соответствующих вершин.		[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.

	[4] - проверка ~~условий~~ выхода из цикла		[4] - проверка условия выхода из цикла

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

Ikramov: /* Информационный граф */

2017-11-16T10:02:45Z

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

← Предыдущая версия		Версия от 10:02, 16 ноября 2017
Строка 129:		Строка 129:
	[6] - проверка условия выхода из цикла		[6] - проверка условия выхода из цикла

	Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math> невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.		Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math>, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.

	[[Файл:quadratic_BFS_ig.png\|thumb\|center\|500px\|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]		[[Файл:quadratic_BFS_ig.png\|thumb\|center\|500px\|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]

Ikramov: /* Информационный граф */

2017-11-16T09:11:33Z

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

← Предыдущая версия		Версия от 09:11, 16 ноября 2017
Строка 107:		Строка 107:
	[4] - добавление еще не посещенных вершин в множество <math>P</math>.		[4] - добавление еще не посещенных вершин в множество <math>P</math>.

	[5] - замена множества <math>F</math> на <math>P</math> и проверка его пустоты. В случае ~~негустого~~ множества - переход на следующую итерацию, иначе завершение работы алгоритма.		[5] - замена множества <math>F</math> на <math>P</math> и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.

	Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, ~~моделирующих~~ данное множество.		Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.

	В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.		В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.

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

2017-11-15T16:32:50Z

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

← Предыдущая версия		Версия от 16:32, 15 ноября 2017
Строка 30:		Строка 30:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

	Вычислительным ядром алгоритма является обход вершин, ~~смежной к~~ выбранной ~~вершине~~ <math>v</math> с ~~последующем~~ добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция ~~выполняться~~ на каждом шаге для каждой вершины <math>v \in F</math>.		Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной <math>v</math>, с последующим добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняется на каждом шаге для каждой вершины <math>v \in F</math>.

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

Ikramov: /* Математическое описание алгоритма */

2017-11-15T15:56:54Z

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

← Предыдущая версия		Версия от 15:56, 15 ноября 2017
Строка 24:		Строка 24:
	Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа описанным далее образом.		Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа описанным далее образом.

	В начале работы алгоритма расстояние до вершины-источника <math>d(u)=0</math>, до остальных вершин <math>d(v) = \infty, \forall v \neq u </math>. ~~Так же~~ в начале работы ~~алгоритм инициализируются~~ множество <math>F = \{u\}</math>.		В начале работы алгоритма расстояние до вершины-источника <math>d(u)=0</math>, до остальных вершин <math>d(v) = \infty, \forall v \neq u </math>. Также в начале работы алгоритма инициализируется множество <math>F = \{u\}</math>.

	Далее на каждом шаге ~~алгоритм~~ строится множество вершин <math>P = {w} </math>, таких, что для <math>\forall v \in F \exists (v, w) \in E \| d(w) = \infty </math>, при ~~том~~ обновляются расстояния <math>d(w)=d(v)+1</math> для <math>\forall w \in P </math>. Затем производится переход на следующий шаг до тех пор, пока <math>P \neq \emptyset</math>, при ~~том~~ в начале каждого шага множество F заменяется на P.		Далее на каждом шаге алгоритма строится множество вершин <math>P = {w} </math>, таких, что для <math>\forall v \in F \exists (v, w) \in E \| d(w) = \infty </math>, при этом обновляются расстояния <math>d(w)=d(v)+1</math> для <math>\forall w \in P </math>. Затем производится переход на следующий шаг до тех пор, пока <math>P \neq \emptyset</math>; при этом в начале каждого шага множество F заменяется на P.

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

ASA в 13:23, 13 ноября 2017

2017-11-13T13:23:33Z

← Предыдущая версия		Версия от 13:23, 13 ноября 2017
Строка 189:		Строка 189:
	<references />		<references />

	[[Категория:~~Начатые статьи~~]]		[[Категория:Статьи в работе]]

			[[En:Breadth-first search (BFS)]]