Предлагается способ представления графовой модели предметной области на основе расширения языка разметки направ-ленных графов Directed Graph Markup Language.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
\r\f
В [2] показано, что соответствующая модель предметной области может быть представлена
древовидным ациклическим графом, вершиной которого является задача
, узлы определяют иерархию
подзадач, дуги – уро
вень их вложенности.
– древовидный иерархический граф, представленный множеством вершин
и множе
ством ребер
. Граф
будем называть динамическим, если за промежуток времени
возможен переход
графа из состояния
в состояние
причем множества
, соответственно,
не совпадают. Модификацией графа
назовем процесс перехода графа из состояния
в момент времени
в состояние
на момент времени
который может быть вызван выполнением некоторой последователь
ности операций на графе (добавление вершины, удаление вершины, разбиение графа, слияние графа). В
соответствии с (1) каждой вершине графа предоставим следующий набор атрибутов:
=
где
– уникальный идентификатор вершины (задачи); task – п
остановка задачи (требования к решению);
status – состояние вершины (0 – задача инициирована, но не решена; 1 – задача в процессе решения, 2 –
задача решена); name – уникальный идентификатор эксперта; addr – адрес эксперта; inf – информационная
составляющая (фактически решение задачи, представленное в одном из допустимых форматов).
Требуется разработать способ представления графовой модели динамической предметной области за
дачи (1), позволяющий описать модель в виде формальной спецификации, допускающей машинное пред
ставление графа, его автоматизированную обработку и облегченный механизм синтаксического анализа.
Классическим способом описания графовых моделей является использование матриц инцидентности
и матриц смежности. Однако в контексте рассматриваемой задачи проблема представления графа услож
няется тем, что вместе со структурой графа необходимо хранить описание отдельной задачи и набор атри
бутов, связанных с каждой вершиной. Иными словами, вершины графа неоднородны. Для представления
неоднородных графов в теории систем искусственного интеллекта разработан язык семантических сетей
[3]. Однако для описания иерархически декомпозированных задач такой язык является избыточным, так как
задачи связаны однородным отношением зависимости по данным. Кроме того, процедуры вывода по иерар
хически декомпозированному графу значительно проще процедур вывода по семантической сети. В связи
с этим предлагается рассмотреть существующие стандарты описания графовых моделей, возможности рас
ширения их собственного синтаксиса или возможности переопределения существующих синтаксических
конструкций.
€†‡”‡ ŒŽ€”’€ˆ ‹‰†•
Для описания графов и теоретико-графовых моделей в настоящее время существует несколько обще
признанных стандартов, основанных на технологии XML. Одним из предшественников таких форматов
является язык GML (Graph Modelling Language). GML до сих пор поддерживается многими прикладными
программами и библиотеками для работы с графами. Позднее появились стандарты GraphXML, GraphML,
XGMML (eXtensible Graph Markup and Modeling Language), GXL (Graph eXchange Language) и другие. Рас
смотрим некоторые из них.
DOT language – язык описания графов в виде простого текста. Набор атрибутов, применимых к объ
ектам графа, предельно лаконичен, реализация программного интерфейса для работы с ним не представляет
особого труда. Однако DOT не предоставляет возможности описывать и добавлять собственные параметры
к ребрам и вершинам графа.
GDL (Graph Description Language) – мощный, простой в обращении язык описания графов. Создавать
графы в формате GDL можно с помощью любого текстового редактора, поддерживающего сохранение фай
лов в формате обычного текста.
GraphML (Graph Modeling Language) – полнофункциональный файловый формат для описания графов.
Он включает базовый язык, предназначенный для описания структурных свойств графа, поддержку направ
ленных, ненаправленных, и смешанных графов, гиперграфов, иерархических графов, описание графическо
го представления, ссылок к внешним данным. GraphML использует синтаксис, основанный на языке XML,
и, следовательно, идеально подходит в качестве универсального средства для представления, хранения и
обработки графов.
Однако все представленные средства
формального описания графовых моделей обладают одним суще
ственным недостатком. Они не предоставляют гибкого механизма расширения языка собственными свой
ствами и механизма добавления данных к структурным элементам графа, что не позволяет использовать их
для решения задачи представления модели динамической предметной области в виде атрибутированного
иерархического графа.
Этого недостатка лишен формат
(Directed Graph Murkup Language) – язык разметки направ
ленных графов, который использует про
стой XML для описания направленного графа.
Направленный граф
представляет собой набор
узлов, соединенных ссылками или границами.
Узлы и ссылки могут быть исполь
зованы для представления сетевых структур, элементов программного проекта.
Можно использовать DGML
для визуализации информации, выполнения анализа сложности или просто для просмотра и редактирования
графа. В контексте решаемой задачи существенным является тот факт, что DGML может быть расширен
за счет включения структурированных элементов, отвечающих специфике предметной области и за счет
добавления дополнительных атрибутов ко всем элементам DGML.
€Ž„Ÿ¦ª®†”ŒŽ€”€‰—Ž•
Œ‰­•‘†€Ž­
Предлагается использовать базовые элементы DGML, расширив их за счет добавления необходимых
дополнительных атрибутов. Основные элементы языка DGML следующие:

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

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



