Исследование и анализ параллельных алгоритмов поиска кратчайшего пути в графе

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

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

Исследование и анализ параллельных алгоритмов поиска кратчайшего пути в графе

Кондратенко Владислав Евгеньевич, студент

Фадеева Марина Викторовна, старший преподаватель

Волгоградский государственный технический университет

Введение

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

Алгоритмы поиска кратчайших путей на графах нашли свое применение в различных областях и сферах деятельности человека. Такие алгоритмы используются в картографических сервисах, при построении пути GPS-навигатора [7], для представления и анализа дорожной сети [8] и во многих других областях [1,9, 11-14]. При этом в настоящее время существует большое число алгоритмов и подходов, которые решают эту задачу. Кроме того, в большинстве своем алгоритмы можно логически разделить на два класса -- алгоритмы поиска кратчайшего расстояния от одной вершины до всех остальных и алгоритмы поиска кратчайших расстоянии между каждой парой вершин [1, 6].

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

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

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

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

· Составить математическое описание информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов.

· Выполнить программную реализацию информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов.

· Проверить эффективность реализованных алгоритмов информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов [2].

Постановка задачи

Сначала был выполнен анализ основные понятия теории построения графов, приведены примеры графов различного вида. Множество X = { x₁, x₂,..., x_k,... } и набор E пар объектов вида { x_i, x_j } или (x_i, x_j) из множества X называется графом и обозначается обычно символом G.

Далее были рассмотрены такие алгоритмы как: Последовательный алгоритм Флойда - поиск кратчайшего пути и Последовательный алгоритм Прима - нахождение минимального охватывающего дерева. В дальнейшем планируется реализации данных алгоритмов и выполнение их сравнительного анализа [2].

Начальной информацией для проблемы поиска кратчайшего пути обычно является исходных взвешенный граф $G=(V,R)$, который содержит $n$ вершин, задан неотрицательный вес. Предполагается, что граф ориентированный, т.е. если из некоторой вершины $i$ существует ребро в вершину $j$, то из этого не следует и обратное наличие ребра из $j$ в $i$. В том случае, если вершины все же соединены взаимообратными ребрами, веса, которые им приписаны, могут и не совпадать. Далее необходимо рассмотреть задачу, в которой для заданного графа G необходимо найти минимальные длины путей между каждой парой вершин графа.

В заключении был выполнен анализ применение алгоритмов поиска кратчайшего пути в графах. Самым распространенным применением алгоритмов поиска кратчайшего пути в графе является их применение в системах навигации для построения маршрутов между несколькими точками, обозначающими физические объекты. Поэтому в данном разделе были рассмотрены следующие системы: Сервис GraphOnline, Пакет утилит Graphviz, Система neo4J, Система GraphX [1].

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

A₁ - задание информации о вершинах графа текстом;

A₂ - задание связей между вершинами визуально;

A₃ - задание матрицы смежности вершин графа;

A₄ - поиск и визуализация кратчайшего пути в графе;

A₅ - оценка точности алгоритмов поиска кратчайшего пути.

Для вычисления весов критериев можно использовать аналитическую иерархическую процедуру Саати [3, 5, 10]. Заданная матрица парных сравнений, вычисленные величины средних геометрических и весов критериев представлены в таблице 1.

Таблица 1 - Матрица парных сравнений, средние геометрические и веса критериев

Диаграмма весовых коэффициентов для выбранных критериев A1, A2, A3, A4, A5 представлена на рисунок 1.

Рисунок 1. Весовые коэффициенты критериев качества

Далее необходимо выполнить проверку матрицы попарных сравнений на непротиворечивость.

Суммы столбцов матрицы парных сравнений: R₁=16.33; R₂=17; R₃=9.67; R₄=4.73; R₅=1.88.

Путем суммирования произведений сумм столбцов матрицы на весовые коэффициенты альтернатив рассчитывается вспомогательная величина L = 5.34. Индексом согласованности ИС = (L-N)/(N-1) = 0.08.

Значение величины случайной согласованности для размерности матрицы парных сравнений: СлС = 1.12.

Значение отношения согласованности ОС=ИС/СлС = 0.075. не превышает 0.2, поэтому уточнение матрицы парных сравнений не требуется.

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

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

Значения весовых коэффициентов a_i соответствующие функциональным возможностям продуктов:

1. задание информации о вершинах графа текстом a₁=0.069;

2. задание связей между вершинами визуально a₂=0.047;

3. задание матрицы смежности вершин графа a₃=0.13;

4. поиск и визуализация кратчайшего пути в графе a₄=0.27;

5. оценка точности алгоритмов поиска кратчайшего пути a₅=0.49. где .

Вычислим (по введенной шкале) количественные значения функциональных возможностей $X_{ij}$ (таблица 2). Определим интегральный показатель качества для каждого программного продукта [4].

