Главная » Просмотр файлов » Диссертация

Диссертация (1090614), страница 9

Файл №1090614 Диссертация (Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов) 9 страницаДиссертация (1090614) страница 92018-01-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Каждая вершина перемещается на подсчитанный вектор в случае, если егодлина больше или равна . Переход к шагу 4.4. Если ни одна вершина не была смещена (т.е. длины всех векторовсмещений оказались меньше ), то переход к шагу 5, иначе – переход кшагу 6.5. Если текущее количество итераций превысило заданный порог k, товыполняется переход к шагу 6, иначе – переход к шагу 2.6.

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

2.5, Рис. 2.7).Рис. 2.5. Результат применения автоматического размещения «павлиний хвост».Базовый метод физических аналогий ограничен размером исследуемогографа: хорошие результаты на небольших графах, плохие результаты на графах,состоящих более чем из сотни вершин. Плохая применимость классическогоподхода на больших графах обусловлена несколькими причинами. Одной изосновных причин является тот факт, что используемая физическая модель обычноимеет большое множество локальных минимумов.Даже использование сложных механизмов получения локального минимумане дают базовому методу хороших результатов при работе на больших графах.Однако, существуют оптимизации, позволяющие получать приемлемыерезультаты на графах, размеры которых достигают десятки и даже сотни тысячвершин.

Ключевая идея оптимизации заключается в технике многоуровневогоразмещения, которая состоит в том, чтобы представить граф в более простой форме(сгруппировать вершины в иерархически вложенный набор кластеров), применитьклассический алгоритм размещения к данному упрощенному представлению иповторить аналогичные операции для каждого из выделенных кластеров. Темсамым базовый метод размещения на основе физических аналогий будетиерархически углубляться от более простых структур к сложным.632.2.2.Геометрическая модель автоматического размещения «быстрыйпавлиний хвост»Вданномразделепредлагаетсягеометрическаямодельалгоритмаавтоматического размещения [14], базирующегося на основе метода физическиханалогий под названием «быстрый павлиний хвост».Алгоритм 2.7.

Размещение «быстрый павлиний хвост» для всего графа.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1. Множество вершин графа разбивается на компоненты связности(Алгоритм 2.3). Переход к шагу 2.2. Выполняется размещение каждой компоненты связности независимо другот друга с использованием построения минимального остовного дерева(Алгоритм 2.8). Переход к шагу 3.3. Совмещение размещенных компонент в одно размещение. Размещениядлякаждойкомпонентысвязностирасполагаютсявдольоднойгоризонтальной прямой, гарантируя отсутствие пересечений соседнихкомпонент связности. Переход к шагу 4.4.

Конец алгоритма.Результат: построено размещение вершин графа на плоскости.Алгоритм 2.8. Размещение «быстрый павлиний хвост» для одной компонентысвязности.Вход: множество вершин, входящих в одну компоненту связности.Последовательность шагов:1. Выполняется построение минимального остовного дерева. Переход кшагу 2.2. Выполняется поиск корневой вершины. Переход к шагу 3.3. Корневая вершина располагается на плоскости.

Переход к шагу 4.644. Выполняетсяразмещениедетейпоследнихдобавленныхвершин(определяются из остовного дерева) на плоскости с использованием (2.4).Переход к шагу 5.5. Добавление новых связей из исходного графа между присутствующимивершинами на схеме. Переход к шагу 6.6. Перемещение вершин с использованием (2.5). Переход к шагу 7.7. Если все вершины добавлены на плоскость, то переход к шагу 8. Иначе –переход к шагу 4.8. Конец алгоритма.Результат: построено размещение вершин графа из одной компоненты связностина плоскости.Асимптотическая сложность алгоритма «быстрый павлиний хвост» равна( ∗ с ∗ (|| + ||)), где – диаметр визуализируемого графа, – множествовершин, – множество ребер, с – константа (по умолчанию равна 25), задающаяколичество итераций при размещении очередного слоя (Алгоритм 2.9.

шаг 6).Благодаря использованию метода физических аналогий вершины обладаютсилой притяжения за счет связей-пружин и отталкивающей силой за счет зарядавершинивсетехжесвязей-пружин.Нижеприведенынесколькоосновополагающих идей, на которых базируется данный алгоритм. Такжеприводится более подробное описание каждого шага.Размещение графа основывается на выделении минимального остовногодерева (Алгоритм 2.8 шаг 1). Построение минимального остовного деревавыполняется с помощью алгоритма Крускала [10].Минимальное остовное дерево строится для того, чтобы построитьпоследовательность добавления вершин на плоскость, начиная с корневой .Корневая вершина будет первой, которая получит координаты на плоскости.Выбор корневой вершины (Алгоритм 2.8 шаг 2) может осуществлятьсяразными способами в зависимости от свойств исследуемых графов.

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

