Управление процессом решения задачи

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

Рассмотрим модель процедурных знаний, известную как рекурсивная сеть переходов (recursive transition network (RTN)). Каждой дуге RTN приписан некоторый предикат (функция), истинное значение которого необходимо для разрешения перехода по данной дуге. На каждом такте функционирования сети производится оценка всех предикатов. При этом порядок просмотра предикатов не имеет значения. В результате определяется множество маршрутов, соединяющих начальное и конечное состояния, переходы вдоль всех дуг которых разрешены. Рассмот­рим RTN на рис. 3. 1.

Рис. 3.1

Вершины сети соответствуют состояниям системы и образуют множество {начало, S₂, S₃, конец}. Переходы между состояниями по­мечены TR₁, TR₂, TR₃, TR₄ и TR₅.Переходу TR_iприписан предикат T_i ( ). Кроме того, с некоторыми из переходов связываются операто­ры A_i, которые выполняются при активации перехода. Допустим, что все предикаты T₁, ..., T₅ оказались истинными. В этом случае все маршруты, связывающие вершину-начало и вершину-конец, будут разрешены и все операторы А₂, А₃, А₄, А₅ будут выполнены. При этом оговаривается, что порядок выполнения операторов устанавливается согласно возрастанию их индексов. С другой стороны, если, например, ложен предикат Т₂, то будет активирован единственный маршрут (TR₁, TR₅) и возможно единственное действие A₅. Таким образом, уп­равление выводом в RTN реализуется посредством включения уп­равляющей структуры в модель знаний.

Сеть RTN является примером модели знаний со встроенной детерминированной процедурой управления. В графе И-ИЛИ проце­дура управления является недетерминированной. Пусть x₁, x₂, ..., x_N - объекты некоторой предметной области, причем для каждого объекта x_i известна одна или несколько процедур его вычисления через другие объекты. Обозначим через j_i (x_i1, x_i2, ..., x_it) процедуру вычисления объекта i через объекты x_i1, x_i2, ..., x_it. Каждый из объектов x_i1, x_i2, ..., x_it в свою очередь вычисляется аналогичным образом через другие объекты и т.д. Таким образом, имеется следующее функциональ­ное отношение

x_i = j_i (x_i1, x_i2, ..., x_it) (3.3)

Очевидно, что если процедура j_i не имеет входных данных, то объ­ект х_i представляет некоторое фиксированное значение, или запрашивается у пользователя. В этом случае

x_i = j_i ( ) (3.4)

Соотношению (3.3) соответствует графический фраг­мент, представленный на рисунке 3.3. Двойная дужка на рис. 3.3 соответствует конъюнктивной связке вершин (связке типа "И"). Очевидно, что вполне допустимо более одной процедуры вычисления объекта x_i, причем в процедуре j_j могут участвовать иные аргументы, чем в процедуре j_i; графически это соот­ветствует рис. 3.4.

Рис. 3.3 Рис. 3.4

Множество аргументов процедуры j_i и j_j, образуют дизъюнктивные связки (связки типа "ИЛИ"). Для вычисления объекта достаточно процедуры над одним альтернативным множеством объектов, входя­щих в одну общую конъюнктивную связку.

Формализуем задачу управления на функциональном "И - ИЛИ" графе. Пусть x₁, x₂, ..., x_N - множество объектов предметной области. Пусть даны процедуры

вычисления одних объектов через другие с числом аргументов, равным соответственно n₁, n₂, ..., n_k.

Определим состояние системы S_i как множество переменных, значения которых известны на шаге i. Пусть S₀ - начальное состояние, S_e - конечное состояние, причем конечное состояние в общем случае будет обозначаться как

S_e = {x_e1, x_e2, ..., x_ez, *}, (3.5)

где * - любое, заранее не оговариваемое множество переменных (возможно пустое), а x_e1, x_e2, ..., x_ez - множество переменных, которые обязательно должны быть определены в конечном состоянии.

Говорим, что процедура j_k (x_k1, x_k2, ..., x_km) валидна (применима) в состоянии S_j, если

(x_k1, x_k2, ..., x_km) Í S_j. (3.6)

Кратко тот факт обозначается как

S_j ^|¾ . (3.7)

В интересах общности далее положим, что каждая процедура j_i вы­числяет в целом более одной переменной. Ясно, что применение j_i - про­цедуры в состоянии S_j, в котором она валидна, приводит в общем слу­чае к новому состоянию S_j+1, содержащему результирующие перемен­ные процедурыj_i.

Задача управления заключается в построении цепочки процедур C = <j_i0, j_i1, ..., j_iz > такой, которая обеспечивает достижение конеч­ного состояния S_e из начального состояния S₀ в результате последова­тельного выполнения процедур из С в указанном порядке.

Рассмотрим решение этой задачи на конкретном примере. Предва­рительно договоримся, что обозначение

j_i <x_i1, x_i2, ..., x_in|x_in+1, x_i+2, ..., x_im> (3.8)

означает, что x_i1, x_i2, ..., x_in - это входные объекты-переменные проце­дуры, на основании которых вычисляются выходные объекты-перемен­ные x_in+1, x_in+2, ..., x_im.

Пусть задана следующая система функций:

j₁: <x₁, x₃|x₄>,

j₂: <|x₁, x₂, x₅>,

j₃: <x₁, x₃|x₄, x₆>,

j₄: <x₂, x₅|x₄, x₆>,

j₅: <x₂, x₇|x₄>,

j₆: <x₁, x₃, x₄|x₆, x₈>,

j₇: <x₃, x₆|x₅, x₇>,

j₈: <x₅, x₆|x₉>.

Поставим в соответствие ей функциональный граф "И - ИЛИ", по­казанный на рис. 3.5. Вершины графа соответствуют объектам предмет­ной области, а дуги маркированы таким образом, что над дугой, исходящей из вершины x_i и заходящей в вершину x_j, стоят индексы функций, в которых x_i является входным аргументом, а x_j выходным результатом. Например, дуга (x₁, x₄) помечена j₁, j₃, поскольку в этих функциях x₁ является входным аргументом, а x₄ - выходным. Пусть S₀ = <x₁, x₃, x₅>,аS_e = <x₇, x₉, *>. Построение цепочки функций С, вы­полняющей переход

(3.10)

осуществляется в два этапа.

Этап 1. Нормализация функционального графа.

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

(О₁) удаление пометок всех тех функций, для которых удалены од­на или более входных вершин-переменных;

(О₂) удаление всех входных дуг, инцидентных вершинам из S₀;

(О₃) удаление вершин x_i и инцидентных им дуг таких, что x_i Ï S_e, и не имеют выходных дуг;

(О₄) удаление тех функций, которые потеряли все свои резуль­тирующие вершины-переменные. Удалению функции соответствует уда­ление идентификатора функции из числа пометок дуг. Если при этом некоторая дуга оказывается непомеченной, то эта дуга удаляется;

(О₅) если удалена дуга, помеченная j, входящая в вершину x, то по­метка j снимается со всех дуг, входящих в x, если таковые есть;

(О₆) удаление (последовательное) альтернативныхвершин и ин­цидентных им дуг. Эта операция - основная. Вершина x является аль­тернативной, если в результате ее удаления и инцидентных ей дуг каждая вершина, в которую заходила дуга из х, может быть вычислена некоторой цепочкой С_i из состояния S₀.

Рис. 3.5.

Рассмотрим рис.3.5. Так, удаляем вершину х₈ согласно операции O₃. Удаляем далее входные дуги вершины x₅ Î S₀. Получаем граф на рис.3.6, а. Вершина х₂ альтернативная и может быть удалена вместе с инцидентными ей дугами. Получаемый в итоге граф на рис. 3.6, б. В нем вершина х₄ также альтернативная. Это последнее удаление приводит к полностью нормализованному графу на рис 3.6, в.

Рис. 3.6, а Рис. 3.6, б

Рис. 3.6, в

Этап 2. Построение уровней L₀, L₁, ..., L_k. В L₀ войдут все верши­ны, которые не имеют входных дуг.

В уровень L_i (i > 0) войдут все те и только те вершины х_i, которые не вошли в уровни L₀, L₁, ..., L_i-1 и которые вычислимы произвольной функцией (ями) j_z, выполнимой в состоянии S_i = L₀ÈL₁È...ÈL_i-1, т.е.

S_i ^|¾ j_z. (3.11)

Так, из рис. 3.6, в устанавливаем непосредственно, что

L₀ = {x₁, x₃, x₅},

L₁ = {x₆},

L₂ = {x₇, x₉}.

Теперь в каждом уровне, исключая L, каждую вершину заменяем на ту процедуру, с помощью которой она вычислялась. Это дает следующий результат

Окончательно интересующая нас цепочка С строится так, чтобы любая функция j_t, принадлежащая уроню L_m,стояла левее любой функции j_q, принадлежащей L_n, если m < n; если m = n, то взаимный порядок расположения функций j_t и j_q в С роли не играет. Из этого правила, устанавливаем, например, что

C = <j₃, j₇, j₈>

суть интересующая нас цепочка.

Завершим этот параграф рассмотрением моделей знаний с алго­ритмом вывода, управляемым по данным. Поскольку структура управ­ления выводом в таких моделях явно не представлена, то нужны неко­торые специальные механизмы: механизм недетерминированного выбо­ра альтернативы (альтернативной продукции), механизм возврата (бэктрекинга) и механизм унификации. Последние два механизма рас­смотрены в разделе 1.4 при описании основных понятий языка Пролог.

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