Глава 13. Представление в виде И/ИЛИ-графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые подзадачи

Сведение задач к подзадачам. И/ИЛИ-Графы

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

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

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

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

Рис. 13.1. Поиск маршрута из а в z на карте дорог. Через реку можно переправиться в городах f и g. И/ИЛИ-представление этой задачи показано на рис. 13.2.

На карте рис. 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, необходимо:

2.1 найти путь из а в g и

2.2 найти путь из g в z.

Рис. 13.3. (а) Решить P — это значит решить P₁ или Р₂ или … (б) Решить Q — это значит решить все: Q₁ и Q₂ и ….

Итак, мы имеем две главных альтернативы для решения исходной задачи: (1) путь через f или (2) путь через g. Далее, каждую из этих альтернатив можно разбить на подзадачи (1.1 и 1.2 или 2.1 и 2.2 соответственно). Здесь важно то обстоятельство, что каждую из подзадач в обоих альтернативах можно решать независимо от другой. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ-графа (рис. 13.2). Обратите внимание на полукруглые дуги, которые указывают на отношение И между соответствующими подзадачами. Граф, показанный на рис. 13.2 — это всего лишь верхняя часть всего И/ИЛИ-дерева. Дальнейшее разбиение подзадач можно было бы строить на основе введения дополнительных промежуточных городов.

Какие вершины И/ИЛИ-графа являются целевыми? Целевые вершины — это тривиальные, или "примитивные" задачи. В нашем примере такой подзадачей можно было бы считать подзадачу "найти путь из а в с ", поскольку между городами а и с на карте имеется непосредственная связь.

Рассматривая наш пример, мы ввели ряд важных понятий. И/ИЛИ-граф — это направленный граф, вершины которого соответствуют задачам, а дуги — отношениям между задачами. Между дугами также существуют свои отношения. Это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них (см. рис. 13.3). В принципе из вершины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, мы будем предполагать, что каждая вершина имеет либо только И-преемников, либо только ИЛИ-преемников; дело в том, что в такую форму можно преобразовать любой И/ИЛИ граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И-дуги, называют И-вершиной; вершину, из которой выходят только ИЛИ-дуги, — ИЛИ-вершиной.

Когда задача представлялась в форме пространства состояний, ее решением был путь в этом пространстве. Что является решением в случае И/ИЛИ-представления? Решение должно, конечно, включать в себя все подзадачи И-вершины. Следовательно, это уже не путь, а дерево. Такое решающее дерево T определяется следующим образом:

• исходная задача P — это корень дерева T;

• если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе со своим собственным решающим деревом;

• если P — это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.

Рис. 13.4. (а) Пример И/ИЛИ-графа: d, g и h — целевые вершины; a — исходная задача. (b) и (с) Два решающих дерева, стоимости которых равны 9 и 8 соответственно. Здесь стоимость решающего дерева определена как сумма стоимостей всех входящих в него дуг.

Иллюстрацией к этому определению может служить рис. 13.4. Используя стоимости, мы можем формулировать критерии оптимальности решения. Например, можно определить стоимость решающего графа как сумму стоимостей всех входящих в него дуг. Тогда, поскольку обычно мы заинтересованы в минимизации стоимости, мы отдадим предпочтение решающему графу, изображенному на рис. 13.4(с).

Однако мы не обязательно должны измерять степень оптимальности решения, базируясь на стоимостях дуг. Иногда более естественным окажется приписывать стоимость не дугам, а вершинам, или же и тем, и другим одновременно.

Подведем итоги:

• И/ИЛИ-представление основано на философии сведения задач к подзадачам.

• Вершины И/ИЛИ-графа соответствуют задачам; связи между вершинами — отношениям между задачами.

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

• Вершина, из которой выходят И-связи, называется И-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить все ее задачи-преемники.

• При заданном И/ИЛИ-графе конкретная задача специфицируется заданием

стартовой вершины и

целевого условия для распознавания

целевых вершин.

• Целевые вершины (или "терминальные вершины") соответствуют тривиальным (или "примитивным") задачам.

• Решение представляется в виде решающего графа — подграфа всего И/ИЛИ-графа.

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

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

• Дугам или вершинам, или и тем, и другим можно приписать стоимости с целью получить возможность сформулировать критерий оптимальности решения.

13.2. Примеры И/ИЛИ-представления задач

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

