Представление и/или деревьев в системе поддержки принятия решений при подготовке производства спортивной одежды

Размещено на http://www.allbest.ru/

ФГОУ ВПО «Госуниверситет - УНПК»

Представление и/или деревьев в системе поддержки принятия решений при подготовке производства спортивной одежды

Глянцев Валерий Константинович

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

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

Одним из способов реализации системы принятия решений является использование И/ИЛИ деревьев. И/ИЛИ дерево может являться механизмом обработки информации о структуре объекта, а также способом организации данных в базе знаний.

Элементы описанные узлами И/ИЛИ дерева представляют собой факты, при условии наличия дополнительных свойств элементов, их взаимодействия с внешней средой, как указано в правилах при формировании новых моделей[2].

Структура И\ИЛИ деревьев не является типовой для хранения данных и поэтому способ ее хранения нуждается в дополнительном описании. Учитывая необходимость хранения больших объемов данных о моделях (в нашем случае внешний вид отдельных элементов) необходимо разработать как структуры для хранения дерева в оперативной памяти, так и общую структуру базы данных.

Для представления деревьев используется 2 подхода: представление в смежной и динамической памяти.

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

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

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

Общими недостатками смежной памяти является:

- ограниченность памяти;

-- статичность, неизменность структуры.

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

-- позволяет работать с большими объемами данных;

- размер занимаемой памяти всегда соответствует объему хранимой информации;

- имеет большую гибкость структуры.

Структура представлена на рисунке 1.

Рисунок 1 - Универсальная структура представления n-арного дерева

Представление И/ИЛИ дерева мало отличается от обычного n-арного дерева. Вся разница заключается в том, что необходимо хранить информацию о типе связи.

И/ИЛИ дерево G можно описать тройкой , где:

1) множество вершин , где

- множество вершин i-го уровня дерева G, n - число уровней дерева G;

2) - множество ребер дерева G;

3) - множество двухуровневых «И» поддеревьев дерева G.[3]

Наиболее естественным для хранения дерева, будет форма представление узлов с раздельными ссылками на И и ИЛИ, рисунок 2.

Рисунок 2 - Структура хранения И/ИЛИ дерева

Для хранения связей между узлами необходимо разграничивать И/ИЛИ ребра, что приводит к избыточности и неоднородности структуры, поэтому И/ИЛИ дерево необходимо свести к виду, когда каждая его вершина имеют только И или только ИЛИ ребра. Для этого для множества И ребер вводим дополнительные вершины, так что у каждого узла есть ребра только одного типа (И-ребра или ИЛИ-ребра)[4].

Тогда структуру дерева, основанную не на типе ребер, а на типе узлов (узел имеет только И или только ИЛИ ребра), можно представить в виде показанном на рисунке 3.

Если в этой структуре можно отобразить И/ИЛИ-дерево вариантов моделей спортивной одежды, то оно примет вид приведенный на рисунке 4.

Необходимость работы с графикой при проектировании ставит вопрос об использовании базы данных как инструментального средства хранения (рисунок 5).

Рисунок 3- Структура хранения И/ИЛИ-дерева

Рисунок 4- Пример представления И/ИЛИ-дерева в динамической памяти

Рисунок 5 - Концептуальная схема структуры хранения дерева И/ИЛИ

Наиболее удобно использовать хранение данных о моделях в виде И-деревьев. Для этого необходимо представить модель в виде иерархической структуры, которую удобно хранить в таблице с рекурсивной связью. Для этого в концептуальной схеме разработана структура (блок 1). На основе таблицы «Элемент модели» строится И-дерево с изменением направление связи вершин: хранится ссылка на родителя, а не на потомка.

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

Графическое представление элементов хранится в базе данных и переносится в приложение только при отображении конечного варианта. Графическое представление может включать в себя чертежи, эскизы, 2-х и 3-х мерные изображения. При проектировании спортивной одежды предполагается использовать 3-х мерные модели элементов одежды.

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

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

Список литературы

1. Сараев А. Д., Щербина О. А. Системный анализ и современные информационные технологии //Труды Крымской Академии наук. -- Симферополь: СОНАТ, 2006. -- С. 47-59

2. В.К. Глянцев. Основы логической реализации экспертной системы для подготовки производства специальной одежды[Текст] / В.К. Глянцев , А.А. Тарапанов // Труды второй международной научно-технической конференции «Компьютерные науки и технологии 2011» - 2011

3. Вовк, А.А. Технология формирования обобщенного «И/ИЛИ» дерева решения задач анализа изображений. Исследование скорости сходимости процесса формирования обобщенного «И/ИЛИ» дерева/ Вовк, А.А., Цибульский, Г.М., Латынцев, А.А.// Техника и технологии. Engineering & Technologies. 2009 2 (1) - С. 32-48

4. Ефимов Е.И. Решатели интеллектуальных задач / Е.И.Ефимов. -- М.: Наука, 1982. -- 320 с

Размещено на Allbest.ru