Алгоритмы поиска в пространстве состояний

Поиск в пространстве состояний можно вести в двух направлениях: от исходных дан­ных задачи к цели и в обратном направлении от цели к исходным данным.

При поиске на основе данных (data-driveп search - поиск, управляемый данными), ко­торый иногда называют прямой цепочкой (forward chaiпiпg), исследователь начинает про­цесс решения задачи, анализируя ее условие, а затем применяет допустимые ходы или пра­вила изменения состояния. В процессе поиска правила применяются к известным фактам для получения новых фактов, которые, в свою очередь, используются для генерации новых фактов. Этот процесс продолжается до тех пор, пока мы, если повезет, не достигнем цели.

Возможен и альтернативный подход. Рассмотрим цель, которую мы хотим достичь.

Проанализируем правила или допустимые ходы, ведущие к цели, и определим условия

их применения. Эти условия становятся новыми целями, или подцелями, поиска. Поиск продолжается в обратном направлении от достигнутых подцелей до тех пор, пока (если

повезет) мы не достигнем исходных данных задачи. Таким образом определяется путь от

данных к цели, который на самом деле строится в обратном направлении. Этот подход называется поиском от цели, или обратной цепочкой.

Подведем итоги: поиск на основе данных начинается с условий задачи и выполняется путем применения правил или допустимых ходов для получения новых фактов, ведущих к цели. Поиск от цели начинается с обращения к цели и продолжается путем определе­ния правил, которые могут привести к цели, и построения цепочки подцелей, ведущей к исходным данным задачи. Наконец заметим, что в обоих случаях (и при поиске на основе данных и при поиске от цели) исследователь работает с одним и тем же графом пространства состояний, од­нако порядок и число состояний в процессе поиска могут различаться. Какую стратегию поиска предпочесть, зависит от самой задачи. При этом следует учитывать сложность правил, "форму" пространства состояний, природу и доступность данных задачи. Все это может изменяться от задачи к задаче.

Как пример зависимости сложности поиска от выбора стратегии рассмотрим задачу, в которой нужно подтвердить или опровергнуть утверждение "Я - потомок Томаса Джефферсона". Положительным решением является путь по генеалогическому дереву от "Я" до "Томас Джефферсон". Поиск на этом графе можно вести в двух направлениях: начиная от вершины "Я" строить цепочку предков к вершине "Томас Джефферсон", или начиная с вершины "Томас Джефферсон" анализировать цепочку его потомков.

Простая оценка позволяет сравнить сложность поиска в обоих направлениях. Томас Джефферсон родился примерно 250 лет назад. Если считать, что новое поколение рож­дается каждые 25 лет, то длина искомого пути составляет примерно 10. Поскольку каж­дый потомок имеет двух родителей, то путь от "Я" требует анализа 2¹⁰ предков. С другой

стороны, поиск от вершины "Томас Джефферсон" требует анализа большего числа со­стояний, поскольку родители обычно имеют более двух детей (особенно это касается во­семнадцатого и девятнадцатого столетий). Если допустить, что каждая семья имеет в среднем троих детей, то в процессе поиска нужно проанализировать 3¹⁰ вершин генеало­гического дерева. Таким образом, этот путь сложнее. Заметим, однако, что оба способа поиска имеют экспоненциальную сложность.