10.2.2. Алгоритм поиска в ширину.

Алгоритм поиска в ширину работает следующим образом.

Дочерние состояния генерируются правилами вывода, допустимыми ходами иг­ры, или другими операциями перехода состояний. На каждой итерации генерируют­ся все дочерние вершины текущего состояния Х и записываются в open. Заметим, что список open действует как очередь и обрабатывает данные в порядке поступления (или "первым поступил - первым обслужен"). Это структура данных FIFO first-iп-first­out. Состояния добавляются в список справа, а удаляются слева. Таким образом в поиске участвуют состояния, которые находятся в списке open дольше всего, обес­печивая поиск в ширину. Дочерние состояния, которые были уже записаны в списки open или closed, отбрасываются. Алгоритм завершается, если текущее состояние буде равно целевому состоянию. Если алгоритм завершается из-за выполнения условия open= [пусто], то можно заключить, что весь граф исследован, а желаемая цель не достигнута. Следовательно, поиск потерпел неудачу.

Проследим путь алгоритма поиска в ширину breadth_first_search на графе, изображенном на рис. 10.10, при этом U - это желаемое целевое состояние.

0 итерация - Инициализируем списки. Список open =[A]; Список closed =[ ];

1 итерация – Выбираем первую вершину из списка open и определяем её как текущее состояние Х=А. Применяем процедуру определения потомков к Х=А, потомки есть, ими являются вершины В, С, D. Записываем справа налево эти вершины в список open, удаляя слева из этого списка вершину А и записывая эту вершину в список closed слева направо. Далее алгоритм переходит к следующей итерации.

2 итерация – Выбираем первую вершину из списка open и определяем её как текущее состояние Х=В. Применяем процедуру определения потомков к Х= В, потомки есть, ими являются вершины Е, F. Записываем справа налево эти вершины в список open, удаляя слева из этого списка вершину В и записывая эту вершину в список closed слева направо. Далее алгоритм переходит к следующей итерации.

Эти итерации продолжаются до тех пор пока текущее состояние Х не будет равно целевому состоянию U, либо список open окажется пустым.

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

Иногда помимо имен состояний в ореn и closed необходимо хранить дополнительную информацию. Например, заметим, что алгоритм поиска в ширину не поддерживает список состояний на текущем пути к цели, как это делалось при поиске с возвратами (backtrack) в списке SL. Все посещенные состояния хранятся в closed. Если путь является решени­ем, то он возвращается алгоритмом. Это может быть сделано путем накопления инфор­мации о предках для каждого состояния. Состояние хранится вместе с записью роди­тельского состояния, Т.е. в виде пары (потомок- родитель).

После итерации	Список open	Список closed
0	[А]	[ ]
1	[ В С D ]	[А]
2	[С D Е F ]	[В А]
3	[D Е F G Н]	[С В А]
4	[ Е F G Н I J]	[ D С В А]
5	[F G Н I J K L]	[ Е D С В А]
6	[ G Н I J K L M]	[F Е D С В А]
7	[ Н I J K L M N]	[ G F Е D С В А]
8	[I J K L M N O P]	[ Н G F Е D С В А]
9	[J K L M N O PQ]	[ I Н G F Е D С В А]
10	[K L M N O PQ R]	[J I Н G F Е D С В А]
11	[ L M N O PQ R S]	[K J I Н G F Е D С В А]
12	[M N O PQ R S T]	[L K J I Н G F Е D С В А]
13	[N O PQ R S T]	[ M L K J I Н G F Е D С В А]
14	[O PQ R S T]	[ N M L K J I Н G F Е D С В А]
15	[PQ R S T]	[ O N M L K J I Н G F Е D С В А]
16	[Q R S TU ]	[P O N M L K J I Н G F Е D С В А]
17	[R S TU ]	[ Q P O N M L K J I Н G F Е D С В А]
18	[S TU ]	[ R Q P O N M L K J I Н G F Е D С В А]
19	[TU ]	[ S R Q P O N M L K J I Н G F Е D С В А]
20	[U ]	[ T S R Q P O N M L K J I Н G F Е D С В А]

Таблица 10.2. Состояние списков после каждой итерации алгоритма поиска в ширину для графа на рис. 10.10.

После итерации	Список пар (потомок-родитель).
0
1	(B,A), (C,A), (D,A)
2	(B,A), (C,A), (D,A), (E,B), (F,B)
3	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C)
4	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D)
5	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E)
6	(B,A),(C,A),(D,A),(E,B),(F,B),(G,C),(H,C),(I,D),(J,D),(K,E),(L,E),(L,F), (M,F)
7	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G)
8	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H)
9	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I)
10	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J)
11	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K)
12	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L)
13	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L)
14	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L)
15	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),( N, G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L)
16	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),(N,G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L),(U,P)
17	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),(N,G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L),(U,P)
18	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),(N,G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L),(U,P)
19	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),(N,G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L),(U,P)
20	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E), (L,F), (M,F),(N,G),(O,H), (P,H),(P,I),(Q,I), (R,J),(S,K),(T,L),(U,P)

Таблица 10.3. Состояние списка пар (потомок-родитель) после каждой итерации алгоритма поиска в ширину для графа на рис. 10.10.

Используя эту информацию, можно легко построить путь (А, В, F), ведущий от А к F. Когда цель найдена, можно создать алгоритм, который может восстановить путь решения, прослеживая его в об­ратном направлении от цели к начальному состоянию по родительским состояниям.