...


...


...

Расширим представленный формат за счет определения дополнительных элементов, которые позволят
описать графовую модель в соответствии с моделью ССЗ (1) и учитывая набор атрибутов (2).
Определим элемент
как единичный узел графа, соответствующий подзадаче, элемент
– как единичную ссылку, соединяющую исходный узел с целевым узлом и задающую ребро графа.
Тогда элемент
должен содержать набор обязательных атрибутов, позволяющих описать подзадачу,
а элемент
– набор обязательных атрибутов, определяющих иерархию подзадач. Реализуем это за
счет возможности добавления дополнительных атрибутов к элементам DGML. Для этого определим список
элементов :




В результате множество вершин графа (задач) описывается в следующем формате:




Для определения иерархии подзадач элемент должен содержать по крайней мере два обяза
тельных атрибута: Source – уникальный идентификатор начальной вершины ребра, Target – уникальный
идентификатор конечной вершины. Тогда множество ребер графа может быть представлено следующим
образом:
\r\f
Source=”…” Target=”…”/>


В результате введения дополнительных элементов и соответствующих атрибутов графовая модель
предметной области представляется DGML-документом следующего формата:














На основе анализа общепринятых стандартов описания графов и теоретико-графовых моделей, ба
зирующихся на технологии XML, рассмотрена возможность создания языка представления динамической
предметной области за счет расширения языка разметки направленных графов DGML. Представленное
решение реализовано за счет включения дополнительных структурированных элементов языка и их атри
бутов, отвечающих специфике предметной области ССЗ. Предложен формат представления графовой мо
дели, позволяющий описать модель предметной области задачи (1) в виде формальной спецификации, до
пускающей машинное представление графа, его автоматизированную обработку и облегченный механизм
синтаксического анализа.
Вальвачев, А. Н
. Технология выполнения IT-проектов коллективами распределенных исполнителей
/ А.
Вальвачев, Х.
Виссия, В.В.
Краснопрошин // Искусственный интеллект. 2008. №
3. С. 63–69.
Карканица, А. В.
Онтологический подход к построению моделей динамических предметных обла
стей // Вестник Гродненского государственного университета имени Янки Купалы. Серия 2. 2010. № 1(92)
С. 92–97.
Краснопрошин, В. В.
Алгоритмы модификации деревьев для построения динамических предметных
областей / А. В.
Карканица // Искусственный интеллект. 2010. №
4. С. 388–394.
Краснопрошин Виктор Владимирович, заведующий кафедрой информационных систем управления Бе
лорусского государственного университета, профессор, доктор технических наук, [email protected]
Карканица Анна Викторовна, старший преподаватель кафедры программного обеспечения интел
лектуальных и компьютерных систем Гродненского государственного университета имени Янки Купалы,

Приложенные файлы

  • pdf 7867644
    Размер файла: 810 kB Загрузок: 1

Добавить комментарий