Разработка алгоритмов

Сфери застосування алгоритмів пошуку найкоротших шляхів
Пошук шляхів на мапах міст та країн
Пошук маршрутів для передачі даних у мережах
Пошук маршрутів у інших задачах, де доцільно використовувати графи

Види алгоритмів пошуку найкоротших шляхів
Пошук шляху із однієї заданої точки в іншу (алгоритм A*, etc)
Пошук шляхів із однієї заданої точки до усіх інших (алгоритм Дейкстри, алгоритм Белмана-Форда, etc)
Пошук шляхів між усіма парами точок на графі(алгоритм Флойда-Уоршала, алгоритм Джонсона, etc)

Постановка завдання
Розробити алгоритм пошуку найкоротших шляхів для кожної пари точок на графі із кластерною топологією
Розроблений алгоритм повинен мати меншу за
складність на графі із кластерною топологією

Алгоритм Флойда-Уоршала
Базується на переборі усіх вершин i, j, k та перевірці умови:
Якщо найкоротший шлях між i та j проходить через вершину k, то відстані від i до k та від j до k додаються
Інакше обирається інша k та продовжується пошук
Пункти 1 та 2 повторюються у циклі по усьому графу

Існуючі спроби рішень
Паралелізація алгоритму на декількох процесорах
Модифікації алгоритму
Рекурсивне обрання підматриць, відновлення результату через FMM

Кластерна топологія графів
У звичайному графі вершини
зв'язані одна з одною як завгодно,
без строгого порядку.
Під кластерною топологією будемо
розуміти існування угруповання
вершин на графі, зв’язаних одна з
одною значно більшою кількістю
ребер, ніж із іншими такими
угрупованнями.

Ідея алгоритму
Алгоритм базується на принципі divide and conquer - розділяй та володарюй.
Розіб’ємо задачу на підзадачи, що будуть мати меншу розмірність, а потім проведемо певні дії для одержання суцільного результату

Зовнішній каркас графа
За умовою наявності кластерної топології, лише через малу кількість вершин одного кластеру можна потрапити до іншого кластеру.
Будемо називати усі ці вершини зовнішнім каркасом графа.

Опис алгоритму
Знаходження усіх найкоротших шляхів всередині кожного з кластерів
Знаходження усіх найкоротших шляхів на зовнішньому каркасі графа
Знаходження усіх найкоротших шляхів між точками з одного кластеру до точок з кожного іншого кластеру

Математична оцінка складності алгоритму
Позначення:
Кількість вершин у всьому графі – N
Кількість кластерів – К
Кількість вершин у i-тому кластері графа –
(де i = 1..K )
Кількість зовнішніх точок – op
Кількість зовнішніх шляхів – ops

Математична оцінка складності алгоритму
Для кожного кластера застосувати алгоритм Флойда-Уоршала –
Для зовнішніх точок застосувати алгоритм Флойда-Уоршала –
Пошук шляхів між кластерами –
Результуюча формула:

Аналіз моделі
Спрощена оцінка при гіпотезі рівновеликих кластерів:
Підвищення ефективної кількості зовнішніх точок
із ростом числа справжніх кластерів у графі

Аналіз моделі
Зменшення долі ефективної кількості зовнішніх вершин у графі залежно від кількості кластерів

Вибір мови програмування
Враховуючи основну вимогу до алгоритму – швидкодію, для реалізації було вирішено обрати мову С++
Переваги С++:
Відсутність віртуального середовища обробки
Прямі операції з пам'яттю на рівні мови
Наявність допоміжних алгоритмів STL

Результати роботи програми
На вхід було запропоновано:
Граф із більш ніж 1800 точок мапи України
Автоматично згенеровані графи
На виході було отримано:
Однакові матриці шляхів за звичайним алгоритмом Флойда-Уоршала та розробленою модифікацією
Час виконання модифікованого алгоритму виявився меншим при вдало обраних кластерах

Фрагмент таблиці тестувань часу роботи

Висновки
Реалізовано алгоритм пошуку найкоротших шляхів між усіма парами точок на графі із кластерною топологією.
Проведено тестування, в ході якого виявлено зменшення часу виконання у модифікованому алгоритмі.
Приведено повну та спрощену оцінки складності алгоритму, на базі спрощеної проведено аналіз алгоритму.
Результати роботи можуть бути використані у будь-якій сфері, де встає необхідність пошуку найкоротших шляхів на графі, якщо його топологія кластерна.

Дякую за увагу!

Додаткові слайди

Недоліки автоматичних алгоритмів кластеризації у розглянутій задачі
Невідома кількість кроків => обчислювальна складність (k-means, forel, etc)
Невідповідність початковим припущенням алгоритмів реальних графів (EM, SEM, etc)
Відома занадто велика складність алгоритмів (KRAB, etc)
Невідповідність визначенню кластерної топології(найкоротший незамкнений шлях)