Визуализация алгоритма Йена

1. Визуализация алгоритма Йена

Выполнил студент группы ИКТб-2301
Сырчин Алексей
MMXXV

2. Алктуальность алгоритма

• Алгоритм широко применяется в
навишаторах - поиск оптимального
маршрута в сети дорог
• Определение реберно-независимых
маршрутов - это позволяет повысить
эффективность функционирования
сетей связи за счёт использования
оптимального набора маршрутов

3. Цель работы

• Разработать программу для визуализации алгоритма Йена

4. Задачи

• Реализовать алгоритм Йена
• Обеспечить ввод с помощью матрицы и графа
• Добавить анимацию построения пути
• Привести описание алгоритмов и соответствующих
схем алгоритмов

5. АЛГОРИТМ ЙЕНА

• Шаг 1: найти самый короткий путь
• Шаг 2: создать отклонённые пути
• Шаг 3: выбор из кандидатов
• Шаг 4: повторение

6. Алгоритм Йена

7. Аналоги

• Алгоритм A с итерацией - эффективно комбинирует эвристики
и постепенный обход, но требует правильного выбора
функции оценки для ускорения.
• Алгоритм Лам - использует разбиение графа для обхода всех
путей, более сложен в реализации, но может быть быстрее на
плотных графах.

8. Реализация

• Ввод данных

9. Пример работы

10. Верификация результатов

• Визуализация совпадает с программами-аналогами

11. Заключение

• Была реализована программа для виузализации
работы алгоритма Йена, результаты совпадают с
ожидаемыми

12. Библиографический список

• 1. Алгоритм Йена - Википедия - URL:
https://en.wikipedia.org/wiki/Yen%27s_algorithm Электронный ресурс
• 2. Yen’s Algorithm - GitHub - URL
https://github.com/joaopfg/Yen-s-algorithm-for-k-shortestpath-problem-using-Lawler-smodification - Электронный
ресурс

13. Спасибо за внимание!