4.5. «И/ИЛИ» ГРАФЫ

Для изображения расчленения задачи на альтернативные множества результирующих задач удобно воспользоваться графоподобной структурой. Так, предположим, что задача А может быть решена либо путем решения задач В и С, либо путем решения задач и Е, либо путем решения задачи Это соотношение изображается структурой на рис. 4.4. В вершинах структуры указаны те задачи, которые они представляют.

Рис. 4.4. Структура, показывающая различные множества подзадач для А

Рис. 4.5. «И/ИЛИ» граф.

Задачи В и С составляют одно множество результирующих задач, задачи и Е — другое, а задача — третье. Вершины, соответствующие одному множеству, помечены специальным значком, связывающим подходящие к ним дуги.

В структуру обычно вводятся некоторые дополнительные вершины, так чтобы каждое множество, содержащее более одной результирующей задачи, группировалось под своей собственной родительской вершиной. При этом структура на рис. 4.4 преобразуется в структуру, изображенную на рис. 4.5. На этом рисунке добавленные вершины и М служат отдельными родительскими вершинами для множеств соответственно. Если считать, что вершины и М играют роль описаний задач, то мы видим, что задача А сведена к одиночным альтернативным подзадачам или По этой причине вершины, помеченные и называются «ИЛИ» вершинами.

Задача сводится к одному множеству подзадач В и С, причем обе они должны быть решены, чтрбы была решена задача По этой причине вершины, помеченные В и С, называются «И» вершинами. Вершины типа «И» выделяются отметкой, сделанной на идущих к ним дугах.

Структуры, подобные той, что изображена на рис. 4.5, называются «И/ИЛИ» графами. Если некоторая вершина «И/ИЛИ» графа имеет непосредственно следующие за ней вершины, то либо все они являются «ИЛИ» вершинами, либо все они — «И» вершины. (Если у некоторой вершины имеется ровно одна непосредственно следующая за ней вершина, то ее можно считать как «И» вершиной, так и «ИЛИ» вершиной.)

Заметим, что в частном случае, когда вершин типа «И» вообще нет, мы получаем обычный граф того типа, который появлялся при переборе в пространстве состояний. Но из-за наличия вершин типа «И» в «И/ИЛИ» графах эти структуры существенно отличаются от обычных графовых структур. Для них требуются свои собственные специализированные приемы поиска, что и служит главной причиной, по которой мы делаем различие между двумя подходами к решению задач.

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

На языке «И/ИЛИ» графов применение одиночного оператора сведения задачи к подзадачам к некоторому описанию задачи обычно будет означать, что по очереди сначала будет построена промежуточная «ИЛИ» вершина, а затем непосредственно следующие за ней «И» вершины. (Исключение составляет случай, когда множество подзадач состоит из одного элемента. В этом случае образуется ровно одна вершина, а именно «ИЛИ» вершина.)

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

Цель процесса поиска, осуществляемого на «И/ИЛИ» графе, — показать, что начальная вершина разрешима. Общее определение разрешимости вершины в «И/ИЛИ» графе можно сформулировать рекурсивно следующим образом:

Заключительные вершины разрешимы (так как они соответствуют элементарным задачам).

Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами

«ИЛИ», то она разрешима тогда и только тогда, когда разрешима по крайней мере одна из этих вершин.

Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами «И», то она разрешима тогда и только тогда, когда разрешима каждая из этих вершин.

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

Рис. 4.6. (см. скан) Некоторые примеры «И/ИЛИ» графов и решающих графов. Для графа (б) имеется более одного решения.

На рис. 4.6 приведены примеры «И/ИЛИ» графов. Заключительные вершины обозначены буквой разрешимые вершины изображены черными кружочками, а решающие графы выде лены жирными линиями.

Если у некоторой вершины «И/ИЛИ» графа, не являющейся заключительной вершиной, вовсе нет следующих за ней вершин, то мы говорим, что такая вершина неразрешима. Появление таких неразрешимых вершин может означать, что и другие вершины графа (и даже начальная вершина) могут оказаться

неразрешимыми. Общее определение неразрешимой вершины дается рекурсивно следующим образом:

Вершины, не являющиеся заключительными и не имеющие следующих за ними вершин, неразрешимы.

Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами

«ИЛИ», то она неразрешима тогда и только тогда, когда неразрешима каждая из этих вершин.

Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами «И», то она неразрешима тогда и только тогда, когда неразрешима по крайней мере одна из этих «И» вершин.

На рис. 4.6 неразрешимые вершины отмечены незачерненными кружочками.

Показанные на рис. 4.6 «И/ИЛИ» графы заданы в явной форме. Точно так же, как в случае решения задач в пространстве состояний, редко случается, чтобы граф, на котором должен осуществляться перебор, задавался в явной форме. Как правило, такой граф определен неявно посредством описания исходной задачи и операторов редукции задачи. Удобно ввести оператор Г построения непосредственно следующих (дочерних) вершин, который, будучи примененным к описанию задачи, порождает все множества следующих из него описаний задач. (Применение оператора Г означает применение всех применимых операторов сведения задачи к подзадачам.) Так, в случае рис. 4.5 применение оператора Г к алгоритму А образует всю ту структуру «И/ИЛИ» графа, которая изображена на рисунке.

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