Алгоритмы обхода графов: различия в производительности
Перевод моей статьи с HackerNoon.
В моем последнем посте я показал способ унификации самых известных алгоритмов обхода графов. Теперь давайте сделаем это более наглядно и рассмотрим различия в производительности.
Предистория
Несколько лет назад Яндекс организовал конкурс Роботы Курьеры с заманчивым призом: билетом на закрытую конференцию по беспилотным технологиям для профессионалов. Конкурс напоминал игру, в которой участникам нужно было находить оптимальные маршруты на карте и оптимизировать доставку с помощью роботизированных курьеров.
Углубляясь в эту тему, я обнаружил, что, несмотря на то, что задача поиска маршрутов уже решена, она продолжает вызывать интерес у профессионального сообщества разработчиков, например, игр. Между 2010 и 2020 годами инженеры сделали значительные оптимизации алгоритма A*, что было особенно полезно для AAA игр с огромными картами. Могу порекомендовать почитать статьи и научные работы из этой сферы.
Однако, требования конкурса Яндекс были разработаны таким образом, чтобы система тестирования могла легко оценивать результаты программ. Поэтому визуализация не играла большой роли, что мне показалось недостаточно интересным.
Я решил разработать небольшое приложение, которое использует известные алгоритмы графов для поиска маршрутов на сетчатой карте, чтобы было интереснее поиграть с результатами и визуально закрепить знания. Для визуализации своих находок я использовал графическую библиотеку SFML. Задание конкурса Яндекс я упомянул только для контекста, так как на самом деле я очень быстро вышел за её рамки, хотя и извлек общие идеи для входных параметров.
Задача
Представьте себе технологически продвинутый и инновационный город, где будущее уже наступило давно. В этом городе большинство заказов доставляются роботами-курьерами, и стало редкостью, когда человек доставляет заказ из кафе. В этой задаче мы приглашаем вас принять участие в поиске оптимальных маршрутов для эффективной доставки заказов.
Представим город как карту размером N × N. Для простоты предположим, что каждый робот занимает ровно одну клетку, и каждая клетка может быть проходимой или непроходимой для роботов. За один шаг робот может переместиться в любом из четырех основных направлений (вверх, вниз, влево или вправо), если целевая клетка свободна.
И я игнорирую остальную часть оригинального задания:
В начале теста вам нужно вывести количество роботов, которых вы хотите использовать для доставки заказов, и их начальные координаты. Создание каждого робота будет стоить Costc рублей.
Далее будет выполнено T итераций симуляции. Одна итерация представляет собой одну виртуальную минуту и состоит из 60 секунд. На каждой итерации ваша программа будет получать количество новых заказов, и в ответ программа должна сообщать, какие действия выполняет каждый робот (60 действий на робота).
За каждый успешно доставленный заказ вы получите max(0, MaxTips - DeliveryTime) долларов чаевых, где MaxTips — максимальное количество чаевых за один заказ, а DeliveryTime — время от момента появления заказа до его доставки в секундах.
Общее количество очков, которое вы заработаете в одном тесте, рассчитывается по формуле TotalTips - R × Costc, где TotalTips — общее количество заработанных чаевых, R — количество использованных роботов, Costc — стоимость создания одного робота. Если вы заработали меньше чаевых, чем потратили на создание роботов, ваши общие очки будут равны 0. Вы также получите 0 очков за тест, если выполните любое неправильное действие.
Входные данные
Программа использует стандартный ввод для чтения параметров. Этот подход позволяет нам задавать тестовые данные различной сложности с использованием входных файлов.
Первая строка ввода содержит три натуральных числа: N (размер карты города), MaxTips (максимальное количество чаевых за заказ) и Costc (стоимость создания одного робота). Я игнорирую параметры MaxTips и Costc для моей первой реализации и, возможно, рассмотрю их в будущем.
После этого каждая из следующих N строк содержит N символов, представляющих карту города. Каждая строка может состоять из двух типов символов:
- '#' - обозначает клетку, занятую препятствием.
- '.' - обозначает свободное пространство.
Далее вам будут предоставлены два натуральных числа: T и D (T ≤ 100 000, D ≤ 10 000 000). T представляет количество итераций взаимодействия, а D — общее количество заказов.
Выходные данные
Ваша задача — визуализировать карту и оптимальные маршруты с использованием библиотеки графики SFML.
Моделирование карт
Карту можно представить в виде сетки ячеек и выполнять поиск пути прямо на сетке без использования каких-либо дополнительных структур данных (и я реализовал это для учебных целей: см. в коде). Однако, чтобы найти оптимальный маршрут с помощью разных алгоритмов поиска, удобнее всё таки представить карту в виде графа, и выполнять поиск маршрута по нему.
В качестве структуры данных для поиска кратчайшего оптимального пути, я предпочёл использовать список смежности ячеек, который легко ложится в алгоритмы BFS, Dijkstra и A-Star. Для таких алгоритмов, как Bellman-Ford, может иметь смысл использовать список ребер вместо списка смежности. Поэтому, если вы посмотрите код, то найдете все эти варианты. Ниже представлена схема классов.
Я создал сущность Navigator, которая отвечает за выполнение поиска пути в соответствии с конфигурацией заказов и задач, заданной через файл App Config и связанные файлы карты.
App Config выглядит так:
```bash
{
"font": "../../data/arial.ttf",
"map": "../../data/maps/test_29_yandex_weighten_real_map",
"shadow": false,
"map_": "../../data/maps/test_08_low_res_simple_map",
"map__": "../../data/maps/test_10",
"map___": "../../data/maps/test_07_partially_blocked_map",
...
```
Обратите внимание, что "map_" (одно подчеркивание), "map__" (два подчеркивания) и т.д. на самом деле не являются свойствами конфигурации. Они игнорируются во время выполнения приложения, где мы считываем только одно доступное свойство "map" согласно схеме класса AppConfig. Поскольку в JSON файле нет возможности комментировать части кода, я использую подчеркивание в имени свойства, чтобы оно оставалось в файле конфигурации, но не использовалось.
Файл карты Map file выглядит так:
```bash
25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20
```
Это один из самых простых примеров, содержащих как заблокированные, так и незаблокированные клетки. Я подготовил множество различных примеров входных параметров и тестовых данных.
Начиная с самых простых, по ходу статьи я буду тестировать их в своем приложении, чтобы постепенно повышать уровень сложности задач.
Кстати, исходный код проекта на GitHub здесь.
Как мы рисуем карты
Итак, карта представлена в виде сетки. Когда карта содержит только ячейки с бинарным состоянием (либо заблокированные, либо незаблокированные), это по сути означает, что любое ребро графа либо существует, либо нет.
Чтобы найти путь в графе, мы должны эффективно его представить. Как в моей предыдущей публикации, я использовал список смежности с отношением Vector[NodeId] -> указывает на -> Vector[Neighbour Nodes]:
typedef std::vector<std::vector<std::shared_ptr<Cell>>> Graph;Интересно, что при исследовании сеток не обязательно использовать графы. Мы можем обходить сетку, используя алгоритмы BFS/DFS, ячейка за ячейкой, не думая о ребрах. См. метод _GetPathByBFSOnGrid.
Пройдемся по коду.
Сначала инициализационный код читает файл и преобразует его в сетку строка за строкой и столбец за столбцом:
```C++
bool RectangularMap::LoadMap(const std::string& filepath, bool shadow)
{
...
// Fill the grid.
_verticesNumber = 0;
for (int row = 0; row < _height; row++)
{
...
for (int col = 0; col < _width; col++)
{
int x = col;
int y = row;
if (line[col] == BLOCK_CELL)
{
// Create a shared pointer here to safely pass pointers between the classes.
_grid[row][col] = std::make_shared<Cell>(x, y, line[col], blockColor, shadow, _scaleFactor);
}
else
{
...
}
}
}
// Make a graph
InitialiseGraph();
...
}
```
Затем создается фактический граф как список смежности:
```C++
void RectangularMap::InitialiseGraph()
{
MapBase::InitialiseGraph();
...
unordered_set<int> visited;
for (int rr = 0; rr < _grid.size(); rr++)
{
for (int cc = 0; cc < _grid[rr].size(); cc++)
{
if (_grid[rr][cc]->GetId() > -1)
{
for (int i = 0; i < 4; i++)
{
int r = rr + dr[i];
int c = cc + dc[i];
if (r >= 0 && c >= 0 && r < _width && c < _height &&
_grid[r][c]->GetId() > -1)
{
if (_isNegativeWeighten)
{
...
}
else
{
_adjacencyList[_grid[rr][cc]->GetId()].push_back(_grid[r][c]);
}
}
}
}
}
}
}
```
Представление сетки полезно для рисования на экране с использованием библиотеки SFML. Мы можем рисовать создавая геометрические объекты:
```C++
...
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
_grid[j][i]->Draw(_window, _scaleFactor);
}
}
...
sf::RectangleShape tile;
tile.setSize(sf::Vector2f(_cellSize - 5, _cellSize - 5));
tile.setPosition(sf::Vector2f(_x * _cellSize, _y * _cellSize));
tile.setFillColor(_color);
window.draw(tile);
```
Или мы можем сделать это эффективно, пиксель за пикселем для больших карт:
```C++
sf::Uint8* pixels = new sf::Uint8[_width * _height * 4];
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
int index = (_grid[j][i]->GetY() * _width + _grid[j][i]->GetX());
sf::Color color = _grid[j][i]->GetColor();
pixels[index * 4] = color.r;
pixels[index * 4 + 1] = color.g;
pixels[index * 4 + 2] = color.b;
pixels[index * 4 + 3] = color.a;
}
}
sf::Texture texture;
texture.create(_width, _height);
texture.update(pixels);
sf::Sprite sprite;
sprite.setTexture(texture);
sprite.setScale(cellSize, cellSize);
_window.draw(sprite);
```
Наконец, давайте посмотрим, как будет выглядеть карта, определенная файлом test_25_xmax.
Исходное состояние карты в файле определено так:
```
..............C.................
..............#.................
.............###................
............#####...............
...........#######..............
..........##1###2##.............
.........###########............
........##3######4###...........
.......###############..........
......#################.........
.....###################........
....#####################.......
.............###................
.............###................
.............###................
```
А карта, отрисованная с помощью SFML, выглядит так:
Так как я хотел, чтобы все это контролировалось пользователем с помощью клавиатуры, почти как в играх, я оставил всю логику поведения пользователя в main.cpp. Было бы приятно называть это "логикой контроллера", хотя по факту это очень-очень упрощенная "каша" :).
Кстати, библиотека SFML делает обработку событий клавиатуры очень простой:
```C++
while (window.isOpen())
{
Event event;
while (window.pollEvent(event))
{
if (event.type == Event::Closed)
window.close();
if (event.type == Event::KeyPressed && event.key.code == Keyboard::Space)
{
... Do what you need here
}
}
}
```
В работе приложения важны следующие вещи:
1. После запуска, пользователь нажатием кнопки ПРОБЕЛ запускает чтение файла карты и ее отрисовку
2. Затем вторым нажатием кнопки ПРОБЕЛ, он загружает задачу маршрутизации и сразу рассчитывает кратчайший путь между двумя точками на карте
Всё просто как палка. В коде это выглядит так:
```C++
...
if (navigator->IsReady())
{
navigator->Navigate(); // Finding route between two points
}
else
{
if (map->IsReady()) // Second SPACE press runs the routing
{
skipReRendering = true;
if (navigator->LoadTasks(filepath))
{
navigator->SetMap(map);
}
}
else // Load and draw map
{
drawLoading(window, font);
if (!map->LoadMap(filepath, shadowed))
{
return 0;
}
drawProcessing(window, font);
}
}
...
```
We need to go deeper
Теперь нам нужно обрабатывать карты с очень гибкой конфигурацией. RectangularMap.cpp содержит много логики, включая все графовые алгоритмы и даже больше, чем нужно (потому что мне нравится экспериментировать, даже если это не особо полезно в данном случае). Заранее прошу прощения за не отполированный код, но целью данной статьи является всё же не красота имплементации, а суть-разница в алгоритмах.
Я реализовал алгоритмы BFS#Line 598, Dijkstra#Line 299, A-Star#Line 356, Bellman-Ford#Line 428 и ряд дополнительных "вспомогательных" алгоритмов, таких как топологическая сортировка и поиск пути из одного источника (Single Sourth Path). Последние два могут быть полезны только в случае направленных ациклических графов, которые я сейчас не использую, но возможно "прикручу" позже.
Из интересного, в коде есть такие функции как фокус, которая позволяет отображать только определенную часть карты. Она меняет фокус, повторно отрисовывая необходимую часть с использованием Observer pattern, когда пользователь нажимает кнопки PgDown или PgUp. С нею можно реализовать функцию "Zoom". Можете взять это как домашнее задание, если вам интересно.
Функция фокуса с картой из файла test_29_yandex_weighten_real_map в действии:
Диаграмма классов выглядит следующим образом:
Запуск
Вы можете провести множество экспериментов, используя готовые файлы входных данных с картами, а также изменять логику в коде.
После запуска вам нужно нажать ПРОБЕЛ, и приложение отобразит карту в соответствии с конфигурационным файлом. Имеет смысл начать исследование с самых простых тестов, постепенно переходя к самым сложным.
Еще раз нажав ПРОБЕЛ, вы запустите алгоритмы маршрутизации, которые найдут путь между начальной точкой и первым ближайшим заказом. Кстати, в коде НЕ реализовано чтение всех остальных заказов, доступных в конфигурационных файлах карты. Вы можете форкнуть репозиторий и сделать это сами :).
Вот маршрут, найденный на карте, определенной файлом test_18_yandex_super_high_res:
Приложение также может находить маршруты на картах существующих городов, таких как Иннополис test_29_yandex_weighten_real_map. Запустив программу вы увидите тонкую голубую линию маршрута.
Именно здесь можно заметить, что поиск эффективных путей между двумя координатами становится сложной задачей для таких алгоритмов, как BFS, но быстро выполняется с помощью A-Star.
Поэтому, чтобы программа не "затупила" на огромном графе, происходит анализ ячеек, найденных в конфигурационных файлах карты, и приложение выбирает как лучше представить карту - как взвешенный или невзвешенный граф, а также какой алгоритм поиска будет наиболее оптимальным. Теперь легко увидеть разницу в производительности между BFS и A-Star:
Заключительные слова
Да, это был один из тех проектов, где от простой идеи до результата довольно тернистый путь. Однако, этот путь интересный (если вы дочитали до этих строк, то вас здесь явно что-то заинтересовало).
На этом я хочу оставить вас наедине с кодом и позволить вам поиграть с этими примерами кода. Надеюсь, вы найдете их увлекательными и многому научитесь.
Ссылки
Комментарии
Отправить комментарий