автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Основы построения графического интерфейса для задач структурного моделирования

РГ6 ОД

2 9 ИЛЙ ^95

На правах рукописи

Тархов Андрей Альбертович

ОСНОВЫ ПОСТРОЕНИЯ ГРАФИЧЕСКОГО ИНТЕРФЕЙСА ДЛЯ ЗАДАЧ СТРУКТУРНОГО МОДЕЛИРОВАНИЯ

Специальность: 05.13.12 - системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

С. - Петербург - 1995

Работа выполнена в Институте проблем машиноведения Российской академии наук

Научный руководитель - доктор технических наук,

профессор Е.Д.Соложенцев

Официальные оппоненты - доктор технических наук,

профессор Л.Н.Розанов

кандидат технических наук, с.н.с. А.В.Поваженко

Ведущая организация - Санкт-Петербургский институт информатики

и автоматизации Российской Академии Наук

Защита диссертации состоится "20" июня 1995г. в 16 час.Д^мин. на заседании диссертационного совета К 063.38.28 в Сан Петербургском Государственном техническом университете по адре 195251, Санкт-Петербург, Политехническая ул., дом 29, ауд. 439 1 учебного корпуса.

С диссертацией можно ознакомится в библиотеке СПбГТУ Автореферат разослан 49" МЯЛ. 1995г. Ученый секретарь

диссертационного Совета К 063.38.28 кандидат технических наук,

доцент

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Работа выполнена в соответствии с планами фундаментальных исследований Российской академии наук по темам "Проблемы

управления и автоматизации" и "Повышение надежности систем челозек-машина-среда".

Цель работы. Повысить эффективность средств организация интерфейса при автоматизации структурного моделирования на основе разработки математического, программного, методического обеспечения и интеллектуализации его графической: части.

Основные задачи работы.

1. Проанализировать методы кодирования графов и установить их связь с временной сложностью базовых операций.

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

3. Исследовать характеристики граф-моделей на примерах подсистем газотурбинных двигателей, как объектов диагностирования и схем функциональной целостности на примерах подсистем корабельной атомной электроэнергетической установки. Разработать и исследовать методы анализа структуры, связанные с декомпозицией и укрупненным представлением графов, эффективные дла подобных моделей.

4. Разработать структурную схему комбинированного интерфейса с учетом интеллектуализации его графической части, соответствующие библиотеки подпрограмм н подсистемы, обеспечивающие реализацию его основных функций.

Научная новизна работы.

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

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

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

позволяющие упростить и облегчить взаимодействие пользователя с системой при работе с моделями данного класса,

4. Предложена методика построения к структура комбинированного интерфейса, что обеспечило возможность разработки интеллектуализированных программных средств.

Практическая значимость.

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

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

3. Выполнен анализ граф-моделей объектов диагностирования и схем функциональной целостности корабельной атомной энергетической установки на основании которого выявлены их наиболее значимые элементы и определен эффективный набор процедур размещения.

На защиту выносятся:

обобщенная функциональная схема комбинированного интерфейса;

- зависимость эффективности базовых операций от метода кодЕфования графов;

- семейство итеративных алгоритмов размещения графов и оценки их эффективности;

- результаты вычислительного эксперимента по исследованию программной реализации семейства итеративных алгоритмов для случайных графов и случайных деревьев;

- приближенные алгоритмы оптимального размещения деревьев и двудольных графов;

- результаты исследования характеристик граф-моделей подсистем газотурбинных двигателей, как объектов диагностирования и схем функциональной целостности судовой атомной электроэнергетической установки;

особенности декомпозиционных алгоритмов и методы укрупненного представления моделей;

- б -

- эффективный приближенный алгоритм определения максимального цикла в графе и алгоритм размещения на его основе.

Внедрение результатов работы. Материалы диссертационной работы переданы и используются в НИЛИТ ВВМИУ им. Дзержинского при разработке автоматизированной системы анализа вероятности безопасности атомных энергетических установок, ЛНЫТТиМ ТюмГНГУ для автоматизированного проектирования систем утилизации тепла и ВНИИтрансмаш для автоматизации диагностирования на граф-моделях.

Апробация работы. Результаты работы докладывались на всесоюзной конференции "Конструкторско-технологнческая

