ПОИСК Статьи Рисунки Таблицы Методика и процедуры поиска решений неформализованных задач из "Экспертные системы в химической технологии" Каждому сгенерированному семантическому решению НФЗ можно поставить в соответствие некоторую математическую модель, реализованную на ЭВМ в виде вычислительной программы, и разработать алгоритм, обеспечивающий выполнение операций над данными. Данные представляют собой конкретную фактографическую информацию об объекте, которая должна быть независима и целостна по отношению к вычислительным программам. База данных (БД) — это именованная централизованная совокупность данных, отображающая состояния объектов и их отношений в рассматриваемой ПО. [c.68] Язык данных задает правила определения поискового критерия и указания элементов данных, значения которых должны быть получены в результате поиска. Более того, в тех случаях, когда поисковый запрос из-за ограниченности ЯД или по каким-либо другим причинам не может быть удовлетворен одним предложением ЯД, должно быть известно, как реализовать этот запрос в вычислительной программе с помощью некоторых предложений ЯД и, возможно, некоторых фрагментов программы, обеспечивающих прием промежуточных данных от предыдущих предложений, их анализ, обработку и передачу последующих предложений. [c.69] Следовательно, любой ЯД предполагает определенную структуризацию данных. При этом должно быть строго определено, в каких совокупностях данных производится поиск, инициируемый тем или иным предложением ЯД, какие совокупности данных являются результатом поиска и какие элементы данных могут указываться в формулировке поискового критерия. Такое определение описывает способ логической структуризации данных, тесно связанный с конкретным ЯД и с реализующей его СУБД. [c.69] Совокупность способа логической структуризации данных и функциональных возможностей манипуляции данными, т. е. принципиальных особенностей ЯД без учета его синтаксиса, называется людаыо данных. Имеется прямая аналогия между понятием модель данных , используемым в технологии БД, и понятием модель представления знаний , используемым в новой информационной технологии и в теории искусственного интеллекта 9]. Действительно, описание организации данных и данные, хранимые в БД,— это формальная запись знаний, образующих в совокупности определенную систему. Способу логической структуризации данных соответствует набор формальных правил записи знаний, а функциональным возможностям манипуляции данными соответствуют примитивы манипуляции знаниями. [c.69] Известны два типа эквивалентных реляционных ЯД язык реляционной алгебры мязык реляционного исчисления [9, 15]. Любой запрос, выраженный одним предложением на языке реляционной алгебры, можно выразить одним предложением и на языке реляционного исчисления, и наоборот. Тем не менее указанные языки существенно различаются в некоторых аспектах, в частности по сложности программной реализации и простоте использования [9, 13]. Общее свойство реляционных ЯД — создание нового отношения в результате выполнения любой операции поиска. Это свойство служит основой для важной конструкции реляционной модели — виртуального отношения. [c.70] е одно важное свойство реляционных ЯД — их высокие выразительные возможности для представления поискового критерия запроса. Допустимая сложность поискового предиката, определяющего содержание запроса, здесь существенно выше, чем для большинства других моделей данных [9]. В частности, такой пре дикат может связывать практически произвольное число отношений БД. Элементами поискового предиката являются квантифицированные переменные (строки отношений) и функции на отношениях. Благодаря этому в реляционной модели данных практически исключается использование сложных процедур, составленных из предложений ЯД. В большинстве случаев процедуры поиска определенных знаний или их модификации могут быть реализованы одним предложением реляционного ЯД [91. [c.71] Методика решения НФЗ основана на использовании принципа многоуровневой декомпозиции исходной задачи и процедур поиска решений НФЗ в пространстве состояний с применением ЭП анализ состояния — выбор средства . -Методику и процедуры поиска решений НФЗ наглядно отображают с использованием различных типов семантических деревьев, или графов решений НФЗ. [c.71] Сущность принципа многоуровневой декомпозиции при поиске решения НФЗ состоит в том, что решение исходной задачи —Рц сводят к поиску решений образующих ее подзадач меньшей размерности—Р1, Р2.Р , в целом представляющих всю задачу. Процедуру декомпозиции повторяют для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное, или тривиальное, решение. [c.71] Решение задачи с использованием метода декомпозиции при поиске в И/ИЛИ графе сводится к нахождению в И/ИЛИ графе решающего подграфа, определение которого приведено ниже. Заметим, что метод решения НФЗ сведением исходной задачи к совокупности подзадач является в некотором смысле обобш,ением метода решения НФЗ с использованием пространства состояний. Действительно, перебор в пространстве состояний можно рассматривать как тривиальный случай сведения задачи всегда к одной подзадаче. При изображении И/ИЛИ графа ветви, исходяш,ие из И -вершины, соединяются дугой при вершине. [c.72] Пример дерева декомпозиции исходной НФЗ на подзадачи приведен на рис. 2.10. Здесь Ро — исходная НФЗ, для решения которой требуется решить или подзадачу Р , или подзадачи Р и Р2. Решение подзадачи сводится к решению подзадачи или подзадачи Р,. Решение подзадачи Р, сводится к решению подзадач Рй иРу. Решение задач Р2, Р5, Р7 предполагается известным, решение задач Р4 и Р,, неизвестно. В приведенном примере задача Рд может быть решена или путем решения задачи Р,, или путем решения задач Р) и Р2. В связи с тем что в И/ИЛИ графе каждая вершина относится только к одному типу (либо И , либо ИЛИ ), для представления графа, изображенного на рис. 2.10, в виде И/ИЛИ графа надо ввести дополнительную вершину (см. на рис. 2.11). На рис. 2.11 двойными линиями выделен решающий подграф задачи Р( а конечные вершины обозначены двойными кружками. [c.72] решающий подграф И/ИЛИ графа —это подграф из разрешимых вершин, который показывает, что начальная вершина разрешима в соответствии с приведенным выше определением (на рис. 2.11 разрешимые вершины заштрихованы, а неразрешимые не заштрихованы). Для некоторой подзадачи могут быть неизвестны ни ее решение, ни способ сведения ее к более простым подзадачам. Такую подзадачу называют неразрешимой. Определение неразрешимой вершины в И/ИЛИ подграфе можно сформулировать рекурсивно следующим образом 9) 1) вершины, не являющиеся конечными и не имеющие вершин-потомков, неразрешимы 2) ИЛИ -вершина неразрешима тогда и только тогда, когда неразрешима каждая из ее вершин-потомков 3) И -вершина неразрешима тогда и только тогда, когда неразрешима хотя бы одна из ее вершин-потомков. [c.73] Поиск решений НФЗ в пространстве состояний отображается с помощью семантического графа, называемого деревом вариантов решений. [c.73] Множество дуг, исходящих вершины х,, отображает множество операторов, которые могут быть применены к состоянию, отображаемому вершиной х,-. В множестве вершин X выделяют подмножество вершинХо СХ, отображающее множество начальных состояний (. 0), и подмножество вершин Х,СХ, отображающее множество конечных (целевых) состояний (. ,). МножествоХ, может быть задано как явно, так и неявно, т. е. через свойства, которыми должны обладать целевые состояния. [c.74] Очевидно, что решение НФЗ методом поиска в пространстве состояний сводится к процедуре поиска пути L в графе С/. Путь из еЛ п вх,сХ, называют решающим (целевым). Часто бывает удобно приписывать дугам графа определенные веса, которые равны стоимости применения соответствующих операторов. Для обозначения веса с дуги, направленной из. г,- в XJ, используют запись с(х Xj). Стоимость пути между двумя вершинами определяется как сумма стоимостей всех дуг данного пути. В ряде приложений возникает задача нахождения путей (пути), имеющих минимальную стоимость, между любыми элементами из множестваХц и любыми элементами из множествах,. Отметим, что граф О может быть задан как в явном виде (эксплицитно), так и в неявном (имплицитно). Неявное задание графа О состоит в определении множества Хо и множества операторов, которые, будучи применимы к некоторой вершине графа, порождают все ее вершины-потомки. [c.74] Практически при решении НФЗ необходимо обеспечить полноту поиска, т. е. организовать поиск так, чтобы все целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный упорядоченный перебор всех вершин графа. Для каждой операции упорядоченного перебора необходимо определить порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа перебора вершин поиск в глубину (или односторонним обходом ) и поиск в ширину (или полным фронтом ). [c.75] При поиске в ширину вершины раскрываются в том же порядке, в котором порождаются. Если в пространстве состояний ввести операторы, переводящие состояние 5, в предшествующее состояние 5/ 1, то поиск можно осуществлять как в направлении от начального состояния (от исходных данных) к целевому, так и в обратном направлении. Стратегию поиска от исходных данных к цели называют прямш1 поиском , а стратегию поиска от цели к данным — обратным поиском . Более того, можно организовать поиск в обоих направлениях одновременно. Такую стратегию называют двунаправленной. [c.75] На рис. 2.12 для графа типа ИЛИ приведен пример поиска решения задачи способом в глубину (рис. 2.12, а) и в ширину (рис. 2.12, б). Вершины пронумерованы в том порядке, в котором они раскрываются целевые вершины помечены заштрихованными квадратами, терминальные —белыми квадратами. При использовании каждого из способов могут быть найдены все решения НФЗ. При переборе всего пространства оба способа будут анализировать одинаковое число вершин, однако способ поиска в ширину будет требовать существенно больше памяти, так как он учитывает все пути поиска (а не один, как при поиске в глубину ). [c.75] Вернуться к основной статье