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

Между полученными при разбиении подзадачами могут быть отношения согласованности (одновременности) решения (отношение И), или отношение альтернативности (отношение ИЛИ). Рассмотрим это подробнее.

Допустим, что исходная задача Z может быть разбита на подзадачи Л, 5, С, Д Е. Пусть при этом подзадачи А и В, а также Си D находятся в отношениях И, т. е. должны решаться согласованно (одновременно), а множества (А И В), (С И D) и подзадача Е находятся в отношении ИЛИ, т. е. они имеют альтернативный характер отношений. Тогда все сказанное легко отобразить на графе (рис. 2.7).

Рис. 2.7. Граф отношений подзадач для задачи Z.

Отношения типа Я будем отмечать двойной дугой, связывающей ребра графа. Для единообразия представления можно ввести дополнительные (фиктивные) вершины, которые группировали бы подзадачи типа Я и ИЛИ под своей собственной родительской вершиной (рис. 2.8).

Рис. 2.8. И/ИЛИ-гуаф задачи Z.

Таким образом, исходная задача Z представлена подзадачами М, N и Е, имеющими альтернативный ЯЛГЯ-характер, а подзадачи М и Л^г, в свою очередь, — подзадачами (А, В) и (С, D) с отношениями типа И. Альтернативные вершины М, N, Е называются поэтому Я/7Я-вершинами, а вершины А, В, С, D — И-вершинами и помечаются двойной дугой.

Структура, типа изображенной на рис. 2.8, называется И/ИЛИ-графом. При этом, как видим, если вершина И/ИЛИ-графа имеет непосредственно следующие за ней вершины, то либо все они являются ЯЖГ-вершинами, либо Я-вершинами. Если у вершины имеется только одна следующая за ней вершина, то ее можно считать как Я-, так и Я/7Я-вершиной. Если вершин типа Я вообще нет, то получается обычный граф, тот самый, который получался в методе полного перебора при поиске в пространстве состояний.

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

Основная цель поиска на Я/Я/7Я-графе — показать разрешимость вершины Sj. Вершина является разрешимой, если выполняется одно из следующих условий:

• 1) вершина S'• является заключительной;
• 2) следующие за 5, вершины являются вершинами типа ИЛИ, и при этом хотя бы одна из них разрешима;
• 3) следующие за S_i вершины являются вершинами типа Я, и при этом каждая из них разрешима.

Решающим графом называется подграф, состоящий из разрешимых вершин с корнем в начальной вершине.

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

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