Мивары: 25 лет создания искусственного интеллекта - [44]
Доходим до ключевого понятия: "На примере мы описали процедуру, которая … носит универсальный характер и пригодна для поиска пути вывода в лабиринтах произвольного типа. Эта процедура известна среди специалистов под названием метода прямой волны. Волна поиска путей к целевой площадке распространяется от всех площадок, играющих роль начальных" [328, стр. 85].
Совершенно логично Поспелов Д.А. пишет: "Возможен и другой способ поиска доказательства. Он носит название метода обратной волны. В этом методе волна начинает свое движение от целевых площадок и движется в направлении начальных площадок лабиринта. Для нашего случая на первом шаге была бы порождена площадка, соответствующая F5, вслед за этим F3 и F1. На этом движение волны прекратилось бы, так как ее фронт достиг всех (в данном случае единственной F1) начальных площадок.
Различие между прямой и обратной волной состоит в том, что они порождают в процессе своего движения различные промежуточные "фронты" площадок, что приводит к различному числу шагов при поиске. Часто используется смешанный метод вывода, при котором одновременно движутся прямая и обратная волны. При встрече этих волн формируется путь вывода от начальных аксиом к целевым выражениям" [328, стр. 85].
Отметим, что эти работы не нашли широкого практического применения в прошлом веке. Это обусловлено тем, что не было предложено метода быстрой логической обработки данных. Как было показано выше, ученые исходили из предпосылки, что любой вывод носит переборный характер, что означает факториальный рост вычислительной сложности при увеличении количества переменных. Даже современные суперкомпьютеры при таком подходе позволяют обрабатывать в реальном масштабе времени (или хотя бы в близком к реальному), лишь 10-15 переменных. Фактически, это позволяет решать только "игрушечные" модельные задачи, т.к. современные требования начинаются с сотен и достигают десятков тысяч переменных даже для относительно простых предметных областей.
5.5. Представление продукций и сетей продукций в виде двудольных графов и сетей Петри
Перейдем к формализованному представлению продукций и сетей, которые могут быть сформированы из них. Выше было отмечено, что Поспелов Д.А. [328, стр. 83-84] представляет сеть правил в таком виде, что она отображается в виде однодольного графа. В работах [72, 63, 134, 303, 279] предложен подход по взаимосвязи сетей правил и графов. Более того, показано, что некоторые задачи логического вывода можно решать на основе подходов теории графов. Сети правил и процедур целесообразнее представлять в виде двудольных графов, получая нечто аналогичное сетям Петри, но с соответствующим развитием до миварных логических сетей [72, 63, 134, 303, 279]. Итак, напомним определения двудольных графов, которые необходимы для продолжения анализа. "Граф G=(V, E) называется двудольным, если существует разбиение V={V1, V2} такое, что никакие две вершины из V1 или из V2 не являются смежными" [247, стр. 223].
"Двудольным графом G=(X, Y, E) называется неориентированный граф, вершины которого можно разбить на два класса X и Y так, что концы каждого ребра принадлежат разным классам" [244, стр. 125]. Приведем следующее важное замечание: "введенные понятия допускают естественное обобщение. Неориентированный граф называется k ‐дольным, если его вершины можно разбить на k классов так, что концы каждого ребра принадлежат разным классам" [244, стр. 125]. Таким образом, можно использовать и двудольные, и трехдольные и многодольные (k ‐дольные) графы для разных предметных областей.
5.6. Переход от продукций к миварным логическим сетям. Описание миварного метода логико-вычислительной обработки информации
Как было сказано выше, миварные логические сети могут быть представлены в виде двудольного графа, состоящего из объектов-переменных и правил-процедур. Для этого прежде всего составляются два списка, которые и образуют две непересекающиеся доли графа: список объектов и список правил. Каждое правило в миварной логической сети является развитием продукций, гиперправил с мультиактивизаторами или вычислительных процедур. Доказано, что с точки зрения дальнейшей их обработки все эти формализмы идентичны и представляют собой, по сути, вершины двудольного графа, которые изображены прямоугольниками на рисунке 61.
Рисунок 61 – Представление миварной логической сети в виде двудольного графа
Покажем, что для Многомерной эволюционной прикладной автоматизированной информационной системы поддержки принятия решений наиболее адекватным является формализм «миварные логические сети».
Теоретические основы миварного метода логико-вычислительной обработки информации (миварного метода) были впервые опубликованы в [72] и [63] еще в 2002 году. В статье [63] представлены теоретические основы создания линейного матричного метода определения маршрута логического вывода на адаптивной сети правил. Суть метода в том, что для сети правил, представленной в списочной форме, строится матрица. Затем, путем анализа этой матрицы определяется факт наличия маршрута вывода, определяются возможные маршруты логического вывода и из этих маршрутов выбирают по заданным критериям оптимальности лучший, кратчайший, маршрут. Пусть известны
