Поиск методом редукции

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа Г, называемого И/ИЛИ графом. Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. К-вершины, или вершины типа «И», вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам К-вершины. Д-вершины, или вершины типа «ИЛИ», вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины. Решение задачи при поиске методом редукции (при поиске в И/ИЛИ графе) сводится к нахождению в И/ИЛИ графе решающего графа, определение которого дадим позже. Заметим, что метод сведения задач к подзадачам является в некотором роде обобщением подхода с использованием пространства состояний. Действительно, перебор в пространстве состояний можно рассматривать как тривиальный случай сведения задачи всегда к одной подзадаче.

Графически для различения Д- и К- вершин дуги, исходящие из К-вершины, соединяются дужкой при вершине. Пример графического представления разбиения задачи на подзадачи приведен на рис.А. Здесь S0 — исходная задача, для решения которой требуется решить подзадачу S3, или подзадачи S1 и S2.

Решение S1 сводится к решению либо подзадачи S4, либо подзадачи S5. Решение подзадачи S3 сводится к решению подзадач S6 и S7.

Решение задач S2, S5, S7 предполагается известным, решение задач S4 и S6 неизвестно. В приведенном примере задача S0 может быть решена либо путем решения задачи S3, либо путем решения задач S1, S2. В связи с тем, что в И/ИЛИ графе каждая вершина относится только к одному типу (либо И, либо ИЛИ), то для записи графа, изображенного на рис.А в виде И/ИЛИ графа, надо ввести дополнительную вершину (см. вершина R1 на рис.В). На рис.В. двойными линиями выделен решающий граф задачи S0, а конечные вершины обозначены квадратиками.

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

1. Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.

2. Вершина ИЛИ разрешима т.и т.т., когда разрешима по крайней мере одна из ее дочерних вершин.

3. Вершина И разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин.

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

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

Дата добавления: 2014-01-07