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

Patarakin в 16:10, 4 января 2023

2023-01-04T16:10:17Z

← Предыдущая версия		Версия от 19:10, 4 января 2023
Строка 1:		Строка 1:
	{{Scripting Tutorials		{{Scripting Tutorials
	\|Description='''Поиск в ширину''' ('''BFS''') — один из методов обхода графа. Пусть задан граф G = (V, E) и выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество рёбер) от s до каждой достижимой из sвершины.		\|Description='''Поиск в ширину''' ('''BFS''') — один из методов обхода графа.
	\|Field_of_knowledge=Информатика		\|Field_of_knowledge=Информатика
	\|Возрастная категория=14		\|Возрастная категория=14
Строка 6:		Строка 6:
	https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif		https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif

			Пусть задан граф G = (V, E) и выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество рёбер) от s до каждой достижимой из sвершины.

	Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.		Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.

Patarakin: /* Временная сложность */

2023-01-04T16:06:24Z

Временная сложность

← Предыдущая версия		Версия от 19:06, 4 января 2023
Строка 97:		Строка 97:

	=== Временная сложность ===		=== Временная сложность ===
	Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков [[Матрица смежности\|смежности]], [[временная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math>~~<ref name="emaxx" /><ref name="nstu" />.~~		Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков [[Матрица смежности\|смежности]], [[временная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math>

	=== Полнота ===		=== Полнота ===

Patarakin: /* Пространственная сложность */

2023-01-04T16:05:50Z

Пространственная сложность

← Предыдущая версия		Версия от 19:05, 4 января 2023
Строка 92:		Строка 92:

	=== Пространственная сложность ===		=== Пространственная сложность ===
	Так как в памяти хранятся все развёрнутые узлы, [[пространственная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math>~~<ref name="emaxx" />.~~		Так как в памяти хранятся все развёрнутые узлы, [[пространственная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math>

	Алгоритм [[IDDFS\|поиска с итеративным углублением]] похож на поиск в ширину тем, что при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов, но требует значительно меньше памяти.		Алгоритм [[IDDFS\|поиска с итеративным углублением]] похож на поиск в ширину тем, что при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов, но требует значительно меньше памяти.

Patarakin в 17:05, 15 декабря 2022

2022-12-15T17:05:49Z

← Предыдущая версия		Версия от 20:05, 15 декабря 2022
Строка 1:		Строка 1:
	'''Поиск в ширину''' ('''BFS''') — один из методов обхода ~~[[Граф (математика)\|~~графа]]. Пусть задан граф ~~<math>~~G = (V, E)~~</math>~~ и выделена исходная вершина ~~<math>~~s~~</math>~~. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из ~~<math>~~s~~</math>~~, вычисляя при этом расстояние (минимальное количество рёбер) от ~~<math>~~s~~</math>~~ до каждой достижимой из ~~<math>s</math> вершины~~.		{{Scripting Tutorials
			\|Description='''Поиск в ширину''' ('''BFS''') — один из методов обхода графа. Пусть задан граф G = (V, E) и выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество рёбер) от s до каждой достижимой из sвершины.
			\|Field_of_knowledge=Информатика
			\|Возрастная категория=14
			}}
	https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif		https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif

Строка 9:		Строка 12:

	== Работа алгоритма ==		== Работа алгоритма ==
	Поиск в ширину работает путём последовательного просмотра отдельных ''уровней'' [[Граф (математика)\|графа]], начиная с узла-источника ~~<math>~~u~~</math>.~~		Поиск в ширину работает путём последовательного просмотра отдельных ''уровней'' [[Граф (математика)\|графа]], начиная с узла-источника u


	Рассмотрим все [[Ребро (теория графов)\|рёбра]] <math>(u,v)</math>, выходящие из [[Узел (теория графов)\|узла]] <math>u</math>. Если очередной узел <math>v</math> является целевым узлом, то поиск завершается; в противном случае узел <math>v</math> добавляется в [[Очередь (программирование)\|очередь]]. После того, как будут проверены все рёбра, выходящие из узла <math>u</math>, из очереди извлекается следующий узел <math>u</math>, и процесс повторяется.

	== Неформальное описание ==		== Неформальное описание ==

Patarakin в 17:02, 15 декабря 2022

2022-12-15T17:02:54Z

← Предыдущая версия		Версия от 20:02, 15 декабря 2022
Строка 61:		Строка 61:

	Реализация на [[Pascal]]:		Реализация на [[Pascal]]:
			<syntaxhighlight lang="pascal" line="1">

	~~<source lang="pascal">~~
	function BFS(v : Node) : Boolean;		function BFS(v : Node) : Boolean;
	begin		begin
Строка 83:		Строка 83:
	BFS := false;		BFS := false;
	end;		end;
	</~~source~~>		</syntaxhighlight>

	== Свойства ==		== Свойства ==
Строка 107:		Строка 107:

	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
			[[Category:Scripting Tutorials]]

Patarakin в 08:16, 20 октября 2022

2022-10-20T08:16:50Z

← Предыдущая версия		Версия от 11:16, 20 октября 2022
Строка 1:		Строка 1:
	'''Поиск в ширину''' ('''BFS''') — один из методов обхода [[Граф (математика)\|графа]]. Пусть задан граф <math>G = (V, E)</math> и выделена исходная вершина <math>s</math>. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из <math>s</math>, вычисляя при этом расстояние (минимальное количество рёбер) от <math>s</math> до каждой достижимой из <math>s</math> вершины.		'''Поиск в ширину''' ('''BFS''') — один из методов обхода [[Граф (математика)\|графа]]. Пусть задан граф <math>G = (V, E)</math> и выделена исходная вершина <math>s</math>. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из <math>s</math>, вычисляя при этом расстояние (минимальное количество рёбер) от <math>s</math> до каждой достижимой из <math>s</math> вершины.

			https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif


	Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.		Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.

Строка 99:		Строка 103:

	[[Поиск по критерию стоимости]] является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует [[Очередь с приоритетом (программирование)\|очередь с приоритетами]].		[[Поиск по критерию стоимости]] является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует [[Очередь с приоритетом (программирование)\|очередь с приоритетами]].

			----

	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]

Patarakin в 18:21, 19 октября 2022

2022-10-19T18:21:23Z

← Предыдущая версия		Версия от 21:21, 19 октября 2022
Строка 2:		Строка 2:
	Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.		Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.

	Поиск в ширину является одним из [[Неинформированный алгоритм поиска\|неинформированных алгоритмов поиска]]~~<ref name="emaxx" />~~.		Поиск в ширину является одним из [[Неинформированный алгоритм поиска\|неинформированных алгоритмов поиска]].

	== Работа алгоритма ==		== Работа алгоритма ==

Patarakin в 18:21, 19 октября 2022

2022-10-19T18:21:01Z

@@ Строка 1: / Строка 1: @@
-{{другие значения|BFS}}
+'''Поиск в ширину''' ('''BFS''') — один из методов обхода [[Граф (математика)|графа]]. Пусть задан граф <math>G = (V, E)</math> и выделена исходная вершина <math>s</math>. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из <math>s</math>, вычисляя при этом расстояние (минимальное количество рёбер) от <math>s</math> до каждой достижимой из <math>s</math> вершины.
 Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.
@@ Строка 9: / Строка 5: @@
 == Работа алгоритма ==
 Поиск в ширину работает путём последовательного просмотра отдельных ''уровней'' [[Граф (математика)|графа]], начиная с узла-источника <math>u</math>.
@@ Строка 105: / Строка 100: @@
 [[Поиск по критерию стоимости]] является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует [[Очередь с приоритетом (программирование)|очередь с приоритетами]].
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:55:02Z

1 версия импортирована

← Предыдущая версия	Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>InternetArchiveBot: Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

2022-07-26T05:09:17Z

Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

Новая страница

{{другие значения|BFS}}
[[Файл:Breadth-First-Search-Algorithm.gif|thumb|Поиск в ширину]]

'''Поиск в ширину''' ({{lang-en|breadth-first search}}, '''BFS''') — один из методов обхода [[Граф (математика)|графа]]. Пусть задан граф <math>G = (V, E)</math> и выделена исходная вершина <math>s</math>. Алгоритм поиска в ширину систематически обходит все ребра <math>G</math> для «открытия» всех вершин, достижимых из <math>s</math>, вычисляя при этом расстояние (минимальное количество рёбер) от <math>s</math> до каждой достижимой из <math>s</math> вершины. Алгоритм работает как для [[Ориентированный граф|ориентированных]], так и для неориентированных графов.<ref>{{Книга|автор=Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн|заглавие=Алгоритмы: построение и анализ|ответственный=|издание=3-е изд|место=|издательство=Издательский дом "Вильямс"|год=2013|страницы=630|страниц=1328|isbn=978-5-8459-1794-2 (рус.)|isbn2=978-0-2620-3384-8 (англ.)}}</ref>

Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии <math>k + 1</math>, выполняется обход вершин на расстоянии <math>k</math>.

Поиск в ширину является одним из [[Неинформированный алгоритм поиска|неинформированных алгоритмов поиска]]<ref name="emaxx" />.

== Работа алгоритма ==
[[Файл:Animated BFS.gif|thumb|Белый — вершина, которая ещё не обнаружена. Серый — вершина, уже обнаруженная и добавленная в очередь. Чёрный — вершина, извлечённая из очереди<ref name="nstu" />.]]
Поиск в ширину работает путём последовательного просмотра отдельных ''уровней'' [[Граф (математика)|графа]], начиная с узла-источника <math>u</math>.

Рассмотрим все [[Ребро (теория графов)|рёбра]] <math>(u,v)</math>, выходящие из [[Узел (теория графов)|узла]] <math>u</math>. Если очередной узел <math>v</math> является целевым узлом, то поиск завершается; в противном случае узел <math>v</math> добавляется в [[Очередь (программирование)|очередь]]. После того, как будут проверены все рёбра, выходящие из узла <math>u</math>, из очереди извлекается следующий узел <math>u</math>, и процесс повторяется.

== Неформальное описание ==
# Поместить узел, с которого начинается поиск, в изначально пустую очередь.
# Извлечь из начала очереди узел <math>u</math> и пометить его как развёрнутый.
#* Если узел <math>u</math> является целевым узлом, то завершить поиск с результатом «успех».
#* В противном случае, в конец очереди добавляются все преемники узла <math>u</math>, которые ещё не развёрнуты и не находятся в очереди.
# Если очередь пуста, то все узлы [[Связный граф|связного графа]] были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
# Вернуться к п. 2.
Примечание: деление вершин на развёрнутые и не развёрнутые необходимо для произвольного графа (так как в нём могут быть циклы). Для [[Дерево (теория графов)|дерева]] эта операция не нужна, так как каждая вершина будет выбрана один-единственный раз.

== Формальное описание ==
Ниже приведён [[Псевдокод (язык описания алгоритмов)|псевдокод]] алгоритма для случая, когда необходимо лишь найти целевой узел. В зависимости от конкретного применения алгоритма, может потребоваться дополнительный код, обеспечивающий сохранение нужной информации (расстояние от начального узла, узел-родитель и т. п.)

Рекурсивная формулировка:
BFS(''start_node'', ''goal_node'') {
'''return''' BFS'({''start_node''}, ∅, ''goal_node'');
}
BFS'(''fringe'', ''visited'', ''goal_node'') {
'''if'''(''fringe'' == ∅) {
// Целевой узел не найден
'''return''' false;
}
'''if''' (''goal_node'' ∈ ''fringe'') {
'''return''' true;
}
'''return''' BFS'({''child'' | ''x'' ∈ ''fringe'', ''child'' ∈ expand(''x'')} \ ''visited'', ''visited'' ∪ ''fringe'', ''goal_node'');
}

Итеративная формулировка:
BFS(''start_node'', ''goal_node'') {
'''for'''(all nodes i) ''visited''[''i''] = false; // изначально список посещённых узлов пуст
''queue''.push(''start_node''); // начиная с узла-источника
''visited''[''start_node''] = true;
'''while'''(! ''queue''.empty() ) { // пока очередь не пуста
''node'' = ''queue''.pop(); // извлечь первый элемент в очереди
'''if'''(''node'' == ''goal_node'') {
'''return''' true; // проверить, не является ли текущий узел целевым
}
'''foreach'''(''child'' '''in''' expand(''node'')) { // все преемники текущего узла, ...
'''if'''(visited[''child''] == false) { // ... которые ещё не были посещены ...
''queue''.push(''child''); // ... добавить в конец очереди...
''visited''[''child''] = true; // ... и пометить как посещённые
}
}
}
'''return''' false; // Целевой узел недостижим
}

Реализация на [[Pascal]]:

<source lang="pascal">
function BFS(v : Node) : Boolean;
begin
enqueue(v);
while queue is not empty do
begin
curr := dequeue();
if is_goal(curr) then
begin
BFS := true;
exit;
end;
mark(curr);
for next in successors(curr) do
if not marked(next) then
begin
enqueue(next);
end;
end;
BFS := false;
end;
</source>

== Свойства ==
Обозначим число вершин и рёбер в графе как <math> \vert V \vert </math> и <math> \vert E \vert </math> соответственно.

=== Пространственная сложность ===
Так как в памяти хранятся все развёрнутые узлы, [[пространственная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math><ref name="emaxx" />.

Алгоритм [[IDDFS|поиска с итеративным углублением]] похож на поиск в ширину тем, что при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов, но требует значительно меньше памяти.

=== Временная сложность ===
Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков [[Матрица смежности|смежности]], [[временная сложность]] алгоритма составляет <math>O(\vert V \vert + \vert E \vert)</math><ref name="emaxx" /><ref name="nstu" />.

=== Полнота ===
Если у каждого узла имеется конечное число преемников, алгоритм является полным: если решение существует, алгоритм поиска в ширину его находит, независимо от того, является ли граф конечным. Однако если решения не существует, на бесконечном графе поиск не завершается.

=== Оптимальность ===
Если длины рёбер графа равны между собой, поиск в ширину является оптимальным, то есть всегда находит кратчайший путь. В случае [[Взвешенный граф|взвешенного графа]] поиск в ширину находит путь, содержащий минимальное количество рёбер, но не обязательно кратчайший.

[[Поиск по критерию стоимости]] является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует [[Очередь с приоритетом (программирование)|очередь с приоритетами]].

== История и применения ==
Поиск в ширину был формально предложен [[Мур, Эдвард Форест|Э. Ф. Муром]] в контексте поиска пути в лабиринте<ref name="moore1959" />. Ли независимо открыл тот же алгоритм в контексте [[Алгоритм Ли|разводки проводников на печатных платах]]<ref name="lee1961" /><ref>Cormen ''et al'', Introduction to Algorithms, 3rd edition, p. 623</ref><ref name="se_origin" />.

Поиск в ширину может применяться для решения задач, связанных с [[Теория графов|теорией графов]]:
* [[Волновой алгоритм]] [[Поиск пути|поиска пути]] в лабиринте<ref name="moore1959" />
* Волновая [[трассировка печатных плат]]<ref name="lee1961" />
* Поиск [[Компонента связности графа|компонент связности]] в графе
* [[Задача о кратчайшем пути|Поиск кратчайшего пути]] между двумя узлами невзвешенного графа
* [[Поиск в пространстве состояний]]: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа<ref name="emaxx" />
* Нахождение кратчайшего цикла в ориентированном невзвешенном графе<ref name="emaxx" />
* Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами <math>a</math> и <math>b</math><ref name="emaxx" />
* Поиск увеличивающего пути в [[Форда-Фалкерсона алгоритм|алгоритме Форда-Фалкерсона]] ([[алгоритм Эдмондса-Карпа]])

== См. также ==
{{wikibooks|Реализации алгоритмов/Поиск в ширину|Примеры реализации поиска в ширину}}
* [[Поиск с ограничением глубины]]

== Примечания ==
{{примечания|1|refs=
<ref name="emaxx">MAXimal :: algo :: [http://e-maxx.ru/algo/bfs Поиск в ширину в графе и его приложения] {{Wayback|url=http://e-maxx.ru/algo/bfs |date=20130916134130 }}</ref>
<ref name="nstu">НГТУ Структуры и алгоритмы обработки данных [http://edu.nstu.ru/courses/saod/bfs.htm Обход графа в ширину] {{Wayback|url=http://edu.nstu.ru/courses/saod/bfs.htm |date=20121230194547 }}</ref>
<ref name="moore1959">{{source|Q28048674|ref=Moore|ref-year=1959}} </ref>
<ref name="lee1961">C. Y. Lee (1961), [https://dx.doi.org/10.1109/TEC.1961.5219222 An algorithm for path connection and its applications]. ''IRE Transactions on Electronic Computers'', EC-10(3), pp. 346–365</ref>
<ref name="se_origin">''Mathematics Stack Exchange'' [http://math.stackexchange.com/questions/283914/ Origin of the Breadth-First Search algorithm]</ref>
}}

== Литература ==
* {{книга
| автор = T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
| заглавие = Introduction to Algorithms
| издание = 3rd edition
| издательство = The MIT Press
| год = 2009
| isbn = 978-0-262-03384-8
}}. Перевод 2-го издания: {{книга
|автор = Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
|заглавие = '''Алгоритмы: построение и анализ'''
|оригинал = Introduction to Algorithms
|ссылка =
|издание = 2-е изд
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы = 1296
|isbn = 0-07-013151-1
}}
* {{source|Q21694522|part=Глава 5. Метод уменьшения размера задачи: Поиск в ширину}}

== Ссылки ==
{{Навигация}}
* ''Steven M. Rubin'' [http://www.rulabinsky.com/cavd/text/chap04-3.html Computer Aids for VLSI Design. Chapter 4: Synthesis Tools]
* [http://100byte.ru/100btwrks/wv/wv.html Волновой алгоритм поиска пути]
* [http://kvodo.ru/search-width.html Поиск в ширину на Pascal и C++]

{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы поиска на графах]]
[[Категория:Алгоритмы поиска]]