Например, корневая вершина будетиметь уровень 0, инцидентные ей вершины – уровень 1. Данные уровнипроставляются на основе алгоритма обхода в ширину.Начиная с корневой вершины, вершины каждого уровня последовательнодобавляются на плоскость (Алгоритм 2.8 шаг 3). Каждый следующий уровеньвершин из минимального остовного дерева добавляется на заранее заданную сетку̅на плоскости по новой окружности (Алгоритм 2.8 шаг 4) на позицию ℎ(рассчитывается для каждой вершины уровня), которая является линейнойкомбинацией двух других векторов. Первый вектор – текущий центр масс̅ .

другой вектор - ̅ , соединяющий родительскую вершину текущейразмещения с прародительской (родительской вершиной родительской вершины для текущейдобавляемой вершины).̅̅̅ℎ= с ( ̅ + ̅ ) + ̅|| | |̅=1| |∑̅ ′ ′ ∈̅ = ̅ − ̅(2.4)66̅ | – длина вектора ̅ , |̅| – длина вектора ̅ , –Где с – константа, |представляет множество всех вершин, присутствующих на схеме, | | мощность множества (количество всех вершин, присутствующих на схеме).И так, вслед за добавлением вершин новые ребра добавляются только междутеми вершинами, которые присутствуют на схеме (Алгоритм 2.8 шаг 5).Затем происходит перемещение вершин (Алгоритм 2.8 шаг 6) за счетподсчета вектора смещения, определяющегося действием влияющих на вершинусил рассматриваемой физической модели.

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

Оптимизация достигается за счет анализа только соседних вершин,попадающих в локальную область на плоскости вокруг рассматриваемой вершиныграфа.Вектора сил притяжения и отталкивания считаются для каждой вершины изатем суммируются. Таким образом подсчитывается вектор смещения вершины наплоскости (Алгоритм 2.8 шаг 6). В процессе размещения вершин используетсядерево (Рис. 2.6), благодаря которому определяется порядок, по которому вершиныучаствуют в вычислении сил взаимодействия пружин. Вершины располагаются,начиная с корня минимального остовного дерева. Минимальное остовное деревоопределяется как минимальный набор ребер, необходимый для того, чтобы графостался связным, и сумма весов ребер была минимальной. Использование67минимального остовного дерева позволяется в итеративном процессе переходадинамической системы к состоянию равновесия сохранить структуру исходногографа, базирующуюся на центральности вершин.Рис.

2.6. Процедура размещения вершин на плоскости с учетом минимальногоостовного дерева, начиная с корня дерева.Суммарная сила, действующая на вершину на каждом шаге алгоритма засчет взаимодействия (притяжения и отталкивания) с другими вершинамирассчитывается по следующей формуле:⃗, = ⃗, + ⃗, == − ∑(|⃗ | − ) ∙ ⃗ − ∑(|⃗ | − ) ∙ ⃗ ,=1(2.5)=0где:• = 0 для всех |⃗ | > • и – константы, определяющие степень влияния притяжения иотталкивания от вершины;• - рекомендуемая длина связи с инцидентной вершиной ;• ⃗ – вектор между вершиной u и i;• |⃗ | – евклидово расстояние между двумя вершинами одного ребра, т.ерасстояние между текущей вершиной и соседней вершиной ;• – количество связей, одним концом из которых является вершина ;68• –количествовершинвлокальнойобластинаплоскости,удовлетворяющих неравенству |⃗ | < ;• ⃗ – вектор между вершиной u и вершиной j, вершины u и j не связаны,вершина j находится от вершины u на расстоянии меньше r;• отталкивание между вершинами применимо только в случае, когда ониближе друг другу на расстояние, меньшее чем .На Рис.

Характеристики

Список файлов диссертации

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее