Дерево модель системы сообщение

Обновлено: 05.07.2024

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

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

1 Что такое деревья (в программировании)?

В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].

Рабочее определение (в рамках этой статьи): дерево — это способ организации данных в виде иерархической структуры.

Когда применяются древовидные структуры:

2 Деревья и другие структуры данных

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

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

удаление элемента по указателю (итератору)

поиск элемента с заданным значением

вставка элемента (значения)

(вернет i-тый по значению элемент)

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

При поиске значения в массиве мы в худшем случае переберем все элементы, то есть выполним O(n) операций. Однако, если массив упорядочен — мы можем применить двоичный поиск, который значительно эффективнее.

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

Деревья поиска, как и связные списки состоят из узлов, связанных указателями. Однако узлы эти упорядочены определенным образом — за счет этого увеличивается эффективность поиска, но осложняется операция вставки элемента. Эта структура данных, в ряде случаев,может иметь преимущества над массивами и связными списками — посмотрим за счет чего это обеспечивается…

3 Деревья поиска

Двоичное дерево состоит из узлов, каждый из которых хранит свое значение, а также две ссылки — на правое и левое поддерево. Если справа или слева нет узлов — соответствующая ссылка равна нулю (в С++ — нулевой указатель). Дерево представляется корнем (ссылкой на самый верхний узел).

Особенность дерева поиска заключается в алгоритме построения — значения вершин левого поддерева должны всегда оказываться меньше или равны значению корневого узла, а правого – больше.

При обходе такого дерева, начиная с левого поддерева, значения будут просмотрены в порядке неубывания, начиная с правого – невозрастания, т.е. дерево поиска хранит отсортированные данные:

если дерево является пустым – то E помещается в корневую вершину;
если значение E больше значения корневой вершины – осуществляется вставка E в правое поддерево (рекурсивно), иначе – в левое.

Пример использования такого алгоритма приведен в таблице:

Шаг 0: исходное дерево
Шаг 1: определям, что вставлять нужно в левое поддерево
Шаг 2: 6 > 4 , поэтому вставляем в правое поддерево
Шаг 3: 6 , вставка в левое поддеррево
Шаг 4: 6 > 5 , вставляем справа, но там пусто.

В качестве упражнения полезно попробовать вставить в дерево узел со значением 8.5 , а также, взять пустое дерево (без элементов) и добавить в него последовательно узлы [1, 11, 32, 46, 48] . Если в результате у вас получится дерево, как на приведенной ниже картинке — вы все поняли и сделали правильно:

Удаление элемента из дерева поиска, несколько запутаннее, поэтому алгоритм тут не приведен, зато приведены поясняющие иллюстрации:

4 Kd-деревья

Во многих программах появляется необходимость хранения и эффективной обработки объектов на плоскости. Это не только картографические приложения, но и все двумерные игры. Задумывались ли вы о том, как эту задачу решают игровые движки?

Игровой уровень обычно значительно больше, чем видимая в данный момент область экрана, а отрисовывать необходимо только видимые объекты. Значит движок должен уметь быстро получать объекты, входящие в заданную прямоугольную область. Кроме того, объекты умеют перемещаться и сталкиваться друг с другом — когда Марио собирает монетку, она исчезает, а счет увеличивается. Игровой движок должен эффективно реализовывать обработку столкновения объектов — подумайте почему эта задача сводится к первой. Примитивная реализация поиска столкнувшихся объектов может заключаться в переборе всех пар, то есть имеет вычислительную сложность O(n^2) . Даже в Марио (которой более 20 лет) уровни содержали тысячи объектов, а значит такой алгоритм не подойдет.

Мы уже разобрались с тем, что для эффективной реализации поиска объекты нужно хранить упорядоченными. Однако, как хранить точки? — ведь у них есть две (или три) координаты, а сортировка по одной из них не обеспечит приемлемую скорость поиска. Именно эти проблемы решают Kd-деревья.

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

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

Первый вариант решения:

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

Пример построения такого дерева приведен на рисунке. Тут плоскость сначала разбита относительно точки А на левую и правую, правая в свою очередь разбита на нижнюю и верхнюю относительно точки С. Нижняя опять разбивается на левую и правую относительно точки D .

С такой структурой данных, алгоритм вывода всех точек, входящих в Прямоугольник может выглядеть так:

Описанный подход называется Kd-деревья с циклическим проходом по измерениям. Возможны и другие варианты выбора секущей плоскости — например каждый узел квадрадерева делит свою часть плоскости на 4 части (левая верхняя, левая нижняя, правая верхняя, права нижняя). Если в какой-то части оказывается более 1 объекта — то она делится дальше. Октадеревья адаптируют эту идею к трехмерному пространству.

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.

Ответ

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

Всякая иерархическая система может быть представлена с помощью дерева.

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

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

ГОСТ

Что является деревом модели?

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

В ходе работы с любой деталью на экране отображается окно, которое содержит Дерево модели.

Деревом модели является графическое представление набора объектов, которые составляют детали. Корневым объектом Дерева является непосредственно деталь. После того как объекты фиксируются в детали, их пиктограммы автоматически появляются в Дереве модели.

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