информатика, автоматизированное создание машин и технологий" (Москва, 1989 г.), всесоюзной конференции с международным участием "Повышение эффективности землеройных машин" (Воронеж, 1994 г.), семинаре BMA им. Кузнецова "Системный анализ при исследовательском проектировании кораблей ВМФ, комплексов вооружения и военной техники" (С.-Петербург, 1995 г.).

Публикации. Основные результаты диссертации опубликованы в б печатных работах.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы яз 126 наименований и приложения. Общий объем работы - 282 страницы, из них 134 страницы машинописного текста, 33 таблицы и 44 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

Во ВВЕДЕНИИ обосновывается актуальность работы, сформулирована цель, научная новизна и практическая значимость диссертации, приведены основные положения, выносимые на защиту.

В ПЕРВОЙ ГЛАВЕ рассматриваются общесистемные вопросы автоматизации моделирования, анализируются особенности структурного моделирования, приводятся примеры реализации конкретных систем. Отмечена важность графического представления модели, роль пользовательского интерфейса и недостатки традиционной схемы автоматизированного структурного моделирования. Рассмотрены проблемы, связанные с проектированием интерфейса. Сформулированы алгоритмически сложные задачи, возникающие при решении задачи проектирования интерфейса для задач структурного моделирования.

Выполнен анализ методологии моделирования объектов диагностирования на графах, научные основы которой разрабатываются

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

На основании анализа работ Можаева A.C., Рябинина И.А. и др. сформулированы основные проблемы, возникающие при автоматизации структурного моделирования, которое является концептуальной основой научной школы логико-вероятностных методов (ЛВМ) исследования надежности, живучести и безопасности сложных систем.

Рассмотрены вопросы, связанные с применением структурного моделирования в экспертных системах. Показана возможность использования графических средств при решении таких традиционно трудных задач, как формирование базы знаний, повышение объяснительных возможностей системы, принятие решений о полноте и непротиворечивости знаний, осуществление отбора знаний от пользователя-профессионала, на необходимость решения которых указано в работах Виттиха В.А., Поспелова Г,С., Соложенцева Е.Д. и др.

На основании приведенного анализа сформулирована цель и основные задачи работы.

Во ВТОРОЙ ГЛАВЕ рассмотрены вопросы, связанные с преобразованием информации при реализации интерфейсного цикла для структурных моделей (графов и основанных на графах структур).

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

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

Осуществлена формальная постановка задачи размещения (визуализации) графа, как задачи многокритериальной оптимизации с ограничениями, с учетом следующих допущений:

1. Решаем задачу геометрического представления графа на плоскости, как наиболее простого и наглядного.

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

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

Для качественной оценки временной сложности решена оптимизационной задачи размещения доказана теорема о NP-полнот следующей однокритериальной задачи: Пусть задан граф G(Y,E), гд< V={v,, v„..., v„} - множество вершин графа, EcrVxV - множество ребе] и KcZxZ - множество точек плоскости с целочисленным! координатами. Найти такое инъсктивнос отображение f:V-»K, чтобы;

I г<£ЫЛ^)Нт1п , " (2)

(v„vj)eE

где r(f(Vi),f(Vj)) - вещественная функция на множестве точек плоскости

удовлетворяющая аксиомам расстояния.

Очевидна взаимосвязь между критерием (1) (обозначим его КО) i

наглядностью представления модели. Кроме него, для максимнзацш

"наглядности", в зависимости от конкретных характеристик графа

дополнительно могут вводиться следующие критерии: 2 r(f(v-x), р0) —>mii

v,eV

- Kl, где p0 произвольная точка плоскости, которая в частном с луч а; может совпадать с образом одной из вершин графа f(v0) Sr(f(vi)>Po)->Eisx - К2; КЗ - у-»min , где у - количество пересечений.

v,eV

