Шпора-small (Шпоры к первому коллоквиуму), страница 13

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

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

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

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

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

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

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

Если же решающего пути нет, то (в случае конечных032 8 31g47 6 58деревьев-пространств) будет сообщено о неуспехе поиска, в случае же бесконечных пространствалгоритм не кончит свою работу.На рис. 5 приведено дерево, построенное в результате применения алгоритма поискавширь к некоторой начальной конфигурации игры в восемь, причем выполнение алгоритмапрервано после построения первых 12 вершин (при этом раскрыто 6 вершин). В вершинах деревапомещены соответствующие описания состояний. Эти вершины занумерованы в том порядке, вкотором они были построены в ходе поиска. На следующем шаге цикла алгоритма будетраскрываться одна из вершин с номерами 6, 7 или 8, поскольку они расположены в начале списканераскрытых вершин.Рис.5217678 36 4g522 8 31 6 47 5g51 2 8 31 6 4g7 54122 8 3 2g31 4g 1 8 47 6 5 7 6 5112 8 3 2 8 31 6g g1 47 5 4 7 6 51092 8g1 6 37 5 42 8 3g6 41 7 52 8 3 g 8 3 12 8 36 g4 2 6 4 1 g61 7 5 1 7 5 7 5 4Считаем, что порядок построения дочерних вершин соответствует следующемузафиксированному порядку перемещения пустой клетки («пустышки»): влево/вправо/вверх/вниз.Предполагается также, что используемая алгоритмом операция раскрытия вершин организованатаким образом, что она не порождает никакое состояние-вершину, построенную ранее иявляющуюся родительской для раскрываемой вершины.

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

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

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

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

Соответствующий алгоритм поисканазывается ограниченным перебором вглубь.Основные шаги базового алгоритма ограниченного перебора вглубь (с граничнойглубиной 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, конфигурация игры в восемь. Вершины занумерованы в том порядке, в которомони были построены.