Состав и структура дерева модели

В Дереве модели изображаются: обозначения начала координат, плоскостей, осей, эскизов, операций и указателя окончания построения модели.

Готовые работы на аналогичную тему

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

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

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

Как правило, пиктограммы изображены в Дереве модели синими. У выделенного объекта пиктограмма зеленая. При выполнении операций объекты отображаются красными пиктограммами.

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

Кроме того, стал возможен просмотр отношений выделенного элемента дерева (компонента, операции, сопряжения) на отдельной панели в нижней части дерева построения (см. рис. 1а). С помощью этой панели стало возможным редактирование отношения.

Дерево модели: представление в виде структуры (а) и обычное дерево (б):

Любой раздел дерева открывается в отдельном окне, что делает возможным его редактирование (рис. 2).

Раздел дерева в отдельном окне:

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

Раскрывающийся список кнопки Состав Дерева модели:

Помимо кнопки Состав Дерева модели используется кнопка Отношения, которая позволяет скрыть или отобразить панель отношений внизу дерева модели.

И еще одна кнопка – Дополнительное окно Дерева модели предоставляет возможность открыть в дополнительном окне выбранный раздел дерева. Эта кнопка не будет активной, если в дереве модели нет ни одного выделенного элемента.

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

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

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

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

Появляется состязательность вариантов.

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

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

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

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

Систематизацию и упорядоченность выявленных способов достижения поставленных целей рекомендуется осуществлять построением дерева систем – ДС

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

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

Дерево целей и дерево систем могут совпадать, а могут и не совпадать.

Дерево систем строится по тем же законам, что и дерево целей. Определяется генеральная система С О , которая структуризируется

на подсистемы первого, второго и последующих уровней (С 1 _о1, С 1 _о2 , … С 1 _о_n и т.д.).

Пример дерева систем

1). Дерево систем технической эксплуатации машин

Где: 1.1 ужесточение нормативов системы ТОиР;

1.2 обеспечение выполнения рекомендаций нормативов;

1.3 совершенство технологии, организации и управления ТОиР;

1.4 обеспеченность НТД(нормативно-технической документации) и другой документацией;

1.5 совершенство проектной документации на строительство и реконструкцию предприятий;

1.6 повышение приспособленности системы ТЭ к изменению конструкции машин и условиям их эксплуатации;

2.1 обеспеченность (повышение) производственно технической базы (ПТБ);

2.2 оптимизация мощности и структуры ПТБ ;

2.3 оптимизация пропускной способности средств ТОиР;

2.4 повышение уровня механизации и автоматизации процессов ТОиР;

2.5 специализация ПТБ;

2.6 кооперация ПТБ на отраслевом и региональном уровне;

3.1 обеспеченность ремонтно – обслуживающим персоналом;

3.2 повышение квалификации ремонтных рабочих, водителей и ИТР;

3.3 совершенствование систем хозрасчета и стимулирования персонала;

3.4 обеспечение стабильности трудовых коллективов;

3.5 повышение престижности профессий;

3.6 развитие коллективных форм работы;

4.1 совершенствование системы снабжения;

4.2 совершенствование норм расхода ГСМ и материалов;

4.3 обеспечение оптимальных запасов запчастей, агрегатов, материалов;

4.4 совершенствование и сокращение продолжительности обмена изделий при капитальном ремонте;

4.5 совершенствование процесса получения новых машин;

4.6 создание резерва производственных площадей, оборудования и персонала;

4.7 создание резерва исправных машин;

5.1 повышение исходного и реализуемого уровня качества и надежности изделий;

5.2 повышение качества эксплуатационных материалов;

5.3 повышение качества восстановления деталей и капитального ремонта;

5.4 изменение структуры парка (тип, грузоподъемность, вместимость, специализация);

5.5 управление возрастной структурой парка;

5.6 уровень унификации изделий и материалов;

6.1 природно-климатические условия;

6.2 дорожные условия;

6.3 транспортные условия и интенсивность использования подвижного состава;

6.4 подбор автомобилей, изделий и материалов с учетом условий эксплуатации;

6.5 использование автомобилей с учетом их технического состояния, возраста и условий эксплуатации.

2. Дерево систем совершенствования технической эксплуатации автомобилей (другая форма).

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

Схема высшего, первого и второго ярусов дерева систем технической эксплуатации

Обозначения:

Из рисунка следует, что важнейшими целереализующими факторами первого уровня являются:

Значение построения ДЦ и ДС для управления:

1. Выявляются все факторы, влияющие на достижение цели;

2. Можно оценить уровень влияния и найти наиболее действенные подсистемы;

3. Исключена реализация целей низшего уровня за счет высшего (сохраняется иерархия);

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

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

6. Декомпозиция позволяет более конкретно проанализировать составляющие и избежать серьезных ошибок, свойственных большим системам;

7. Построение и анализ ДЦ и ДС обычно используется при разработке сложных программ совершенствования больших систем.

Читайте также: