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

1.

Тема: «Разработка библиотеки методов
для двухкритериальной оптимизации в
задаче поиска кратчайшего пути в графе»
Тарбаева А.В.
Руководитель Емельянов Д.М.
группа: А-06м-22

2.

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

3.

Многокритериальная оптимизация
Многокритериальная оптимизация – поиск наилучшего решения, которое
удовлетворяет нескольким критериям.
Основные подходы:
• свертка критериев;
• метод Парето.

4.

Актуальность
Разрабатываемую программную
реализацию библиотеки методов
можно применять построения
маршрута в модели метро:
• критерий времени
• критерий комфорта
• динамические изменения
критериев во времени

5.

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