Intel_Nils, страница 6

Глава 2 ПРЕДСТАВЛЕНИЕ ЗАДАЧ В ПРОСТРАНСТВЕ СОСТОЯНИЙ ал. опислния состоянии В предыдущей главе мы ввели понятия состояний и операторов. Здесь мы займемся детальной разработкой этих идей и дадим несколько примеров формулировки задач в терминах пространства состояний. Чтобы построить описание задачи с использованием пространства состояний, мы должны иметь определенное представление о том, что представляют собой состояния в этой задаче. В игре в пятнадцать выбор в качестве состояний различных конфигураций из фишек был достаточно очевидным.

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

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

Рассмотрим задачу преобразования алгебраического выражения (АВ+ СР)/ВС в более простое выражение А/С+ Р/В. Очевидно, что в качестве состояний задачи здесь должны выступать алгебраические выражения, но необходимо еще принять решение относительно формы описания состояний. В широко используемом описании употребляются двоичные деревья. Неконцавые вершины в таком дереве описания представляют арифметические знаки (+, —, Х, —:), а концевые вершины представляют переменные или постоянные символы (А, В, С, Р), появляющиеся в этом выражении. Таким обра- 27 22.

Операторы зом, деревом представления для выражения (АВ+ С0)/ВС должно быть л 6 и и Здесь ветвь, отходящая от вершины —: влево, представляет числитель дроби, а ветвь, отходящая вправо, — ее знаменатель. Применение законов алгебраических преобразований (операторов в пространстве состояний) привело бы к преобразованию этого описания в другие описания. Наша задача состоит в преобразовании его в состояние, 'описываемое деревом Другой известной формой описания служит линейная строка. Возможное описание для выражения (АВ+ С0)(ВС в виде строки такое — .

'+ Х АВ Х С0 Х ВС. Здесь арифметические операторы ( —:, + н Х) называются префиксныии операторами, поскольку они предшествуют в этой строке своим операндам. Так как нам известно, что каждый из этих операторов относится ровно к двум операндам, то в этой строке нет необходимости в пунктуации. Операндами для символа + в этой строке, например, должны быть две идущие непосредственно друг за другом подстроки, которые представляют собой алгебраические выражения Х АВ и Х С0. Используя описание в форме строки, можно сформулировать стоящую перед нами проблему как задачу преобразования строки †.' + Х АВ Х Х С0 Х ВС в строку + —: АС вЂ”: 0В. 2.2.

ОПЕРАТОРЫ Операторы переводят одно состояние в другое. Таким образом, их можно рассматривать как функции, определенные иа множестве состояний и принимающие значения из этого мнот 28 Гя. 2. Представление вада« в пространстве состояний. жества'). Так как наши процессы решения задач основаны на работе с описаниями состояний, то мы будем предполагать, что операторы суть функции этих описаний, а их значения суть новые описания.

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

Он основан на идее правил переписывания (называемых иногда продукциячи (ргос(псИопз)). Множество правил переписывания определяет возможные способы преобразования одной строки в другую. Все правила переписывания имеют форму 5т — 5ь означающую, что строка 5, может быть преобразована в строку 5р Пример правила переписывания таков: А$ -ь В$ Оно означает, что если символ А появляется в качестве первого символа некоторой строки, то он может быть заменен на символ В.

Знак $ — произвольная подстрока (включая пустую строку). В приведенном правиле переписывания знак $ указывает, что часть строки (какова бы она ни была), идущая непосредственно за А, не изменяется, когда А заменяется на В. Для указания нескольких различных подстрок в правилах переписывания может быть использовано несколько знаков $. Так мы получаем следующие примеры возможных правил переписывания: !, А 3 А-ьА (строка, начинающаяся и кончающаяся символом А, может быть заменена одиночным символом А).

2. 3,ВАВ3г-+3,ВВ3г (одиночный символ А, стоЯщий междУ двумя символами В, можно исключить). $~3г$а-ь31$г3г3г (каждая подстрока может быть повторена). 4 $13г3г3а-+3~3г3г (одна из двух стоящих рядом одинаковых подстрок может быть исключена). ') В действительности они могут быть определены не на всем множестве состояний, поскольку оператор может быть неприменим к некоторым состояниям. 2.2. Операторы Используя, например, два последних правила, строку АВСВАВС можно преобразовать в ст11оку АВС следующим образом: АВСВАВС вЂ” АВАВСВАВС вЂ” АВАВС вЂ” АВС Правило переписывания часто может применяться к некоторой строке несколькими различными способами. Так, в приведен- х, хб х, х, Ха Хб Хб хв Хб х, хв Хб х, Хг х, х, Хб Хт «б «4 хв Хб хв х, х, х, Кб Хб х, хв х х„ хв х, х, 7 Хв Хт х, к, хб х, Хб Хб хт Хб «7 Хт х, — хах,х, х, х, х; Х7 Хб х, х, х, х, х, х, кт хб Хв Хб кв хт хв хв Рис.

2.Ь Правила переписывания для игры в восемь. ном примере правило 4 к строке АВСВАВС вообще не может быть применено, тогда как правило 3 может применяться к ней несколькими способами. Конечно, определенному оператору отвечает некоторое конкретное применение данного правила переписывания. Поскольку одно правило переписывания может пред- х, з х х х, х, х, х х, «х х 1В Х Х Х вЂ” хб х, х, Хт зо Гл. 2. Представление эадач в аространстве состояний ставлять много различных операторов, то правила переписывания находят широкое применение при решении задач. Представление операторов с помощью правил переписывания не должно быть обязательно ограничено ситуациями, в которых состояния описываются строками. Аналогичные идеи могут быть использованы, например, для игры в пятнадцать, в которой естественным описанием состояний служит массив 4 уС 4.

Проиллюстрируем это обобщенное понятие правил переписывания на примере игры в восемь — упрощенном варианте игры в пятнадцать. В этой игре восемь пронумерованных фишек расположены на площадке размером Зря,З, Один из способов представления допустимых ходов в этой игре состоит в задании множества правил переписывания, определенных над массивами. Этн правила определяют пути, по которым массивы 3 рс,З могут быть преобразованы в другие массивы того же размера. На рис.

2.1 изображено множество правил переписывания для игры в восемь. Каждое правило представляет собой в действительности два правила (как это показано двунаправленными стрелками), объединенных для экономии места в одно; в каждом случае левая запись может быть заменена правой и обратно. В каждом из правил переписывания допустимый ход определяется путем подстановки чисел 1,2, ..., 8 на место переменных Хт, Хм ..., Хв по каждую сторону от стрелки (при условии Хт ~ Х;). Так, может быть преобразовано в посредством применения правила 3, ЗЛ.

ЦЕЛЕВЫЕ СОСТОЯНИЯ Во все наши процедуры исследования пространства состоя. ний входит построение новых описаний состояний, исходя из старых с последующей проверкой новых описаний состояний, К4. Залива в виде графа с тем чтобы убедиться, не описывают ли оии состояние, отвечающее поотавленной цели. Часто это просто проверка того, соответствует ли некоторое описание состояния данному целевому описанию состояния, но иногда должна быть произведена более сложная проверка. Например, для игры в пятнадцать целью может быть создание конфигурации из фишек, в которой в верхних двух рядах не будет фишек с номерами, превосходящими !2.

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

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

Мы уже отмечали, что пространство состояний полезно представлять себе в виде направленного. графа. Такое представление особенно полезно для исследования различных методов поиска в пространстве состояний. В следующем разделе мы приведем некоторые необходимые сведения из теории графов. Ял. ЗАПИСЬ В ВИДЕ ГРАФА В гл. 1 мы использовали граф с целью иллюстрации пространства состояний для игры в пятнадцать. Ло сих пор наше рассмотрение графов носило интуитивный характер, а в настоящем разделе будут введены некоторые полезные формальные понятия, относящиеся к графам. Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направлеииь»х графов.

Если некоторая дуга направлена от вершины п» к вершине пь то говорят, что вершина и; является дочерней вершиной для вершины и;, а вершина п» является родительской вершиной для и». Может оказаться, что некие две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае когда граф используется для пред. 32 Гл. 2. Представление задач в ирастранстве состояний ставления пространства состояний, с его вершинами связывают описания состояний, а с его дугами — операторы. Последовательность вершин пн, пм, ..., пм, в которой каждая вершина пп дочерняя для пс,;,, ) = 2, ..., й, называется путем длины й от вершины и;, к вершине паь Если существует путь, ведущий от вершины пс к вершине пв то вершину и, называют достижимой из вершины и; или потомком вершины пь В этом случае вершина кч называется также предком для вершины пр Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе.