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

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

В исходной точкепроцесса к начальному состоянию применяется тот или иной оператор и строится новая вершинасостояние, а также связывающие ее с корневой вершиной дуги. На каждом последующем шагепоиска к одной из уже полученных вершин-состояний применяется допустимый оператор истроится еще одна вершина графа и связывающие дуги. Этот процесс поиска продолжается до техпор, пока не будет построена вершина, соответствующая целевому состоянию.Рис.21117131117139g52438101512614111713111713g3529481015126149352g481093524 15g 128 610 1415126141117131117139352154810g12614935241281015g614111713111713935293524 158 12g 610 144 15g 128 610 14Примеры пространств состоянийРазберем два характерных примера представления в пространстве состояний,показывающих, что такое представление возможно для различных типов задач.

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

Коммивояжер, располагая картой дорог,соединяющей 7 городов (рис. 3), должен построить свой маршрут так, чтобы выехав из города А,посетить каждый из других шести городов B, C, D, E, H, G в точности по одному разу и затемвернуться в исходный город. В другом, более сложном варианте задачи требуется также, чтобымаршрут имел минимальную протяженность.ABGEDHРис. 3CСостояние решаемой задачи можно задать как список городов, которые уже проехалкоммивояжер к текущему моменту.

Тогда возможным состояниям соответствуют списки изэлементов A, B, C, D, E, H, G без повторений, исключение составляет только город A, он можетвстретиться в списке дважды – в начале списка и его конце. Пример списка-состояния – (A B C H).Начальное же состояние определяется как список (A), а целевое – как любой допустимый список,начинающийся и кончающийся элементом A.

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

Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбиратьсяна него и хватать бананы.Ясно, что описание состояния этой задачи должно включать следующие сведения:местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. наполу она или на ящике), местоположение ящика на полу и наличие у обезьяны бананов. Все этоможно представить в виде четырехэлементного списка (ПолОб, ВертОб, ПолЯщ, Цель), гдеПолОб – положение обезьяны на полу (это может быть двухэлементный вектор координат);ПолЯщ – положение обезьяны и ящика на полу;ВертОб – это константа П или Я в зависимости от того, где находится обезьяна, на полу или наящике;Цель – это константа 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 состояний, дуги графа-пространства промаркированы порядковым номеромприменяемого оператора. Пространство содержит четыре цикла хождения обезьяны между тремязначимыми точками (с ящиком или без него). В пространстве есть также две тупиковые ветви –когда обезьяна залезает на ящик, но не под связкой бананов.

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

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

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

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

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

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