Лекция: Алгоритм поиска в ширину.

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

Дочерние состояния генерируются правилами вывода, допустимыми ходами иг­ры, или другими операциями перехода состояний. На каждой итерации генерируют­ся все дочерние вершины текущего состояния Х и записываются в 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. Если путь является решени­ем, то он возвращается алгоритмом. Это может быть сделано путем накопления инфор­мации о предках для каждого состояния. Состояние хранится вместе с записью роди­тельского состояния, Т.е. в виде пары (потомок- родитель).

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

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

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