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

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

Дочерние состояния генерируются правилами вывода, допустимыми ходами иг­ры, или другими операциями перехода состояний. На каждой итерации генерируют­ся все дочерние вершины текущего состояния Х и записываются в 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
	[ А ]	[ ]
	[ В С D ]	[ А ]
	[ С D Е F ]	[ В А ]
	[ D Е F G Н ]	[ С В А ]
	[ Е F G Н I J ]	[ D С В А ]
	[ F G Н I J K L ]	[ Е D С В А ]
	[ G Н I J K L M ]	[ F Е D С В А ]
	[ Н I J K L M N ]	[ G F Е D С В А ]
	[ I J K L M N O P ]	[ Н G F Е D С В А ]
	[ J K L M N O PQ ]	[ I Н G F Е D С В А ]
	[ K L M N O PQ R ]	[ J I Н G F Е D С В А ]
	[ L M N O PQ R S ]	[ K J I Н G F Е D С В А ]
	[ M N O PQ R S T ]	[ L K J I Н G F Е D С В А ]
	[ N O PQ R S T ]	[ M L K J I Н G F Е D С В А ]
	[ O PQ R S T ]	[ N M L K J I Н G F Е D С В А ]
	[ PQ R S T ]	[ O N M L K J I Н G F Е D С В А ]
	[ Q R S TU ]	[ P O N M L K J I Н G F Е D С В А ]
	[ R S TU ]	[ Q P O N M L K J I Н G F Е D С В А ]
	[ S TU ]	[ R Q P O N M L K J I Н G F Е D С В А ]
	[ TU ]	[ S R Q P O N M L K J I Н G F Е D С В А ]
	[ U ]	[ T S R Q P O N M L K J I Н G F Е D С В А ]

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

После итерации	Список пар (потомок-родитель).
	(B,A), (C,A), (D,A)
	(B,A), (C,A), (D,A), (E,B), (F,B)
	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C)
	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D)
	(B,A), (C,A), (D,A), (E,B), (F,B), (G,C), (H,C), (I,D),(J,D),(K,E), (L,E)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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)
	(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. Когда цель найдена, можно создать алгоритм, который может восстановить путь решения, прослеживая его в об­ратном направлении от цели к начальному состоянию по родительским состояниям.