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

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

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

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

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

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

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

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

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

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

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

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