Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
5.3. Описание автомата на языке логики предикатовРассмотренное в примере множество последовательностей действий
Рис. 5.2. Дерево последовательностей действий Атомы действий для дерева:
Эти атомы истинны, если совершается соответствующее действие, находящееся в скобках. Атомы состояний для дерева:
Эти атомы истинны, если среда находится в соответствующем состоянии. Формулы переходов между состояниями для дерева. Дерево на рис. 5.2 содержит 11 переходов между состояниями, каждый из которых происходит при осуществлении соответствующего действия. Переходы описываются импликациями:
Легко заметить, что подобное описание можно осуществлять как по дереву, так и по графу переходов автомата, реализующих множество Атомы действий для графа. Эти атомы, естественно, те же самые, что и для дерева на рис. 5.2:
Атомы состояний для графа. Граф переходов на рис. 5.1 содержит существенно меньше вершин (состояний), чем дерево на рис. 5.2. Поэтому и количество атомов для состояний меньше:
Формулы переходов для графа. Переходов в графе также меньше, чем в дереве. Поэтому и соответствующих импликаций также меньше:
Атомы действий, состояний и формулы переходов являются основой для постановки задачи. Легко подсчитать, что постановка задачи поиска целевого состояния, если ее осуществлять по дереву на рис. 5.2, будет содержать 3 атома для действий, 12 атомов для состояний и 12 формул для переходов, в то время как постановка задачи по графу на рис. 5.1 будет содержать 3 атома для действий, 3 атома для состояний и 8 формул для переходов. Если ограничиться только этими формулами, то в первом случае имеем суммарное число формул, равное 27, во втором случае — 14, т.е. во втором случае число формул уменьшилось почти вдвое. Это, конечно, не означает, что сложность (трудоемкость) поиска при постановке задачи поиска с меньшим количеством фактов будет всегда ниже, но, по крайней мере, объем памяти, требуемый для запоминания формул, может быть значительно меньше. Конечно, предварительное преобразование исходного описания постановки задачи в другое, требующее меньшее количество формул, также требует ресурсов (времени, памяти). Но если это преобразование осуществляется один раз, а после этого решение задачи осуществляется многократно для поиска различных целей, то затраты на преобразование могут оказаться оправданными. Возникает, конечно, вопрос, можно ли использовать для поиска цели по графу ту же стратегию, что и по дереву. Легко заметить, что при поиске по дереву не использовалось никаких соображений, которые учитывали бы свойства дерева. На каждом шаге поиска состояние, в которое был осуществлен переход после очередного действия, проверялось, не является ли оно целевым. Если оно таковым оказывалось, то задача поиска (если целевое состояние единственное) считалась завершенной. Таким образом, рассмотренная в главе 2 стратегия поиска в пространстве состояний никак не зависит от того, имеете ли вы граф или дерево. Алгоритм разбиения последовательностей на классы эквивалентности требует трудоемкой и утомительной процедуры проверки отношения
|
1 |
Оглавление
|