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

Возникает, конечно, вопрос, можно ли использовать для поиска цели по графу ту же стратегию, что и по дереву. Легко заметить, что при поиске по дереву не использовалось никаких соображений, которые учитывали бы свойства дерева. На каждом шаге поиска состояние, в которое был осуществлен переход после очередного действия, проверялось, не является ли оно целевым. Если оно таковым оказывалось, то задача поиска (если целевое состояние единственное) считалась завершенной. Таким образом, рассмотренная в главе 2 стратегия поиска в пространстве состояний никак не зависит от того, имеете ли вы граф или дерево. Алгоритм разбиения последовательностей на классы эквивалентности требует трудоемкой и утомительной процедуры проверки отношения R на множестве последовательностей S. В постановке задачи, однако, вместо множества последовательностей действий S имеем множество состояний и переходов. Каждой последовательности действий а*, ведущей из начального состояния, соответствует на дереве последовательность переходов, ведущих из начального состояния дерева в одно из промежуточных или целевых состояний. Каждая последовательность ведет только в одно состояние, т.е. каждое состояние взаимно однозначно соответствует последовательности переходов, ведущей в него. Эк> означает, что если последовательность действий с*ведет из начального состояния в состояние Ь, то можно считать, что Ф*(С*) = Ф(А). ИСХОДЯ ИЗ этого, вместо классов эквивалентности последовательностей действий можно получать классы эквивалентности состояний на основе трансформации отношения R в отношение, которое обозначим /Р, определяемое следующим образом: А,/?*А2, если bv b2e В и Ф(А") — Ф(А") для всех а^а*, а2*а* € Л*" таких, что с, * ведет в bv аг * ведет в bv с* ведет из состояния Ьх в состояние Ь'[, а из1 состояния Ь2 в состояние Ь".