Для задачи отыскания кратчайшего маршрута (рис. 13.1) И/ИЛИ-граф вместе с функцией стоимости можно определить следующим образом:

• ИЛИ-вершины представляются в форме X-Z, что означает: найти кратчайший путь из X в Z.

• И-вершины имеют вид

X-Z через Y

что означает: найти кратчайший путь из X в Z, проходящий через Y.

• Вершина X-Z является целевой вершиной (примитивной задачей), если на карте существует непосредственная связь между X и Z.

• Стоимость каждой целевой вершины X-Z равна расстоянию, которое необходимо преодолеть по дороге, соединяющей X с Z.

• Стоимость всех остальных (нетерминальных) вершин равна 0.

Стоимость решающего графа равна сумме стоимостей всех его вершин (в нашем случае это просто сумма стоимостей всех терминальных вершин). В задаче рис. 13.1 стартовая вершина — это а-z. На рис. 13.5 показан решающий граф, имеющий стоимость 9. Это дерево соответствует пути [a, b, d, f, i, z], который можно построить, если пройти по всем листьям решающего дерева слева направо.

Рис. 13.5. Решающее дерево минимальной стоимости для задачи поиска маршрута рис. 13.1, сформулированной в терминах И/ИЛИ-графа.

Задача о ханойской башне

Задача о ханойской башне (рис. 13.6) — это еще один классический пример эффективного применения метода разбиения задачи на подзадачи и построения И / ИЛИ-графа. Для простоты мы рассмотрим упрощенную версию этой задачи, когда в ней участвует только три диска:

Имеется три колышка 1, 2 и 3 и три диска а, b и с (а — наименьший из них, а с — наибольший). Первоначально все диски находятся на колышке 1. Задача состоит в том, чтобы переложить все диски на колышек 3. На каждом шагу можно перекладывать только один диск, причем никогда нельзя помещать больший диск на меньший.

Эту задачу можно рассматривать как задачу достижения следующих трех целей:

(1) Диск а — на колышек 3.

(2) Диск b — на колышек 3.

(3) Диск с — на колышек 3.

Беда в том, что эти цели не независимы. Например, можно сразу переложить диск а на колышек 3, и первая цель будет достигнута. Но тогда две другие цели станут недостижимыми (если только мы не отменим первое наше действие). К счастью, существует такой удобный порядок достижения этих целей, из которого можно легко вывести искомое решение.

Рис. 13.6. Задача о ханойской башне

Порядок этот можно установить при помощи следующего рассуждения: самая трудная цель — это цель 3 (диск с — на колышек 3), потому что на диск c наложено больше всего ограничений. В подобных ситуациях часто срабатывает хорошая идея: пытаться достичь первой самую трудную цель. Этот принцип основан на следующей логике: поскольку другие цели достигнуть легче (на них меньше ограничений), можно надеяться на то, что их достижение возможно без отмены действий на достижение самой трудной цели.

Применительно к нашей задаче это означает, что необходимо придерживаться следующей стратегии:

Первой достигнуть цель "диск с — на колышек 3", а затем — все остальные.

Но первая цель не может быть достигнута сразу, так как в начальной ситуации диск с двигать нельзя. Следовательно, сначала мы должны подготовить этот ход, и наша стратегия принимает такой вид

(1) Обеспечить возможность перемещения диска с с 1 на 3.

(2) Переложить с с 1 на 3.

(3) Достигнуть остальные цели (а на 3 и b на 3).

Переложить c с 1 на 3 возможно только в том случае, если диск а и b оба надеты на колышек 2. Таким образом наша исходная задача перемещения а, b и с с 1 на 3 сводится к следующим трем подзадачам:

Для того, чтобы переложить a, b и с с 1 на 3, необходимо

(1) переложить а и b с 1 на 2, и

(2) переложить с с 1 на 3, и

(3) переложить а и b с 2 на 3.

Задача 2 тривиальна (она решается за один шаг). Остальные две подзадачи можно решать независимо от задачи 2, так как диски а и b можно двигать, не обращая внимание на положение диска с. Для решения задач 1 и 3 можно применить тот же самый принцип разбиения (на этот раз диск b будет самым "трудным"). В соответствии с этим принципом задача 1 сводится к трем тривиальным подзадачам:

Для того, чтобы переложить а и b с 1 на 2, необходимо:

