5.3. Описание автомата на языке логики предикатов

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

Рис. 5.2. Дерево последовательностей действий

Атомы действий для дерева:

Эти атомы истинны, если совершается соответствующее действие, находящееся в скобках.

Атомы состояний для дерева:

Эти атомы истинны, если среда находится в соответствующем состоянии.

Формулы переходов между состояниями для дерева. Дерево на рис. 5.2 содержит 11 переходов между состояниями, каждый из которых происходит при осуществлении соответствующего действия. Переходы описываются импликациями:

Легко заметить, что подобное описание можно осуществлять как по дереву, так и по графу переходов автомата, реализующих множество Если воспользоваться графом на рис. 5.1, то получим следующее множество формул.

Атомы действий для графа. Эти атомы, естественно, те же самые, что и для дерева на рис. 5.2:

Атомы состояний для графа. Граф переходов на рис. 5.1 содержит существенно меньше вершин (состояний), чем дерево на рис. 5.2. Поэтому и количество атомов для состояний меньше:

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

Атомы действий, состояний и формулы переходов являются основой для постановки задачи. Легко подсчитать, что постановка задачи поиска целевого состояния, если ее осуществлять по дереву на рис. 5.2, будет содержать 3 атома для действий, 12 атомов для состояний и 12 формул для переходов, в то время как постановка задачи по графу на рис. 5.1 будет содержать 3 атома для действий, 3 атома для состояний и 8 формул для переходов. Если ограничиться только этими формулами, то в первом случае имеем суммарное число формул, равное 27, во втором случае — 14, т.е. во втором случае число формул уменьшилось почти вдвое. Это, конечно, не означает, что сложность (трудоемкость) поиска при постановке задачи поиска с меньшим количеством фактов будет всегда ниже, но, по крайней мере, объем памяти, требуемый для запоминания формул, может быть значительно меньше. Конечно, предварительное преобразование исходного описания постановки задачи в другое, требующее меньшее количество формул, также требует ресурсов (времени, памяти). Но если это преобразование осуществляется один раз, а после этого решение задачи осуществляется многократно для поиска различных целей, то затраты на преобразование могут оказаться оправданными.

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

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