Prolog

независимые подзадачи. Примерами таких задач могут служить поиск маршрута, символическое интегрирование, а также игровые задачи, доказательство теорем и т.п. В этой главе мы разработаем программы для поиска в И / ИЛИ-графах, в том числе программу поиска с предпочтением, управляемого эвристиками.

13. 1.    Представление задач в виде И / ИЛИ-графов

В главах 11 и 12, говоря о решении задач, мы сконцентрировали свое внимание на пространстве состояний как средстве представления этих задач. В соответствии с таким подходом решение задач сводилось к поиску пути в графе пространства состояний. Однако для некоторых категорий задач представление в форме И / ИЛИ-графа является более естественным. Такое представление основано на разбиении задач на подзадачи. Разбиение на подзадачи дает преимущества в том случае, когда подзадачи взаимно независимы, а, следовательно, и решать их можно независимо друг от друга.

Проиллюстрируем это на примере. Рассмотрим задачу отыскания на карте дорог маршрута между двумя заданными городами, как показано на рис. 13.1. Не будем пока учитывать длину путей. Разумеется, эту задачу можно сформулировать как поиск пути в про-

Рис. 13. 1.  Поиск маршрута из  а  в  z  на карте дорог. Через реку

можно переправиться в городах  f  и   g.  И / ИЛИ-представление этой

задачи показано на рис. 13.2.

странстве состояний. Соответствующее пространство состояний выглядело бы в точности, как карта рис. 13.1: вершины соответствуют городам, дуги - непосредственным связям между городами. Тем не менее давайте построим другое представление, основанное на естественном разбиении этой задачи на подзадачи.

На карте рис. 13.1 мы видим также реку. Допустим, что переправиться через нее можно только по двум мостам: один расположен в городе  f,   другой - в городе  g.  Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит, он должен пройти либо через  f,  либо через  g.   Таким образом, мы имеем две главных альтернативы:

        Для того, чтобы найти путь из  а  в  z,

        необходимо найти одно из двух:

        (1)         путь из  а  в  z,   проходящий через  f,  или

        (2)         путь из  а  в  z,   проходящий через  g.

Рис. 13. 2.  И / ИЛИ-представление задачи поиска маршрута рис. 13.1.

Вершины соответствуют задачам или подзадачам, полукруглые дуги

означают, что все (точнее, обе) подзадачи должны быть решены.

Теперь каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:

        (1)         Для того, чтобы найти путь из  a  в  z  через

                     f,   необходимо:

                    1.1 найти путь из  а  и  f   и

                    1.2 найти путь из  f  в  z.

        (2)         Для того, чтобы найти путь из  a  в  z  через

                     g,   необходимо: