Лекция 15. Методы поиска решений в экспертных системах. 1 страница

Термины: метазнания, метпространство.

План темы:

· 15.1. Классификация методов поиска решений, используемых в экспертных системах, символы и поиск.

· 15.2. Методы поиска.

· 15.3. Поиск решения в одном пространстве.

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

· 15.5. Эвристический поиск.

· 15.6. Поиск методом "генерация - проверка".

· 15.7. Поиск в иерархий пространств.

· 15.8. Поиск в факторизованном пространстве.

· 15.9. Поиск в фиксированном множестве пространств.

· 15.10. Поиск а изменяющемся множестве иерархических пространств.

· 15.11. Роль ограничений при поиске.

· 15.12. Принцип наименьших свершений.

· 15.13. Метапространство в иерархии пространств.

· 15.14. Поиск в альтернативных пространствах.

Вспомнить вопросы:

· Что такое граф?

15.1. Классификация методов поиска решений, используемых в экспертных системах, символы и поиск.

Анализ работ в области искусственного интеллекта, проведенный Ньюэллом и Саймоном [1976], позволил им выделить два основных понятия: символические системы и поиск. Символическая система есть набор символов, образующих символические структуры, и набор процессов. Причем процессы способны производить, разрушать и модифицировать символические структуры. Символ есть первичное понятие. Примером символа является строка буквенно-цифровых знаков (список, изделие - 35, 3, 14 и т.п.). Символическая структура представляет собой некоторое число символов, соотнесенных определенным физическим способом (например, один символ следует за другим). Примером символических структур являются следующие наборы символов: (ИДЕНТИЧНОСТЬ МИКРООРГАНИЗМ-1 Е. СОLI); (ПЛЮС X Y); (РАВЕН (НИКОЛАЙ) (НАЧАЛЬНИК (ОТДЕЛ 237)). Символическая структура может рассматриваться как тип данных в некотором языке. Символические структуры обладают двумя основными свойствами: 1) они могут обозначать (designate) объекты, процессы и другие символические структуры; 2) если они обозначают процессы, то они могут быть интерпретированы. Символическая структура обозначает некоторую сущность (объект, процесс или символическую структуру), если символическая система может осуществлять поведение, определяемое данной сущностью, или может воздействовать на эту сущность. Система может интерпретировать символическую структуру, если структура обозначает некоторый процесс, и система может выполнить этот процесс.

Ньюэлл и Саймон [1976] высказали две гипотезы, на которых базируются исследования по искусственному интеллекту:

1. Гипотеза символических систем. Символические системы имеют необходимые и достаточные средства для осуществления интеллектуальных действий.

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

Приведенные гипотезы разделяются многими специалистами в области искусственного интеллекта. По-видимому, можно утверждать, что все существующие экспертные системы подтверждают гипотезы Ньюэлла и Саймона.

15.2. Методы поиска.

Методы решения задач, основанные на сведении их к поиску, зависят от особенностей проблемной области, в которой решается задача, и от требований ограничений, предъявляемых пользователем к решению. Особенности проблемной области с точки зрения методов решения можно характеризовать следующими параметрами: 1) размер; 2) изменяемость области; 3) полнота модели, описывающей область; 4) определенность данных о решаемой задаче. Параметр "размер" характеризует размер пространства, в котором предстоит искать решение. Параметр "изменяемость" характеризует степень изменяемости области во времени и пространстве. По параметру "изменяемость" будем выделять статические и динамические области. Параметр "полнота модели" характеризует адекватность модели, используемой для описания данной проблемной области. Обычно, если модель не полна, то для описания области используют несколько моделей, дополняющих друг друга за счет отражения различных свойств проблемной области (например, модель, описывающая электрическую схему двигателя, и модель, определяющая его механическую схему), Параметр "определенность данных" характеризует степень точности или ошибочности и полноты или неполноты данных. "Точность" является показателем того, что проблемная область с точки зрения решаемых задач описана точными данными. "Ошибочность" является показателем того, что данные о проблемной области не точны. Под "полнотой" (неполнотой) данных понимается достаточность (недостаточность) входных данных для однозначного решения задачи. Обычно при неполноте данных для поиска решения необходимо использовать некоторые предположения или ограничения.

Требования пользователя к результату задачи, решаемой с помощью поиска, можно характеризовать "количеством решений" и свойствами результата" (и/или способом его получения). Параметр "количество решений" может принимать следующие основные значения: одно решение, несколько решений, все решения. Параметр "свойства" задает ограничения, которым должен удовлетворять полученный результат или способ его получения. Так, например, для системы, выдающей рекомендации по лечению больных, пользователь может указать требование не использовать некоторое лекарство (в связи с его отсутствием или в связи с тем, что оно противопоказано данному пациенту). Параметр "свойства" может определять и такие особенности, как время решения ("не более чем", "диапазон времени" и т.п.), объем памяти, используемой для получения результата, указание об обязательности (невозможности) использования каких-либо знаний (данных) и т.п.

Итак, сложность задачи можно характеризовать примерно следующим набором параметров: 1) размер пространства, в котором решается задача; 2) изменяемость области; 3) полнота модели; 4) определенность данных; 5) количество необходимых решений; 6) ограничения на результат и способ его получения. Во введенных терминах сложность задачи колеблется от простых задач (малая область, статическая область, полная модель, определенные данные, какое-нибудь решение, отсутствие ограничений на результат и способ его получения) до сложных задач (большая область, динамическая область, неполнота одной модели, ошибочные и неполные данные, все решения, произвольные ограничения на результат и способ его получения), Ясно, что каким-либо одним методом нельзя решить все задачи. Обычно одни методы превосходят другие только по некоторым из перечисленных параметров. Например, методы поиска в иерархии пространств лучше методов поиска в одном пространстве в отношении большей размерности, а методы поиска в альтернативных пространствах позволяют работать с ошибочными и локально неполными областями.

Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом:

1. Методы поиска в одном пространстве - методы, предназначенные для использования в следующих условиях: малые области, статические области, полнота модели, точные и полные данные.

2. Методы поиска в иерархических пространствах - методы, предназначенные для работы в больших статических областях.

3. Методы поиска при неточных и неполных данных.

4. Методы поиска в динамической проблемной области - методы, предназначенные для работы с областями, изменяемыми во времени и (или) в пространстве.

5. Методы поиска, использующие несколько моделей, предназначенные для работы с областями, для адекватного описания которых одной модели недостаточно.

Предполагается, что перечисленные методы при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким из перечисленных выше параметров.

15.3. Поиск решения в одном пространстве.

Поиск в пространстве состояний.

Задача поиска в пространстве состояний может быть сформулирована так (см. [Нильсон, 1973. Попов и Фирдмак, 1976]), Пусть задана тройка (S₀, F S_T), где S₀ - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, S_T - множество конечных (целевых) состояний (решений задачи). В этой постановке решить задачу значит определить такую последовательность операторов, которая преобразует начальные состояния в конечные. Процесс решения можно представить в виде графа G = (X, У), где X = { х₀, х₁,...} - множество, в общем случае бесконечное, вершин графа, каждая из которых отождествляется с одним из состояний, а У - множество, содержащее пары вершин (x_i,x_j), x_i,x_j Î X. Если каждая пара (x_i,x_j) неупорядочена, то ее называют ребром, а граф называют неориентированным. Если для каждой пары (x_i,x_j) задан порядок, то пару (x_i,x_j) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным), Вершины пары (x_i,x_j) называют концевыми точками ребра (дуги), Поиск в пространстве состояний более естественно представлять в виде ориентированного графа. Наличие пары (x_i,x_j) свидетельствует о существовании некоторого оператора f(fÎF), преобразующего состояние, соответствующее вершине x_i, в состояние x_j. С точки зрения поиска в пространстве состояний для некоторой вершины x_i уместно выделить множество всех направленных пар (x_i,x_j), (x_i,x_j) Î У т.е. множество дуг, исходящих из вершины х_i, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины x_i, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине x_i. В множестве вершин X выделяют подмножество вершин Хо Í X, соответствующее множеству начальных состояний (S₀), и подмножество вершин Х_T Í X соответствующее множеству конечных (целевых) состояний (S_T). Множество X_T может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

Определим на графе G маршрут L как такую последовательность ребер, что каждые два соседних ребра имеют общую концевую точку. Будем обозначать путь L как последовательность (x_i1,x_j2…x_i(k+1))), где пара (x_i(j-1), x_ij) Î У, j = 2,..., к + 1. Будем говорить, что маршрут L имеет длину к и соединяет вершины (состояния) x_i1 и x_i(k+1). В случае ориентированного графа маршрут называют путем. Очевидно, что решение задачи методом поиска в пространстве состояний (т.е. нахождение последовательности операторов, преобразующей начальное состояние в конечное) сводится к задаче поиска пути L на графе G. Путь из х₀ Î Х_о в х_т Î Х_т называют решающим (целевым). Часто бывает удобно приписывать дугам графа веса отражающие стоимость применения соответствующих операторов. Для обозначения стоимости дуги, направленной из x_i; в x_j, используют запись с (x_i,x_j). Стоимость пути между двумя вершинами определяется как сумма стоимости вех дуг, образующих этот путь. В ряде приложений возникает задача нахождения путей (пути), имеющих минимальную стоимость, между любыми элементами из множества Хо и любыми элементами из множества Хт. Отметим, что граф G может быть задан как в явном виде, так и неявно. Неявное задание графа G состоит в определении множества Х₀ и множества операторов, которые будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решений. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина из х₀ Î Х₀, к ней применяются все возможные операторы, порождающие все дочерние вершины. Порождение всех дочерних вершин для некоторой вершины x_i называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают ли6о временем. либо объемом памяти, В практических приложениях часто требуется обеспечить полноту поиска, т.е. организовать поиск так, чтобы все: целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный перебор всех вершин, Для задания процесса перебора необходимо определить порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа поиска: поиск в глубину и поиск в ширину. При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. Глубина вершины в графе определяется так: 1)глубина начальной вершины равна нулю; 2) глубина не начальной вершины равна единице плюс глубина наиболее близкой родительской вершины. При практической реализации поиск в глубину в некотором направлении завершается в следующих случаях: 1) при достижении целевой вершины; 2) при достижении терминальной вершины; 3) при построении в ходе поиска вершины, глубина которой превышает некоторую граничную глубину. При поиске в ширину вершины раскрываются, в том же порядке, в котором они порождаются (Нильсон, 1973). Если в пространстве состоянии ввести операторы, переводящие состояние S_i в предшествующее состояние S_i-1, то поиск можно осуществлять не только в направлении от начального достояния к целевому, но и в обратном направлений. Поиск первого типа называют поиском от данных (или прямым поиском), а поиск второго типа- поиском от цепи (или обратным поиском). Более того, можно организовать поиск в обоих направлениях одновременно. Такой поиск называют двунаправленным (или бинаправленным).

Рис. 15.1. Пространство состояний, построенное:

(а) поиском в глубину и (б) поиском в ширину.