(1) переложить а с 1 на 3, и

(2) переложить b с 1 на 2, и

(3) переложить а с 3 на 2.

13.2.3. Формулировка игровых задач в терминах И/ИЛИ-графов

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И/ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами — ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция P — это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника Q ₁, Q ₂, Q ₃, … (см. рис. 13.7). Далее каждый вариант хода противника в позиции Q ₁ приводит к одной из позиций игрока R ₁₁, R ₁₂, …. В И/ИЛИ-дереве, показанном на рис. 13.7, вершины соответствуют позициям, а дуги — возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции P, нужно найти ход, переводящий P в выигранную позицию Q_i. (при некотором i). Таким образом, игрок выигрывает в позиции P, если он выигрывает в Q₁, или Q₂, или Q₃, или …. Следовательно, P — это ИЛИ-вершина. Для любого i позиция Q_i — это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Q_i, если он выигрывает во всех позициях R_i1 и R_i2 и …. Таким образом, все позиции противника — это И-вершины. Целевые вершины — это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.

Рис. 13.7. Формулировка игровой задачи для игры двух лиц в форме И/ИЛИ-дерева; участники игры: "игрок" и "противник".

13.3. Базовые процедуры поиска в И/ИЛИ-графах

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И/ИЛИ-графа. Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога — это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф рис. 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:

а:- b. % а - ИЛИ-вершина с двумя преемниками

а:- с. % b и с

b:- d, e. % b - И-вершина с двумя преемниками d и e

с:- h.

с:- f, g.

f:- h, i.

d. g. h. % d, g и h - целевые вершины

Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- а.

Получив этот вопрос, пролог-система произведет поиск в глубину в дереве рис. 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 13.4(b), ответит "да".

Преимущество такого метода программирования И/ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

• Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.

• В эту программу трудно вносить добавления, связанные с обработкой стоимостей.

• Если наш И/ИЛИ-граф — это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.

Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И/ИЛИ-графов.

Прежде всего мы должны изменить представление И/ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '--->'. Например, вершина а с двумя ИЛИ-преемниками будет представлена предложением

а ---> или: [b, с].

Оба символа '--->' и ':' — инфиксные операторы, которые можно определить как

:- op(600, xfx, --->).

:- op(500, xfx,:).

Весь И/ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений

а ---> или: [b, с].

b ---> и: [d, e].

с ---> и: [f, g].

e ---> или: [h].

f ---> или: [h, i].

цель(d). цель(g). цель(h).

Процедуру поиска в глубину в И/ИЛИ-графах можно построить, базируясь на следующих принципах:

Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:

(1) Если В — целевая вершина, то задача решается тривиальным образом.

(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).

(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).

Если применение этих правил не приводит к решению, считать, что задача не может быть решена.

Соответствующая программа выглядит так:

решить(Верш):-

цель(Верш).

решить(Верш):-

Верш ---> или: Вершины, % Верш - ИЛИ-вершина

принадлежит(Верш1, Вершины),

% Выбор преемника Верш1 вершины Верш

решить(Bepш1).

решить(Верш):-

Верш ---> и: Вершины, % Верш - И-вершина

решитьвсе(Вершины).

% Решить все задачи-преемники

решитьвсе([]).

решитьвсе([Верш | Вершины]):-

решить(Верш),

решитьвсе(Вершины).

Здесь принадлежит — обычное отношение принадлежности к списку.

Эта программа все еще имеет недостатки:

• она не порождает решающее дерево, и

• она может зацикливаться, если И/ИЛИ-граф имеет соответствующую структуру (циклы).

Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:

решить(Верш, РешДер).

Решающее дерево представим следующим образом. Мы имеем три случая:

(1) Если Верш — целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.

(2) Если Верш — ИЛИ-вершина, то решающее дерево имеет вид

Верш ---> Поддерево

где Поддерево — это решающее дерево для одного из преемников вершины Верш.

(3) Если Верш — И-вершина, то решающее дерево имеет вид

Верш ---> и: Поддеревья

где Поддеревья — список решающих деревьев для всех преемников вершины Верш.

% Поиск в глубину для И/ИЛИ-графов

% Процедура решить(Верш, РешДер) находит решающее дерево для

% некоторой вершины в И / ИЛИ-графе

решить(Верш, Верш):- % Решающее дерево для целевой

