Искусственный интеллект

состояние (?,'), состояние (Ь2), состояние (Ь0. Формулы переходов для графа. Переходов в графе также меньше, чем в дереве. Поэтому и соответствующих импликаций также меньше: состояние (?,') л действие (ё) з состояние (bf), состояние (Ь\) л действие (о,) з состояние (Ь\), состояние (Ь\) л действие (а}) з состояние (Ь\), состояние (Ь)) л действие(а2) з состояние(Ь'2), состояние (Ь'г) л действие (о,) з состояние (Ь0, состояние (Ь2Г) л действие (о3) з состояние (А,'), состояние (Ь'г) л действие (о,) з состояние (Ь'2), состояние (Ь0 л действие (а2) з состояние (Ь\). 114 5.3 Описание автомата на языке логики предикатов Атомы действий, состояний и формулы переходов являются основой для постановки задачи. Легко подсчитать, что постановка задачи поиска целевого состояния, если ее осуществлять по дереву на рис. 5.2, будет содержать 3 атома для действий, 12 атомов для состояний и 12 формул для переходов, в то время как постановка задачи по графу на рис. S.1 будет содержать 3 атома для действий, 3 атома для состояний и 8 формул для переходов. Если ограничиться только этими формулами, то в первом случае имеем суммарное число формул, равное 27, во втором случае — 14, т.е. во втором случае число формул уменьшилось почти вдвое. Это, конечно, не означает, что сложность (трудоемкость) поиска при постановке задачи поиска с меньшим количеством фактов будет всегда ниже, но, по крайней мере, объем памяти, требуемый для запоминания формул, может быть значительно меньше. Конечно, предварительное преобразование исходного описания постановки задачи в другое, требующее меньшее количество формул, также требует ресурсов (времени, памяти). Но если это преобразование осуществляется один раз, а после этого решение задачи осуществляется многократно для поиска различных целей, то затраты на преобразование могут оказаться оправданными.