wali.su
 
Набережные Челны
Тел.: +7 8552 397129

Структуры данных

 
 

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

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

Для установления такой ассоциативной связи пользуются самыми разнообразными методами. В системе «МикроЭксперт» запоминание большинства элементов данных, без которых невозможно функционирование дедуктивной машины, осуществляется с помощью связанных списков записей, называемых структурными компонентами. И хотя при этом память расходуется недостаточно экономно, структура программы в целом упрощается. На распечатке 1 такого рода компонент представлен в виде кода на языке Паскаль.

Существуют два основных вида структурных компонентов. Компонент правила содержит признак, значение, номер правила и тип самого компонента (условие или вывод правила). Поскольку в описании правила можно использовать предикат только одного вида — «ЯВЛЯЕТСЯ» (или тире), — предикат не включается в структурный компонент. Для каждого выражения, входящего в правило, формируется свой компонент, причем в составе правила такие компоненты соединяются между собой указателями. И наконец, в эту упорядоченную структуру вводится еще один указатель, идущий от некоторого общего массива и отмечающий первый компонент правила (рис. 2). Таким образом, любое правило заносится в память в виде двух связанных списков, один из которых относится к условию правила, а другой — к выводу.

Рис. 2. Представление правила 8 в виде связанных списков.

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

Рис. 3. Связи между списком признаков и списками подсказак и переводов, проиллюстрированные на примере признака ПОЛОЖЕНИЕ.

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

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

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

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

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

В описании картотечно-поисковой дедуктивной машины мы оперировали с колодой сброса, куда помещались «отработанные» правила. В рассматриваемой программе для реализации той же функции удобно воспользоваться массивом булевых переменных. Первоначально каждому элементу такого массива приписывается значение ИСТИНА. По мере того как правила перестают быть «действующими» (т. е. когда в зависимости от контекста определяется, истинны они или ложны), для соответствующего элемента массива правил устанавливается значение ЛОЖЬ.

 
 

 
 
Copyright © 2008 Валеев Ильшат
Тел.:(8552) 397129
Создание и продвижение сайтов