2. Стратегия управления с поиском на графе

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

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

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

Если ребро направлено от вершины n_i кn_j, то вершинаn_jназываетсяпереемником вершиныn_i, а вершинаn_i–родителемn_j. В графе, представляющем для нас интерес, у любой вершины может быть лишь конечное число переемников. Обе вершины в паре могут быть одновременно переемниками друг друга. В этом случае пара направленных ребер заменяется одним ненаправленным ребром.Дерево– это частный случай графа, в котором каждая вершина имеет не более одного родителя, и граф не содержит циклов. Вершина дерева, не имеющая родителя, называетсякорневой, а не имеющая переемников –концевой. Корневой вершине соответствует глубина равная нулю, глубина любой другой вершины дерева определяется как глубина родительской вершины плюс один.

Последовательность вершин n_i1,n_i2,...,n_{i k}(где каждая вершинаn_ijявляется переемником вершиныn_{i j-1}дляj=2,...,k) называетсяпутем длинойkотn_i1кn_{i k}.

Если существует путь от вершины n_iкn_j, то вершинаn_jдостижима из вершиныn_iи является еёпотомком.

Часто оказывается удобным приписать положительные «стоимости» дугам для того, чтобы отразить «стоимость» применения соответствующего правила. Будем использовать обозначение С(n_i,n_j) для стоимости дуги, направленной от вершиныn_iкn_j. «Стоимость» пути между двумя вершинами равна сумме «стоимостей» всех дуг, соединяющих вершины, лежащие на данном пути. Во многих задачах искусственного интеллекта требуется не просто найти какой – либо путь от исходной базы данных к целевой, а путь, который обладает минимальной «стоимостью».

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

Это неявное описание дается с помощью начальной вершины s, представляющей собой исходную базу данных и правил, изменяющих базу данных. Удобно ввести понятие оператора построения (оператора раскрытия) переемников, применение которого к некоторой вершине выявляет всех переемников этой вершины вместе со «стоимостями» соответствующих дуг в явном виде. Процесс применения оператора построения к некоторой вершине называетсяраскрытием этой вершины.