PDF-лекции, страница 13

Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в списокраскрытых вершин Closed.Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет,то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open ипостроить указатели, ведущие от этих вершин к родительской вершине Current.Шаг 5. Проверить, нет ли среди дочерних вершин целевых.

Если есть хотя бы одна целевая вершина, тоокончание алгоритма и выдача решения задачи, получающегося просмотром указателей назад отнайденной целевой вершины к начальной. В противном случае перейти к шагу 2.Конец алгоритма.Основу этого алгоритма составляет цикл последовательного раскрытия (шаги 2-5) концевыхвершин (листьев) дерева перебора, хранящихся в списке Open. Алгоритм поиска вширь являетсяполным. Можно также показать, что при переборе вширь непременно будет найден самый короткийпуть к целевой вершине, причем быстрее, чем другие решающие пути – при условии, что этот путьвообще существует.

Если же решающего пути нет, то (в случае конечных деревьев-пространств) будетсообщено о неуспехе поиска, в случае же бесконечных пространств алгоритм не кончит свою работу.На рис. 5 приведено дерево, построенное в результате применения алгоритма поиска вширь кнекоторой начальной конфигурации игры в восемь, причем выполнение алгоритма прервано послепостроения первых 12 вершин (при этом раскрыто 6 вершин). В вершинах дерева помещенысоответствующие описания состояний. Эти вершины занумерованы в том порядке, в котором они были42построены в ходе поиска.

На следующем шаге цикла алгоритма будет раскрываться одна из вершин сномерами 6, 7 или 8, поскольку они расположены в начале списка нераскрытых вершин.Рис.512 8 31 6 47 542 8 31 6 47 522 8 31 6 47 5510362 8 3147 6 5782 8 3 2 8 3 2 8 3 231 6 1 4 1 4 1 8 47 5 4 7 6 5 7 6 5 7 6 52 8 36 41 7 590112 8 3  8 3 12 8 36 4 2 6 4 1 61 7 5 1 7 5 7 5 4122 81 6 37 5 4Считаем, что порядок построения дочерних вершин соответствует следующемузафиксированному порядку перемещения пустой клетки («пустышки»): влево/вправо/вверх/вниз.Предполагается также, что используемая алгоритмом операция раскрытия вершин организована такимобразом, что она не порождает никакое состояние-вершину, построенную ранее и являющуюсяродительской для раскрываемой вершины.

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

Но в случае поиска на произвольном графе (и в этом – отличие от деревьев-пространств) однои тоже состояние может быть продублировано в разных частях полученного дерева перебора. В примереигры в восемь по принятому предположению об операции раскрытия исключалось только повторноевозникновение состояний, встречавшихся два шага вверх по дереву перебора, другие же, более далекиедруг от друга повторы одного и того же состояния остаются возможными. В случае поиска в графесостояний общего вида он как бы разворачивается при поиске в дерево путем дублирования некоторыхего частей. Если это дублирование неоднократное (из-за циклов в графе), то оно может привести кзацикливанию базового алгоритма поиска вширь.Перебор вглубьДля формулировки алгоритма поиска вглубь необходимо определить понятие глубины вершиныв дереве поиска.

Это можно сделать следующим образом: глубина корня дерева равна нулю; глубина каждой некорневой вершины на единицу больше глубины ее родительской вершины.В алгоритме перебора вглубь раскрытию в первую очередь подлежит вершина, имеющаянаибольшую глубину. Такой принцип может привести к бесконечному процессу – это происходит, еслипространство состояний бесконечно, и поиск вглубь пошел по ветви дерева, не содержащей целевуювершину. Поэтому необходимо то или иное ограничение этого процесса, самый распространенныйспособ – ограничить глубину просмотра дерева. Это означает, что в ходе перебора можно строитьтолько вершины, глубина которых не превышает некоторую заданную граничную глубину.

Тем самым,раскрытию в первую очередь подлежит вершина наибольшей глубины, но расположенная вышефиксированной границы. Соответствующий алгоритм поиска называется ограниченным переборомвглубь.43Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной D)таковы:Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open. Установить ее глубину (0).Шаг 2.

Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, впротивном случае перейти к следующему шагу.Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в списокраскрытых вершин Closed.Шаг 4. Если глубина вершины Current равна граничной глубине D, то перейти к шагу 2, в иномслучае перейти к следующему шагу.Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины.

Если дочерних вершин нет, топерейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке; с указанием ихглубины) в начало списка Open и построить указатели, ведущие от этих вершин к родительскойвершине Current.Шаг 6. Если среди дочерних есть хотя бы одна целевая вершина, то окончание алгоритма и выдачарешения задачи, получающегося просмотром указателей от найденной целевой вершины к начальной. Впротивном случае перейти к шагу 2.Конец алгоритма.Приведенное только что описание очень похоже на описание алгоритма поиска вглубь, разницазаключается только в ограничении глубины (шаг 4) и в месте списка Open, куда помещаютсяпостроенные дочерние вершины (шаг 5).Поскольку глубина поиска ограничена, то будучи примененным к деревьям-пространствамсостояний, описанный базовый алгоритм поиска вглубь всегда заканчивает работу.

Но в отличие оталгоритма поиска вширь, он является неполным алгоритмом, поскольку вершины пространствасостояний, расположенные ниже граничной глубины, среди которых могут быть и целевые, так иостанутся нерассмотренными.На рис. 6 показано дерево перебора, построенное алгоритмом поиска вглубь; граничная глубинаустановлена равной 4.

В качестве начального состояния взята та же самая, что и в примере на рис. 5,конфигурация игры в восемь. Вершины занумерованы в том порядке, в котором они были построены. Входе поиска раскрыто 7 и построено 12 вершин, но, как нетрудно убедиться, сравнивая последние дварисунка, в целом это не те же самые 12 первых вершин, построенных алгоритмом поиска вширь.Видно, что в алгоритме поиска в глубину сначала идет поиск вдоль одного пути, пока не будетдостигнута установленная граничная глубина, затем рассматриваются альтернативные пути той же илименьшей глубины, которые отличаются от первого пути лишь последней (концевой) вершиной, послечего рассматриваются пути, отличающиеся последними двумя вершинами, и т.д.Рис.632 8 36 41 7 502 8 31 6 47 512 8 31 6 47 552 8 31 6 47 592 8 3147 6 522 8 36 41 7 562 8 31 67 5 4102 8 31 47 6 548 32 6 41 7 572 8 3167 5 48112 8 8 31 6 3 2 1 47 5 4 7 6 5122 8 37 1 46 544Анализ слепых алгоритмов. БэктрекингЕсли продолжить выполнение алгоритмов перебора вширь и вглубь для рассмотренногоначального состояния игры в восемь (для задачи, указанной на рис.1(б)), то на глубине 5 будет найденацелевая конфигурация.

При этом алгоритмом поиска вширь будет раскрыто 26 и построено 46 вершин, аалгоритмом поиска вглубь – соответственно 18 и 35 вершин.Сравнивая в общем алгоритмы поиска вширь и вглубь, можно утверждать, что они примерносравнимы по эффективности (количеству построенных вершин). Но в ряде случаев второй алгоритм,несмотря на свою неполноту, может оказаться предпочтительнее: если он начат с удачной стороны, тоцелевая вершина будет обнаружена раньше, чем в алгоритме поиска вширь.Подчеркнем, что как и в случае перебора вширь, при переборе вглубь формируется именнодерево, а не граф перебора, даже если пространство состояний представлялось графом с циклами.

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

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