Представление задач в виде И/ИЛИ-графов
Мы рассмотрели подход к решению задач, основанный на поиске пути в графе пространства состояний. Однако для некоторых категорий задач представление в форме И/ИЛИ-графа является более естественным. Такое представление основано на разбиении задач на подзадачи. Разбиение на подзадачи дает преимущества в том случае, когда подзадачи взаимно независимы, а, следовательно, и решать их можно независимо друг от друга.
Рис. 2.7. Поиск маршрута из a в z на карте дорог.
Через реку можно переправиться в городах f и g.
И/ИЛИ-представление этой задачи показано на рис. 2.8.
Проиллюстрируем это на примере. Рассмотрим задачу отыскания на карте дорог маршрута между двумя заданными городами, как показано на рис. 2.7. Не будем учитывать длину путей. Разумеется, эту задачу можно сформулировать как поиск пути в пространстве состояний. Соответствующее пространство состояний выглядело бы в точности, как карта рис. 2.7: вершины соответствуют городам, дуги - непосредственным связям между городами. Тем не менее, давайте построим другое представление, основанное на естественном разбиении этой задачи на подзадачи. На карте рис. 2.7 мы видим также реку. Допустим, что переправиться через нее можно только по двум мостам: один расположен в городе f, другой - в городе g. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит, он должен пройти либо через f, либо через g. Таким образом, мы имеем две главных альтернативы:
Для того чтобы найти путь из a в z, необходимо найти одно из двух:
(1) путь из a в z, проходящий через f, или
(2) путь из a в z, проходящий через g.
Теперь каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:
(1) Для того, чтобы найти путь из a в z через f, необходимо:
1.1 найти путь из a в f и
1.2 найти путь из f в z.
(2) Для того, чтобы найти путь из a в z через g, необходимо:
2.1 найти путь из a в g и
2.2. найти путь из g в z.
Итак, мы имеем две главные альтернативы для решения исходной задачи: (1) путь через f или (2) путь через g.
Далее, каждую из этих альтернатив можно разбить на подзадачи (1.1 и 1.2 или 2.1 и 2.2 соответственно). Здесь важно то обстоятельство, что каждую из подзадач в обеих альтернативах можно решать независимо от другой. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ -графа (рис. 2.8).
Рис. 2.8. И/ИЛИ-представление задачи поиска маршрута рис.2.7
Вершины соответствуют задачам или подзадачам, полукруглые дуги означают, что все (точнее, обе) подзадачи должны быть решены.
Обратите внимание на полукруглые дуги, которые указывают на отношение И между соответствующими подзадачами. Граф, показанный на рис. 2.8 - это всего лишь верхняя часть всего И/ИЛИ-дерева. Дальнейшее разбиение подзадач можно было бы строить на основе введения дополнительных промежуточных городов.
Какие вершины И/ИЛИ-графа являются целевыми? Целевые вершины - это тривиальные, или "примитивные" задачи. В нашем примере такой подзадачей можно было бы считать подзадачу "найти путь из a в c", поскольку между городами a и c на карте имеется непосредственная связь.
Рассматривая наш пример, мы ввели ряд важных понятий. И/ИЛИ-граф - это направленный граф, вершины которого соответствуют задачам, а дуги отношениям между задачами. Между дугами также существуют свои отношения. Это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них (рис. 2.9). В принципе из вершины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, мы будем предполагать, что каждая вершина имеет либо только И-преемников, либо только ИЛИ-преемников; дело в том, что в такую форму можно преобразовать любой И/ИЛИ-граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И-дуги, называют И-вершиной; вершину, из которой выходят только ИЛИ-дуги, - ИЛИ-вершиной.
Рис. 2.9. (a) Решить P - это значит решить P1или P2 или …
(b) Решить Q - это значит решить Q1 и Q2 и … .
Когда задача представлялась в форме пространства состояний, ее решением был путь в этом пространстве. Что является решением в случае И/ИЛИ-представления? Решение, конечно, должно включать в себя все подзадачи И-вершины. Следовательно, это уже не путь, а дерево. Такое решающее дерево T определяется следующим образом:
· исходная задача P - корень дерева T;
· если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе со своим собственным решающим деревом;
· если P - это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.