город Z(з)

1.

Разработка алгоритма оптимального
маршрута полицейского патруляв городе Z
Вариант 1
Выполинили:
Быков Н., Шабаев Р., Цыренжапов М., Образов Н.

2.

Постановка задачи
Условия задачи:
Граф города Z состоит из 25 районов и улиц (районы - вершины,
улицы - рёбра)
Рёбра односторонние и двухсторонние
У каждого района есть свой коэффицент k (который
пропорционален числу жителей)
У каждой улицы есть свое время проезда t
Требования:
Полицейский должен проехать как минимум один раз по каждой
улице
Полицейский должен посетить каждый район как минимум k раз
Маршрут должен быть минимальным по времени
2

3.

Идея решения
Подходы:
1. Покрытие всех рёбер
• Используем алгоритм поиска эйлерова пути
• Выбор следующего ребра с минимальным временем
2. Минимизация переходов
• Используем алгоритмлгоритм Флойда-Уоршелла для поиска кратчайших
путей
• Предварительный расчёт всех попарных расстояний
3. Учёт посещений вершин
• Дополнительная проверка после покрытия всех рёбер
• Корректирующие переходы для требования k посещений
Town
Z
3

4.

Алгоритм
Этап 1 (подготовка данных):
• Чтение графа из файла
• Построение матрицы смежности
• Расчёт кратчайших путей
Этап 2 (поиск кратчайших путей):
Алгоритм будет дейтсвовать пока есть непройденнные рёбра. Если
есть текущее непройденное рёбро, тело проходит через него,
обновляем время и позицию и убираем индекс поиска. Иначе
алгоритм будет искать ближайшее непройденное ребро и проложит
крачтайший путь до него, после чего обновит счётчики и время
4

5.

Алгоритм
Этап 3 (посещение вершин):
Для всех вершин пока действует
неравентсво v(p) < k(p)
выполняется следующие шаги:
• Происходит поиск
кратчайшего пути до p
• Тело проходит путь до
вершины p
• Обновляется счетчики и
время.
Presentations are
communication tools
that can be used as
demonstrations.
5
Your title here

6.

Реализация
read_graph() - чтение графа из файла
floyd_warshall() - расчёт кратчайших путей
get_path() - восстановление пути по матрице
get_edge_time() - получение времени ребра
calculate_required_visits() - требования по
посещениям
find_balanced_route() - построение итогового
маршрута
6

7.

Тестирование
Тестовый граф, состоящий из 5 районов:
A(k=2), B(k=1), C(k=1), D(k=1), E(k=1)
Улицы:
A -> B: 5 мин (двустороннее)
B -> C: 3 мин (одностороннее)
C -> D: 4 мин (двустороннее)
D -> E: 2 мин (одностороннее)
E -> A: 6 мин (двустороннее)
A -> C: 7 мин (одностороннее)
7

8.

Вывод
Результаты работы:
• Разработан алгоритм построения маршрута патруля с
учётом всех ограничений
• Реализована программа на Python, находащая маршрут
Данный алгоритм будет эффективен в задачах логистики и
маршрутизации
8

9.

Спасибо за внимание
9