С учетом допущения 3, необходимо ввести следующее ограничение: У(\'ь\',)еЕ с декартовыми координатами образов концевьи вершин (xi,yj и (Xj,yj) и Vvk с декартовыми координатами се образ: (xk,yt) если xi<xk<xj и у^ук<у< , то:

(*„ - - Yi) - (х, - ОСу* - Уд * 0 (2)

Чтобы подтвердить существование такого решения доказан«

теорема: Пусть D> ^^—- + 2, п= IV | - число зершия графа, S -

целочисленный квадрат со стороной D, Тогда найдется янъектнвное отображение f:V->S, удовлетворяющее условию (2).

На основании этих результатов доказаны следующие положения:

1. Если граф G размещен в целочисленном прямоугольнике со сторонами D1 и D2, то дополнительную вершину v* произвольным образом связанную с вершинами исходного графа, всегда можно разместить внутри этого прямоугольника с соблюдением условия (2), если D1+D2-2 > ai (где m - количество ребер графа).

2. Задача "Найти отображение f удовлетворяющее условию (2)" принадлежит классу полиномиально-разрешимых задач Р.

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

А(М, К, G) (3)

где: M - метод поиска решения; К - критерии оптимизациЕГ, G -граничные условия.

Разработаны алгоритмы для трех методов М={М1, М2, МЗ} в которых последовательность перебора обеспечивает решение, удовлетворительное по КО. С учетом ряда допущений показан полиномиальный характер оценок временной сложности алгоритмов в '"среднем". Они получены для каждой из имеющих смысл комбинаций M и К.

Семейство итеративных алгоритмов реализовано на языке С (ставдарт AN-SY) в среде программирования TURBO С 2.0 на ЭВМ АТ-386 (SX/40) с показателем быстродействия CPU по NORTON UTILITYS 17, который может служить коэффициентом пропорциональности при оценке времени выполнения соответствующих процедур на ЭВМ этой-же архитектурной линии. Для подтверждения полиномиальной временной сложности проведена серия статистических испытаний для каждого реализованного алгоритма, Для диапазона вершин графа от 20 до 40 с шагом 5 генерировался случайный граф (рис.!,?.). Для каждого значения количества вершин проводились серии из 10 опытов. Испытания проводились без учета граничных условий, поэтому обозначения приводятся з форме А(М,К).

Зависимость Т(п) (время Еыпонешгз) аппроксимировалась степенной функцией ахпь. Для оценки параметров а и b проведена обработка результатов статистических испытаний с помощью процедур

регрессионного анализа, которые показывают, что прЕшятая модель очень хорошо соответствует результатам эксперимента, коэффициент детерминации достаточно высок. (86...99 %), а коэффициент корреляции близок к единице (0.97.,.0.99),

» @

<5.

\

& €> ^ /

0 У 6

Рис. 1. Результат реализации итеративных алгоритмов для случайного графа с 20 вершинами и случайного дерева с 50 вершинами: а)А(М1,К1); 5)А(К2+К3) Показатель степени в худшем случае близок к степени старшего члена полинома в аналитической оценке временной сложности алгоритма (Ь=1.4...4.3 для К1 и К2 (рис. 2,а), Ь=3.7...4.9 для К1+КЗ и К2+КЗ при коэффициенте 11=1, задающем зону поиска оптимального решения по КЗ (рис. 2,6)).

Л(МШ5

А1М1.К2), А1МЗ.К1), А!М2,КЗ), А(М;,К1)

А(МЗ,К2)

Г 35

а)

150"

/ /

20 25 б)

"I 40

Рис. 2. Зависимость времени размещения графа от количества вершин; а - для различных М без КЗ; б - для различных М с КЗ Большое количество реальных структурных моделей, взаимодействие с которыми можно свести к графам, имеют сравнительно

небольшие цикломатическис числа. Поэтому работа итеративных алгоритмов с такими структурами по своим характеристикам больше похожа на работу с деревьями длз которых, учитывая их пяанарность, особенно важно произвести минимизацию по КЗ. Для деревьев М1, М2 и МЗ совпадают, поэтому обозначения сделаны в форме А(К), Для алгоритмов серии А(КЗ+К2) при количестве еершин порядка 50 это удается сделать, как правило, для 1^=1 (рис. 1,6). Для группы алгоритмов А(КЗ+К1) при достаточно большом количестве вершин полностью планарная укладка обычно невозможна (даже при увеличении К), но они дают более компактное представление, что можно использовать в условиях жестких ограничений на площадь размещения и масштаб.

Исследованы временные характеристики работы реализованных процедур для случайных деревьев (рис. 3). Методика проведения статистических испытаний аналошчаа численному эксперименту для случайного графа. Однако больше серий проведено для оценки поведения алгоритмов при изменении К (от 0 до Результаты

регрессионного анализа подтверждают полиномиальный характер алгоритмов с более низкими значениями коэффициента Ь (1.7...2.8).

1111! 40 45 50 55 30

Рис. 3. Зависимость времени размещения дерева от количества вершин для-семейства итеративных алгоритмов о К1, К2 я КЗ.

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

- 12 -

цикла (рис. 4). Доказано следующее положение: Дда неориентированного графа, остоз которого получен на основе поиска в "ширину", все хорды соединяют вершины одного и того-же или соседних ярусов.

Для двудольных графов традиционное представление удобно использовать при небольшом количестве вершин. Под традиционным представлением понимается граф, у которого подмножества вершин \71 и У2 лежат на параллельных прямых 1, и соответственно (У{у1,у2}еЕ, ^еУц к у^еУ-»). В этом случае для повышения наглядности необходимо решить оптимизационную задачу с критериями КО и КЗ. Упрощенно эти два критерия можно свести к

т

критерию —>зшх1 - К4, где т - количество ребер графа О, с* -

проекция 1-го ребра на 1,.

Предложен приближенный алгоритм решения задачи размещения двудольного графа, основанный на таком разбиении множества V на непересекающиеся подмножества V,, У2,..., Уи, что ^¡=|У1|+|У2|+...+|Ук| и V, - входит в максимальную цепь графа 0(У,£), У2 - входит в максимальную цепь подграфа С, порожденного множеством вершин У*=У\У1,..., граф порожденный множеством Ук=У*\Ук.; - связный граф, содержащий гамильтонову цепь.

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

1. Для двудольного графа, остов которого получен на основе поиска в "ширину", нет ни одной хорды, соединяющей вершины одного а того же яруса.

2. Для неориентированного двудольного графа, остов которого получен на оснозе поиска в "ширину", хорды соединяют только вершины соседних ярусов.

3. Если ос-товное дерево поиска в "ширину" для неориентированного двудольного графа размещено в "традиционном" стиле, то для него всегда выполняется условие (2).

В ТРЕТЬЕЙ ГЛАВЕ выполнены исследования характеристик структурных моделей реальных технических систем, на основании

? "

Ю'чеа ^ здзнеяых гаыюв

СЭДЭЙОА»,© X X

Х--®

- - -11»

0 V

Рис. 4.

да «14

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

Установлены следующие характеристики граф-моделей подсистем газотурбинных двигателей (ГТД), как объектов диагностирования: максимальное количество вершин п—13 5 н дуг т=200, диапазон цикломатических чисел 5...66, большое количество висячих вершин и вершин с малыми степенями (максимальная степень вершины 16). Приведенные данные зажны как для решения задачи выделения доминирующего множества, так и задач, связанных с поддержкой качественного графического интерфейса,

Рассмотрены схемы функциональной целостности для оценки безопасности подсистем корабельной атомной электроэнергетической установки. Приведен анализ их "графовых" характеристик, аналогичный вышеизложенному для граф-моделей, в результате которого установлены следующие существенные показатели: максимальное количество вершин -79 и дуг - 117; диапазон цижломатических чисел - 5...39; максимальная степень вершины - 7. Показано очевидное сходство с граф-моделями объектов диагностирования, как. по диапазонам характеристик, так и по единству задач при организации взаимодействия с моделями.

На основании провсдсЕгаого анализа показана необходимость учета связности графа. Известны полиномиальные алгоритмы анализа графа на связность: на основе поиска в "глубину1, поиска в "ширину", матричных методов. Рассмотрены преимущества поиска в "ширину" с точки зрения удобства решения задачи размещения и выполнен анализ зависимости его временной сложности от применяемых базовых операций и метода кодирования.

Для ряда моделей установлено, что они имеют блоковую структуру (например, граф модели гидросистемы управления реверсивным устройством и системы смазки имеют по 3 блока отличных от тривиального). Доказаны теоретические положения, позволяющие построить алгоритм выявления блоковой структуры и точек сочленения на основе анализа базиса циклов, полученного в результате поиска з "глубину" или в "ширину", что является обобщением теоретических основ алгоритма Хопкрофта и Тарьяна:

1, Любой блок связного графа Сг=:(У,Е) является либо объединением некоторого подмножества базисных циклов, либо тривиальным блоком,

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

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

Выявление бикомпонент можно проводить по известному алгоритму преобразование матрицы 11'=11®Е.Г в блочно-диагональную (И -матрица достижимостей). Сформулированы положения, позволяющие снизить размерность матрицы и упростить ее анализ.

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

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

Для моделей, имеющих блоки большой размерности, следует проводить разрыв некоторых связей, или приводить граф к мишшально-гомеоморфному виду без учета и с учетом ориентации, при котором с целью исключения появления мультиграфов введены следующие ограничения на слияние ребер (дуг): для ребер ху и хг х^г., которые подлежат слиянию, не существует ребра уг. Показана возможность повышения "наглядности" представлением минимально гомеоморфного графа. Доказана некоммутативность комбинации операций { и где £ -отсечение леса, а & - сведение & к минимально гомеоморфному виду при этом: fg=gfg.

В пределах блока могут использоваться различные способы разбиения множества вершин на подмножества, при котором

представление подграфа, порожденного одним из подмножеств имеет гсомстрпчгсьуЕо интерпретацию. Рассмотрен: случай приближенного решения задачи о максимальном цикле графа (данная задача является НР-полной), который графически может быть представлен выпуклым многоугольником (рис. 5). Сформулированы принципы для снижения размерности входа данной задачи. Алгоритм работает по методу последовательного уточнения решения, что существенно при жестких системных ограничениях на время выполнения и -УР-полноте задачи. Оценка качества решения может производиться по графическому образу.

(jp—©—-& fXit^

©-V-а.

\

© ß ё w

a)

В

4

Oi

Рис. 5. Размещение граф-модели подсистемы сдува вихря ГТД PS-90: а - по А(М1, К1): б - на основе вычисления максимального цикла

В ЧЕТВЕРТОЙ ГЛАВЕ рассмотрена методология проектирования комбинированного интерфейса с интеллектуализацией его графической части и реализация соответствующего программного обеспечения.

На основе изложенных теоретических положений и алгоритмов с учетом особенностей структурного моделирования, многообразия задач и возможности распространения

адач,

связанных

реализацией

интерфейса для графов на более широкий диапазон структурных моделей, разработаны следующие программные продукты:

1. Библиотека функций анализа структуры (для графов).

2. Библиотека функций размещения графов - получения координат вершЕгн на основе символьной (числовой или аналитической) формы представлена.

3. Библиотека функций графического вывода.

4. Специализированный графический редактор (для автоматизации процесса непосредственного ввода графической формы).

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

При реализации полноценного комбинированного интерфейса необходимы следующие модули, обеспечивающие ввод и вывод алфавитно-цифровой информации:

1. Интерпретатор входного языка.

2. Подсистема вывода алфавитно-цифровой информации.

Функциональная схема комбинированного интерфейса для задач

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

Рис. 6 Обобщенная функциональная схема комбинированного интерфейса для задач структурного моделирования

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

модуль анализа структуры - модуль графического вывода, который может замыкаться через элемент интерфейсного цикла - человека.

Модули анализа структуры и. размещения реализованы ita основе двух структурно обособленных, но функционально взаимосвязанных программных продуктов: библиотеки функций анализа структз'ры и библиотеки функций размещения (TURBO С). Библиотечный принцип организации позволяет использовать предлагаемый набор функций в интегрированных автоматизированных системах различного назначения с широким спектром аппаратного и программного обеспечения. Программы разработаны в процедурно-ориентированном стиле на языке "С" (стандарт ANSY), что ввиду устоявшихся стандартов и наличию диалектов "С на машинах различных архитектурных линий упрощает переносимость данного программного обеспечения. Хорошая структурированность языка "С" и его распространенность облегчает возможную модификацию и реализацию данных алгоритмов в других стилях программирования: объектно-ориентированном, функциональном, продукционном. Организаций межмодульного обмена производится через систему файлов текстового формата.

Разработаны два варианта специализированного графического редактора (ОТ) - встроенный (ВССГР) и внешний (ВНСГР). ВССГР реализован: на языке "С" и предоставляет возможность автоматизированного построения структурных моделей а пределах экрана дисплея. Управление функциями: ВССГР производится через систему падающих меню п комбинации ''горячих" клавиш, ВССГР минимизирован по объему занимаемой памяти н позволяет работать с небольшими моделями (десятки узлов) и ограниченным набором следующих функций: выбор типа узлов, идентификация узлов, построение узлов, ввод связей, ввод цепей, удаление отдельных узлов, удаление связей, очистка экрана и перерисовка модели.

ВНСГР реализован па базе AUTO CAD зеренн Î0 и предоставляет следующие возможности: выполнение всех функций ВССГР, ввод и редактирование атрибутов узлов и связей, идентификация узлов, идентификация связей с возможностью взода и редактирования атрибутов, перенос узла (с сохранением связей), функция переноса части модели, масштабирование прямоугольной части модели.

Разработана система автоматизированного построения и анализа структурных моделей, которая обеспечивает выполнение следующих функций: автоматизированное графическое построение изображения (схемы) структурной модели; автоматическое построение структурной

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

С использозанием указанного программного обеспечения проведены следующие работы:

- по матричному описанию 10 граф-моделей подсистем ГГД и 7 моделей атолшой энергетической установки получены различные варианты графического представления;

- исследована размерность этих моделей, диапазоны циклома-тических чисел, векторы степеней;

- выявлена блоковая структура и точки сочленения, которые для систем диагностирования являются предпочтительными при выборе контролируемых параметров, а для моделей безопасности показывают '"слабые" места системы;

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Разработано семейство итеративных алгоритмов размещения графов с учетом различных критериев оптимизации. Проведено исследование соответствующих программ на случайном графе и случайном дереве и показан их полиномиальны?! характер Достоинством алгоритмов является пошаговая работа, что важно прк реализации комбинированного интерфейса, разработке интерфейса дл* систем с динамической структурой и т.д.

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

целесообразно применять при возможности установить принадлежность структуры к. данному классу.

5. Исследованы характеристики граф-моделей подсистем газотурбинных двигателей (максимальны; показатели п=!35 и т=200, небольшие цикломагические числа и большое количество зерпшн с с!е^<2). что доказывает возможность применения разработанного аппарата для данных и подобных систем. Выявлена их блоковая структура и точки сочленения.

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

7. Обобщены теоретические основы алгоритма Хопкрофта и Тарьяна, позволяющие разработать алгоритм для выявления блоковой структуры и точек, сочленения на основе анализа базиса циклов. Рассмотрены различные методы декомпозиции и укрупненного представления графоз, позволяющие перейти к работе с иод елями значительно меньшей размерности.

8. Предложен полиномиальный алгоритм приближенного решения задачи поиска максимального простого цикла в графе. Разработан соответствующий алгоритм размещения, позволяющий в ряде случаев существенно повысить "наглядность'1 представления.

9. Разработаны методика построения комбинированного интерфейса с интеллектуализацией графической части и его обобщенная функциональная схема. Установлен приоритет а последовательности реализации его подсистем и роль модулей акали.-:?, структуры, размещения а вывода графической информации.

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

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

1. Губинстшй М.В., Михалочкин В.В., Тархов A.A. Автоматизированная система грз'ппнрованяя. //Информационный листок..

П.: Межотраслевой территориальный центр научно-технической информации и пропаганды, 1985, 3 с.

2. Королев В.А., Романов П.И., Тархов A.A. Система автоматизированного проектирования сбалансированных манипуляторов.// Материалы всесоюзной конференция "Конструкторско-тех дологическая информатика, автоматизированное создание машин и технологий". - М,1989, с. 187-191.

3. Донской А..С., Королев В.А, Мнацакашш М.А, Романов П.И.. Тархов A.A. САПР пневматических сбалансированных манипуляторов для механизации технологических процессов и производств. Учебное пособие. - Ленинград: изд. ЛГТУ, 1990, 79 с.

4. Добрынин В.Ю., Мясянкова Г.И., Тархов A.A. Исследование задачи визуализации граф-мод ела. //В препринте N104, "Теория к информационная технология моделирования безопасности сложных систем", вып. 2 - С-Пстербург : ИПМАШ РАН, 1994, с, 43-63.

5. Карнаухов H.H., Тархов A.A. Анализ и синтез граф-моделей систем утилизация тепла строительных машин. //Тез. доклада на зторой всесоюзной конференции с международным участием "Повышение эффективности землеройных машин" - Воронеж, 1994, с. 91.

6. Тгрхоз A.A. Система автоматизированного графического построения к анализа структурных моделей (САГПА СМ). //В препринте N109, "Теория и информационная технология моделирования безопасности сложных систем", вып. 3. - С-Петсрбург : ИПМАШ РАН, 1994, с. 22-47.