AI-2010 Day 09 (Лекции 2010 года (rtf))

Искусственный интеллект – IV курс – День 09, лекции № 17, № 18 02.11.2010.

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

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

Алгоритмы поиска решения

Классификация алгоритмов

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

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

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

Вершины и указатели, построенные в процессе поиска, образуют поддерево всего неявно определенного при формализации задачи графа-пространства состояний. Это поддерево называется деревом перебора.

Известные алгоритмы поиска в пространстве состояний можно классифицировать по различным характеристикам, а именно:

• использование эвристической информации;

• порядок раскрытия (перебора) вершин;

• полнота просмотра пространства состояний;

• направление поиска.

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

Два основных вида слепых алгоритмов поиска, различающихся порядком раскрытия вершин – это алгоритмы поиска вширь и поиска вглубь.

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

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

Методы слепого (полного) перебора

Слепые алгоритмы поиска вширь (breadth_first_search) и поиска вглубь (depth_first_search) отличаются тем, какая вершина выбирается для очередного раскрытия. В алгоритме перебора вширь вершины раскрываются в том порядке, в котором они строятся. В алгоритме же перебора в глубину прежде всего раскрываются те вершины, которые были построены последними.

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

Перебор вширь

Базовый алгоритм поиска вширь состоит из следующей последовательности шагов (здесь и далее предполагаем, что начальная вершина не является целевой):

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

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

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

Конец алгоритма.

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

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

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

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

Перебор вглубь

Для формулировки алгоритма поиска вглубь необходимо определить понятие глубины вершины в дереве поиска. Это можно сделать следующим образом:

1. глубина корня дерева равна нулю;

2. глубина каждой некорневой вершины на единицу больше глубины ее родительской вершины.

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

Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной 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 первых вершин, построенных алгоритмом поиска вширь.

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

Анализ слепых алгоритмов. Бэктрекинг

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

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