На рис. 5.1 приведен пример решения задачи поиском в глубину (рис. 5.1, а) и в ширину (рис. 5.1, б). Вершины пронумерованы в том порядке, в котором они раскрываются (не порождаются), целевые вершины помечены заштрихованными квадратами, а терминальные - белыми квадратами(При использовании каждого из способов могут быть найдены все решения. При переборе всего пространства оба метода будут анализировать одинаковое количество вершин, однако метод поиска в ширину будет требовать существенно больше памяти, так как он запоминает все пути поиска (а не один, как при поиске в глубину).

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

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач (Нильсон, 1973). Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ графом. Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Конъюнктивные вершины или вершины типа "И", вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины. Дизъюнктивные вершины или вершины типа "ИЛИ", вместе со своими дочерними вершинами интерпретируются так: решение задачи сводится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины [Слейгл, 1973; Уинстон, 1980]. Обратим внимание читателей, что некоторые авторы [Нильсон, 1973, 1980] определяют вершины И и вершины ИЛИ иначе. В множестве вершин И/ИЛИ графа выделяют подмножество начальных вершин, т.е. задач, которые следует решить, и подмножество конечных (целевых) вершин, т.е. заведомо разрешимых задач. Решение задачи при поиске методом редукции (при поиске в И/ИЛИ графе) сводится к нахождению в И/ИЛИ графе решающего графа, определение которого будет дано ниже. Заметим, что метод сведения задач к подзадачам является в некотором роде обобщением подхода с использованием пространства состояний. Действительно, перебор в пространстве состояний можно рассматривать как тривиальный случай сведения задачи всегда к одной подзадаче.

Графически для различения дизъюнктивной и конъюнктивной вершин дуги, исходящие из конъюнктивной вершины, соединяются дужкой при вершине. Пример графического представления разбиения задачи на подзадачи приведен на рис. 5.2. Здесь.S₀ - исходная задача, для решения которой требуется решить подзадачу S₃ или подзадачи S₁ к S₂ Решение S₁ сводится к решению либо подзадачи S₄, либо подзадачи S₅. Решение подзадачи S₃ сводится к решению подзадач S₆ и S₈. Решение задач S₂, S₅, S₇ предполагается известным, решение задач S₄ и S₆ неизвестно. В приведенном примере задача S₀ может быть решена либо путем решения задачиS₃, либо путем решения задачи S₁ и S₂. В связи с тем, что в И/ИЛИ графе каждая вершина относится только к одному типу (либо И, либо ИЛИ), то для записи графа, изображенного на рис. 5.2 в виде И/ИЛИ графа, надо ввести дополнительную вершину (см. вершина R₁ на рис. 5.3). На рис. 5.3 двойными линиями выделен решающий граф задачи Sо, а конечные вершины обозначены квадратиками.

Рис.15.2 Графическое представление процесса разбиения задачи на подзадачи.

Рис.15.3.Пример И/ИЛИ графа.

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

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

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

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

4.Итак, решающий граф определяется как подграф из разрешимых вершин, который показывает, что начальная вершина разрешима (в соответствии с приведенным выше определением). На рис. 5.3 разрешимые вершины зачернены, а неразрешимые не зачернены. Можно привести более строгое определение решающего графа [Чэнг и Слейгл, 1971; Попов и Фирдман, 197б].Для некоторой подзадачи может быть неизвестно ни ее решение, ни способ сведения ее к более простым подзадачам. Такая подзадача называется неразрешимой. Определение неразрешимой вершины в И/ИЛИ графе можно сформулировать рекурсивно следующим образом:

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

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

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

Рис.5.4а Поиск в ширину для И/ИЛИ графа.

Рис.5.4б Поиск в глубину для И/ИЛИ графа.

Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. |На рис. 5.4 приведен пример поиска в ширину (рис. 5,4, а) и поиска в глубину (рис. 5.4, б), на рисунке вершины пронумерованы в том порядке, в котором они раскрывались; конечные вершины обозначены квадратиками, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями. Более подробно с методами поиска читатели могут ознакомиться по книгам Нильсона [1973,1980]. Метод поиска в глубину в И/ИЛИ графе использован в ряде популярных экспертных систем, таких, как: МУСIN, Е МУСIN (см, § 1,5 и гл. 2), РUFF [Фрейхер, 1980].

15.5. Эвристический поиск.

Методы поиска в глубину и ширину называют слепым поиском, поскольку в этих методах порядок раскрытия вершин предопределен и никак не зависит от расположения цели. При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и (или) памяти. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию проблемной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят к цели. Один способ сокращения перебора состоит в выборе более "информированного" оператора, который не строит так много вершин, не относящихся к делу, Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру "перспективности" вершины в виде некоторой оценочной функции. В некоторых случаях удается ввести такую оценочную функцию, что она, сокращая перебор, не теряет свойства полноты. Чаще же используемые эвристики, сильно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить расстояние от текущей вершины по конечной. Из двух вершин при одинаковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частости для экспертных систем, применение количественных оценок не позволяет эффективно направлять процесс поиска.

15.6. Поиск методом "генерация - проверка".

Процесс поиска может быть сформулирован в терминах "генерация - проверка". Действительно, пространство поиска (пространство состояний или И/ИЛИ граф), как правило, явно не задано. Поэтому для осуществления процесса поиска необходимо генерировать очередное возможное решение (состояние или подзадачу) и проверить, не является ли оно результирующим. Разумно потребовать, чтобы генератор удовлетворял требованиям полноты и неизбыточности. Говорят, что генератор является полным, если он обеспечивает генерацию всех возможных решений. Генератор является неизбыточным, если он генерирует каждое решение только один раз. Обеспечение свойства неизбыточности является важным, но трудно выполнимым, так как в соответствии с этим требованием не допускается генерация не только тождественных, но и синонимичных решений. Например, если задача генератора - синтезировать все фразы русского языка, то весьма трудно (если вообще возможно) сделать такой генератор неизбыточным.

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

Можно выделить важную форму метода "генерация - проверка", называемую иерархическая "генерация - проверка" (см. п. 5.3.1). В этом случае на верхнем уровне генератор вырабатывает не полное, а частично определенное решение (будем для краткости называть такие решения частичными). Каждое частичное решение описывает, например, не все состояние, а только его некоторую часть, определяя таким образом класс возможных состояний. Идея состоит в том, что устройство проверки может уже по виду частичного решения определить, что оно (а следовательно, и все полные решения, которые могут быть получены из него) не ведет к успеху. Если же проверка не отвергает частичное решение, то на следующем уровне генератор продолжает вырабатывать из данного частичного решения все полные решения, а устройство проверки определяет, являются ли они целевыми.

15.7. Поиск в иерархии пространств.

Методы поиска в одном пространстве не позволяют решать сложные задачи, так как с увеличением размера пространства время поиска экспоненциально растёт. При большом размере пространства поиска можно попробовать разбить общее пространство на подпространства и осуществлять поиск сначала в них. Можно сказать, что в данном случае пространство поиска представлено иерархией пространств. Важность иерархических методов при работе с большими, пространствами понята давно. В 1963 г. Минский писал, что введение "островков планирования" уменьшает время поиска по экспоненте: "В графе с 10 ребрами, исходящими из каждой вершины, 20-щаговый поиск может потребовать 10²⁰ попыток, что нереально реализовать, в то время как введение четырех лемм, или последовательных подцелей может уменьшить поиск до 5*10⁴ попыток, которые машина может выполнить. Поэтому имеет смысл приложить даже огромные усилия, чтобы выявить такие "островки" при решении сложных задач" [Минский, 1967, с. 447]. Идею Минского о иерархии пространств можно развить, допустив в иерархии не только конкретные, но и абстрактные пространства, т.е. пространства которые имеют описание только наиболее важных сущностей. Использование неполных описаний позволяет сократить пространство и (или) сделать операторы в нем более мощными, что приводит к дополнительному ускорению решения задачи. В качестве классического примера использования абстрактных пространств можно привести задачу определения кратчайшего пути на карте. Пусть требуется переехать из центра города А в центр города В. Если осуществлять поиск требуемого пути на детальной карте, содержащей все улицы во всех городах, встретившихся по дороге, то задача может стать практически неразрешимой. При определении пути из города А в город В целесообразно спланировать маршрут по крупномасштабной карте (т.е. осуществить поиск в абстрактном пространстве), а затем по детальной карте спланировать выезд из города А и въезд в город В.

В данном параграфе будут рассмотрены методы, использующие общую идею иерархии пространств, но отличающиеся природой пространств. Отметим, что иерархические методы поиска использованы в ряде экспертных систем.

15.8. Поиск в факторизованном пространстве.

Во многих приложениях требуется найти все решения. Примерами таких областей являются интерпретация данных, постановка диагноза и др. Действительно, в случае постановки диагноза нас интересуют все, а не некоторые болезни пациента. Однако пространство поиска в практических приложениях бывает столь велико, что не позволяет применить слепые методы поиска. Применение эвристических методов в данном случае, как правило, также исключено, так как они не обеспечивают получение всех возможных решений. Если пространство поиска удается факторизовать, то поиск даже в очень большом пространстве можно организовать эффективно. Пространство называется факторизованным, если оно разбивается на непересекающиеся подпространства (классы) частичными (неполными) решениями (см. п. 5.2.4). Причем по виду частичного решения можно определить, что оно не приведет к успеху, т.е. что все полные решения, образованные из него, не приведут к целевым решениям. Поиск в факторизованном пространстве осуществляется на основе метода иерархическая "генерация-проверка". Генератор вырабатывает текущее частичное решение, затем проверяется, может ли это решение привести к успеху. Если текущее частичное решение отвергается, то из рассмотрения без генерации и проверки устраняются все полные решения этого класса. Если текущее частичное решение не отвергается, то генератор вырабатывает на его основе все полные решения, а устройство проверки определяет, являются ли эти решения целевыми. Решение задачи поиском в факторизованном пространстве использовано в экспертной системе GА1 [Стефик, 1978].

Дата добавления: 2014-10-31