Конъюнктивная вершина
Cтраница 1
 |
Графическое представление процесса разбиения задачи на подзадачи [ IMAGE ] Пример И / ИЛИ графа. [1] |
Конъюнктивные вершины, или вершины типа И, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Обратим внимание читателей, что некоторые авторы [ Нильсон, 1973, 1980 ] определяют вершины И и вершины ИЛИ иначе. В множестве вершин И / ИЛИ графа выделяют подмножество начальных вершин, т.е. задач, которые следует решить, и подмножество конечных ( целевых) вершин, т.е. заведомо разрешимых задач. Решение задачи при поиске методом редукции ( при поиске в И / ИЛИ графе) сводится к нахождению в И / ИЛИ графе решающего графа, определение которого будет дано ниже. Заметим, что метод сведения задач к подзадачам является в некотором роде обобщением подхода с использованием пространства состояний. Действительно, перебор в пространстве состояний можно рассматривать как тривиальный случай сведения задачи всегда к одной подзадаче. [2]
Графически для различения дизъюнктивной и конъюнктивной вершин дуги, исходящие из конъюнктивной вершины, соединяются дужкой при вершине. Решение задачи Si сводится к решению либо подзадачи S4, либо подзадачи Ss. Решение подзадачи 8з сводится к решению подзадач 8б и S. В приведенном примере задача So может быть решена либо путем решения задачи 8з, либо путем решения задач Si и Sz. [3]
 |
Графическое представление процесса разбиения задачи на подзадачи [ IMAGE ] Пример И / ИЛИ графа. [4] |
Графически для различения дизъюнктивной и конъюнктивной вершин дуги, исходящие из конъюнктивной вершины, соединяются дужкой при вершине. [5]
 |
Графическое представление процесса разбиения задачи на подзадачи [ IMAGE ] Пример И / ИЛИ графа. [6] |
Конъюнктивные вершины, или вершины типа И, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Обратим внимание читателей, что некоторые авторы [ Нильсон, 1973, 1980 ] определяют вершины И и вершины ИЛИ иначе. В множестве вершин И / ИЛИ графа выделяют подмножество начальных вершин, т.е. задач, которые следует решить, и подмножество конечных ( целевых) вершин, т.е. заведомо разрешимых задач. Решение задачи при поиске методом редукции ( при поиске в И / ИЛИ графе) сводится к нахождению в И / ИЛИ графе решающего графа, определение которого будет дано ниже. Заметим, что метод сведения задач к подзадачам является в некотором роде обобщением подхода с использованием пространства состояний. Действительно, перебор в пространстве состояний можно рассматривать как тривиальный случай сведения задачи всегда к одной подзадаче. [7]
Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Конъюнктивные вершины, или вершины типа И, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Дизъюнктивные вершины, или вершины типа ИЛИ, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины. Отметим, что некоторые авторы [4, 7] определяют вершины И и ИЛИ иначе. [8]
Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Конъюнктивные вершины, или вершины типа И, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Дизъюнктивные вершины, или вершины типа ИЛИ, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины. Отметим, что некоторые авторы [4, 7] определяют вершины И и ИЛИ иначе. [9]
Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Конъюнктивные вершины, или вершины типа И, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Дизъюнктивные вершины, или вершины типа ИЛИ, вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины. Отметим, что некоторые авторы [4, 7] определяют вершины И и ИЛИ иначе. [10]
Страницы: 1