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

Нужно найтипоследовательность действий, которая позволит обезьяне достать бананы. Предполагается, что обезьянаможет ходить по комнате, двигать по полу ящик, взбираться на него и хватать бананы.Ясно, что описание состояния этой задачи должно включать следующие сведения:местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. на полу онаили на ящике), местоположение ящика на полу и наличие у обезьяны бананов. Все это можнопредставить в виде четырехэлементного списка (ПолОб, ВертОб, ПолЯщ, Цель), гдеПолОб – положение обезьяны на полу (это может быть двухэлементный вектор координат);ПолЯщ – положение обезьяны и ящика на полу;ВертОб – это константа П или Я в зависимости от того, где находится обезьяна, на полу или наящике;Цель – это константа 0 или 1 в зависимости от того, достала ли обезьяна бананы или нет.Зафиксируем также как константы три следующие точки в плоскости пола:ТО – точка первоначального местоположения обезьяны;ТЯ – точка первоначального расположения ящика;ТБ – точка пола, расположенная непосредственно под связкой бананов.Тогда начальное состояние задачи описывается списком (ТО, П, ТЯ, 0), а целевое состояние задается каклюбой список, последний элемент которого – 1.Естественно определить операторы в этой задаче в соответствии с возможными действиями обезьяны:1) Перейти (W) – переход обезьяны к точке W горизонтальной плоскости пола;2) Передвинуть (V) – передвижение обезьяной ящика в точку V пола;3) Взобраться – обезьяна взбирается на ящик;4) Схватить – обезьяна хватает связку бананов.Условия применимости и действие этих операторов легко определить в виде правил продукций вида:аргумент оператора  результат оператора причемX, Y, Z, W, V обозначают переменные:1.

Перейти (W) :(X, П, Y, Z )  (W, П, Y, Z)2. Передвинуть (V) :(X, П, X, Z)  (V, П, V, Z)3. Взобраться :(X, П, X, Z)  (X, Я, X, Z)4. Схватить:(ТБ, Я,ТБ, 0)  (ТБ, Я, ТБ, 1)Будем считать, что для решения задачи значимы лишь вышеупомянутые точки пола Т О, ТЯ, ТБ ,тогда получим пространство состояний задачи, изображенное на рис. 4. Это пространство содержиттолько 13 состояний, дуги графа-пространства промаркированы порядковым номером применяемогооператора.

Пространство содержит четыре цикла хождения обезьяны между тремя значимыми точками(с ящиком или без него). В пространстве есть также две тупиковые ветви – когда обезьяна залезает наящик, но не под связкой бананов. Жирными дугами (стрелками) показан решающий путь, состоящий изчетырех операторов: Перейти (ТЯ); Передвинуть(ТБ); Взобраться; Схватить.40Рис. 4(ТО,П,ТЯ,0)(ТБ,П,ТЯ,0)11(ТЯ,Я,ТЯ,0)1(ТЯ,П,ТЯ,0)32(ТО,Я,ТО,0)3(ТО,П,ТО,0)1(ТЯ,П,ТО,0)3224(ТБ,П,ТБ,0)11(ТБ,Я,ТБ,0)1(ТБ,П,ТО,0) (ТЯ,П,ТБ,0)(ТБ,Я,ТБ,1)11(ТО,П,ТБ,0)Рассмотренный пример показывает, сколь важен для успешного и эффективного решения задачивыбор представления задачи. Такое небольшое по размерам пространство состояний получено, вчастности, вследствие того, что игнорировались все точки пола, кроме трех, соответствующихпервоначальному расположению обезьяны, ящика и бананов.Мощным приемом сужения пространств состояний является применение так называемых схемсостояний и схем операторов, в которых для описаний состояний и операторов используютсяпеременные.

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

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

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

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

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

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