цель(Верш). % вершины - это сама вершина

решить(Верш, Верш ---> Дер):-

Верш ---> или: Вершины, % Верш - ИЛИ-вершина

принадлежит(Верш1, Вершины),

% Выбор преемника Верш1 вершины Верш

решить(Bepш1, Дер).

решить(Верш, Верш ---> и: Деревья):-

Верш ---> и: Вершины, % Верш - И-вершина

решитьвсе(Вершины, Деревья).

% Решить все задачи-преемники

решитьвсе([], []).

решитьвсе([Верш | Вершины], [Дер | Деревья]):-

решить(Верш, Дер),

решитьвсе(Вершины, Деревья).

отобр(Дер):- % Отобразить решающее дерево

отобр(Дер, 0),!. % с отступом 0

отобр(Верш ---> Дер, H):-

% Отобразить решающее дерево с отступом H

write(Верш), write('--->'),

H1 is H + 7,

отобр(Дер, H1),!.

отобр(и: [Д], H):-

% Отобразить И-список решающих деревьев

отобр(Д, H).

отобр(и: [Д | ДД], H):-

% Отобразить И-список решающих деревьев

отобр(Д, H),

tab(H),

отобр(и: ДД, H),!.

отобр(Верш, H):-

write(Верш), nl.

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

Например, при поиске в И/ИЛИ-графе рис. 13.4 первое найденное решение задачи, соответствующей самой верхней вершине а, будет иметь следующее представление:

а ---> b ---> и: [d, c ---> h]

Три формы представления решающего дерева соответствуют трем предложениям отношения решить. Поэтому все, что нам нужно сделать для изменения нашей исходной программы решить, — это подправить каждое из этих трех предложений, просто добавив в каждое из них решающее дерево в качестве второго аргумента. Измененная программа показана на рис. 13.8. В нее также введена дополнительная процедура отобр для отображения решающих деревьев в текстовой форме. Например, решающее дерево рис. 13.4 будет отпечатано процедурой отобр в следующем виде:

а ---> b ---> d

e ---> h

Программа рис. 13.8 все еще сохраняет склонность к вхождению в бесконечные циклы. Один из простых способов избежать бесконечных циклов — это следить за текущей глубиной поиска и не давать программе заходить за пределы некоторого ограничения по глубине. Это можно сделать, введя в отношение решить еще один аргумент:

решить(Верш, РешДер, МаксГлуб)

Как и раньше, вершиной Верш представлена решаемая задача, а РешДер — это решение этой задачи, имеющее глубину, не превосходящую МаксГлуб. МаксГлуб — это допустимая глубина поиска в графе. Если МаксГлуб = 0, то двигаться дальше запрещено, если же МаксГлуб > 0, то поиск распространяется на преемников вершины Верш, причем для них устанавливается меньший предел по глубине, равный МаксГлуб-1. Это дополнение легко ввести в программу рис. 13.8. Например, второе предложение процедуры решить примет вид:

решить(Верш, Верш ---> Дер, МаксГлуб):-

МаксГлуб > 0,

Верш ---> или: Вершины, % Верш - ИЛИ-вершина

принадлежит (Верш1, Вершины),

% Выбор преемника Верш1 вершины Верш

Глуб1 is МаксГлуб - 1, % Новый предел по глубине

решить(Bepш1, Дер, Глуб1).

% Решить задачу-преемник с меньшим ограничением

Нашу процедуру поиска в глубину с ограничением можно также использовать для имитации поиска в ширину. Идея состоит в следующем: многократно повторять поиск в глубину каждый раз все с большим значением ограничения до тех пор, пока решение не будет найдено, То есть попробовать решить задачу с ограничением по глубине, равным 0, затем — с ограничением 1, затем — 2 и т.д. Получаем следующую программу:

имитация_в_ширину(Верш, РешДер):-

проба_в_глубину(Верш, РешДер, 0).

% Проба поиска с возрастающим ограничением, начиная с 0

проба_в_глубину(Верш, РешДер, Глуб):-

решить(Верш, РешДер, Глуб);

Глуб1 is Глуб + 1, % Новый предел по глубине

проба_в_глубину(Верш, РешДер, Глуб1).

% Попытка с новым ограничением

Недостатком имитации поиска в ширину является то, что при каждом увеличении предела по глубине программа повторно просматривает верхнюю область пространства поиска.