РАЗРАБОТКА СИСТЕМЫ ДЛЯ РАБОТЫ С АЛГОРИТМАМИ НА ГРАФАХ Жигмонт Андрей Владимирович e-mail: zhigmont@gmail.com@gmail.com Магистрант ММФ БГУ, кафедра численных.

Презентация:



Advertisements
Похожие презентации
Обработка аудио и видео, разработка редактора для создания видео учебников Иванов Сергей Валерьевич Магистрант ММФ БГУ, кафедра веб-технологий и компьютерного.
Advertisements

Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ
Нижегородский государственный университет им. Н.И. Лобачевского Факультет вычислительной математики и кибернетики Учебно-исследовательская лаборатория.
Методы распознавания зашумленных образов БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра математического.
Разработка модели и реализация системы администрирования web-сайта Магистрант математического факультета Антоник Денис Владимирович руководитель Переверзева.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
ЕМЕЛЬЯНЧЕНКО Наталья Сергеевна МОДЕЛИ И АЛГОРИТМЫ ДЛЯ ЗАДАЧ ТЕОРИИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ.
РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ КОНКУРЕНТНОГО РЫНКА НА КЛАСТЕРНЫХ СИСТЕМАХ Авторы: Е.В. Болгова, А.С. Кириллов, Д.В. Леонов Научный.
Разработка программного комплекса для решения некоторых задач формирования производственных групп БУШИНСКИЙ Сергей Дмитриевич Омский государственный технический.
Введение в задачи исследования и проектирования цифровых систем Санкт-Петербургский государственный университет Факультет прикладной математики - процессов.
Магистерская диссертация 2009 Журак И.К. 1 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра информационного.
1 Алгоритмы построения надежных сетей Алдын-оол Татьяна Андреевна аспирант 1 года ММФ Руководитель – А.И. Ерзин.
Использование орграфов в задачах производственного планирования Дмитрий Петренко Донецкий Национальный Технический Университет.
Белорусский государственный университет Механико-математический факультет Кафедра функционально анализа Жук Анастасия Игоревна Системы дифференциальных.
СПЕЦИАЛИЗИРОВАННАЯ ИНСТРУМЕНТАЛЬНАЯ ОБОЛОЧКА ДЛЯ АВТОМАТИЗАЦИИ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ САПР С ДИФФЕРЕНЦИРОВАННЫМ ПОДХОДОМ К КВАЛИФИКАЦИИ ПОЛЬЗОВАТЕЛЯ.
Теория экономических информационных систем Представление дисциплины.
Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.
Задача распределения потоков при моделировании пропуска трафика в сети NGN докладчик: Муравьев Василий Владимирович руководитель: к.ф.-м.н., доц. Чукарин.
Кафедра «Кибернетика» Дипломная работа по направлению «Прикладная математика и информатика» на тему: Разработка приложения для управления.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Транксрипт:

РАЗРАБОТКА СИСТЕМЫ ДЛЯ РАБОТЫ С АЛГОРИТМАМИ НА ГРАФАХ Жигмонт Андрей Владимирович Магистрант ММФ БГУ, кафедра численных методов и программирования руководитель: СУЗДАЛЬ Станислав Валерьевич, кандидат физ.-мат. наук

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

Немного истории В 2009 году на механико-математическом факультете в СНИЛ Дискретные структуры и алгоритмы начала раз- рабатываться система работы с графовыми моделями и алгоритмами GraphMagic, которая должна была быть лишена многих недостатков других известных специа- лизированных систем.

Изучить и проанализировать архитектуру системы GraphMagic и её возможности по расширению. Задачи Разработать плагин(дополнительный программный модуль), позволяющий применять к графам алгоритм поиска множества K реберно-непересекающихся путей между двумя заданными вершинами графа с наименьшей суммой весов ребер, входящих в цепи множества(кратчайшего K множества реберно- непересекающихся цепей), K2.

Преимущества GraphMagic Дополняемость Кроссплатформенность Открытость и бесплатность(General Public License version 2, разработанная Free Software Foundation в 1991 году)

Основные модули проекта: ядро, оболочка и плагины Архитектура GraphMagic

Интерфейс Graph Архитектура GraphMagic

Интерфейсы вершины и ребра графа Архитектура GraphMagic

Интерфейс GraphMagicPlugin Архитектура GraphMagic

Plugin edge-Disjoint-Paths Описание плагина Разработанный плагин позволяет решать две следующие задачи: Построение кратчайшей пары реберно- непересекающихся путей между двумя вершинами; Построение K(K>2) кратчайшего множества реберно- непересекающихся путей между двумя вершинами.

Используемые технологии и алгоритмы Описание плагина Технологии: o Java o Swing o JUnit o EasyMock o Maven Алгоритмы: o Алгоритм Дейкстры (Dijkstras algorithm). o Модифицированный aлгоритм Дейкстры (Modified Dijkstras algorithm).

Алгоритм нахождения кратчайшей пары реберно- непересекающихся путей между двумя вершинами Описание плагина 1.Находим кратчайший путь Р из стартовой вершины s в конечную вершину t (Алгоритм Дейкстры). 2.Ориентируем (разворачиваем) все рёбра пути Р по направлению от t к s и присваиваем им отрицательный вес. 3.В получившемся графе находим кратчайший путь Q из s в t (используя модифицированный алгоритм Дейкстры). 4.Удаляем из P и Q ребра, принадлежащие и Р и Q. 5.Из P и Q формируются два кратчайших рёберно- непересекающихся пути из s в t.

Алгоритм нахождения K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами Описание плагина 1.Находим кратчайший путь Р из стартовой вершины s в конечную вершину t (Алгоритм Дейкстры). 2.Ориентируем (разворачиваем) все рёбра пути Р по направлению от t к s и присваиваем им отрицательный вес. 3.В получившемся графе находим кратчайший путь Q из s в t (используя модифицированный алгоритм Дейкстры). 4.Ориентируем (разворачиваем) все рёбра пути Q по направлению от t к s и присваиваем им отрицательный вес(если ребро уже было с отрицательным весом, тогда его вес не меняеться).

Алгоритм нахождения K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами Описание плагина Проделываем K-2 раз следующие операции: o В получившемся графе находим кратчайший путь Qi из s в t (используя модифицированный алгоритм Дейкстры). o Ориентируем (разворачиваем) все рёбра пути Qi по направлению от t к s и присваиваем им отрицательный вес(если ребро уже было с отрицательным весом, тогда его вес не меняеться). Удаляем из P,Q,Qi (i=1,K-2) все ребра, принадлежащие хотя бы двум путям. Из P,Q,Qi (i=1,K-2) формируются k кратчайших рёберно- непересекающихся путей из s в t.

K=2 Результаты работы плагина

K=3 Результаты работы плагина

K=4 Результаты работы плагина

Изучена и проанализирована система GraphMagic и её возможности по расширению. Заключение Разработан плагин, позволяющий применять к графам алгоритм поиска множества K реберно- непересекающихся путей между двумя заданными вершинами графа с наименьшей суммой весов ребер, K2.

СПАСИБО ЗА ЗАВНИМАНИЕ!