Таблица 2. Интегральные показатели качества

Построим лепестковую диаграмму интегрального показателя качества каждого программного продукта (рисунок 2).

Рисунок 2. Лепестковая диаграмма интегральных показателей качества программных продуктов

алгоритм кратчайший путь граф

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

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

На рисунке 4 показана диаграмма верхнего уровня процесса «Поиск кратчайшего пути в графе».

Рисунок 4. Диаграмма верхнего уровня процесса «Поиск кратчайшего пути в графе».

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

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

Исполнителями процесса являются пользователь ИС и информационная система (ИС*).

Управление процессом осуществляется на основании математической модели алгоритмов поиска кратчайшего пути.

Поиск кратчайшего пути в графе осуществляется в пять этапов:

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

2. заполнение матрицы смежности графа» - на данном этапе выполняется заполнение матрицы связей вершин графа;

3. реализация алгоритма Флойда» - на данном этапе выполняется расчёт кратчайших путей между вершинами графа (при попарном их сравнении), вычисленные значения сохраняются во внутренние переменные системы;

4. реализация алгоритма Прима» - на данном этапе выполняется расчёт кратчайших путей между вершинами графа (при попарном их сравнении), вычисленные значения сохраняются во внутренние переменные системы;

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

На рисунке 5 показана детализация процесса «Поиск кратчайшего пути в графе».

Рисунок 5. Декомпозиция диаграммы А1 «Поиск кратчайшего пути в графе».

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

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

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

1. ИЗОТОВА Т.Ю. Обзор алгоритмов поиска кратчайшего пути в графе // Новые информационные технологии в автоматизированных системах. 2016. №19 С.341-344.

2. ФамКонгТханг, Нгуен Ван Хьеу Построение алгоритма поиска кратчайшего пути на расширенном графе // Известия ТулГУ. Технические науки. 2013. №11 С.367-372.

3. Морозов А.О., Рыбанов А.А. Экспертная оценка программных продуктов для расчета метрических характеристик физической схемы базы данных // Современные научные исследования и инновации. 2015. № 1-1 (45). С. 97-102.

4. Рыбанов А.А., Макушкина Л.А. Технология определения весовых коэффициентов сложности тем дистанционного курса на основе алгоритма Саати // Открытое и дистанционное образование. 2016. № 1 (61). С. 69-79.

5. Рыбанов А. Определение весовых коэффициентов сложности тем учебного курса на основе алгоритма Cаати // Педагогические измерения. 2014. № 4. С. 21-28.

6. Рыбанов А.А., Усмонов М.С.О., Попов Ф.А., Ануфриева Н.Ю., Бубарева О.А. Информационные системы и технологии/Научный ред. И. А. Рудакова/Центр научной мысли (г. Таганрог). Москва, 2013. Том Часть 4. -90 с.

7. Моисеев Ю.И., Билялов М.Х., Рыбанов А.А. Система идентификации водителя на примере туристического междугороднего автобуса Волжанин 5285//Вестник магистратуры. 2013. № 5 (20). С. 63-67.

8. Лебединский А.И., Рыбанов А.А. Автоматизация мониторинга топлива в резервуарах азс на базе измерительного комплекса "Струна" с целью повышения эффективности принимаемых решений специалистом отдела логистики//Молодой ученый. 2014. № 7. С. 35-40.

9. Rybanov A., Tretyakova V. Application of Fitts's law to the assessment of users' skills of work with computer devices of targeting//Pedagogical and psychological problems of the modern society: scientific approaches to the study and overcoming practices 2nd edition: research articles. Science editor: A. Burkov.San Francisco,California,USA, 2015. С. 39-47.

10. Кондрацкий Д.Е., Рыбанов А.А. Исследование методов и алгоритмов автоматизированной системы оценки альтернативных вариантов методом Т.Саати//NovaInfo.Ru. 2016. Т. 3. № 46. С. 107-116.

11. Морозов А.О., Рыбанов А.А. Разработка автоматизированной системы расчета метрических характеристик mysql базы данных на основе концептуального графа физической схемы//NovaInfo.Ru. 2015. Т. 2. № 34. С. 34-48.

12. Рыбанов А.А. Оценка сложности физической схемы реляционной базы данных//Современная техника и технологии. 2014. № 9 (37). С. 26-30.

13. Рыбанов А.А., Морозов А.О. Автоматизация расчета метрических характеристик физических схем баз данных на основе концептуальных графов//Молодой ученый. 2014. № 9 (68). С. 26-30.

14. Рыбанов А.А., Фатеенков М.М. Разработка и анализ хранимой процедуры для получения глубины дерева связей таблицы и схемы базы данных//NovaInfo.Ru. 2015. Т. 1. № 34. С. 41-55.

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