Я пишу моделирование курьеров/логистики на картах OpenStreetMap и понял, что основной алгоритм A *, как показано на рисунке ниже, не будет достаточно быстрым для больших карт (например, Большой Лондон).
Зеленые узлы соответствуют тем, которые были помещены в очередь открытого набора/приоритета, и из-за огромного количества (вся карта составляет примерно 1-2 миллиона), для поиска нарисованного маршрута требуется около 5 секунд. К сожалению, 100 мс на маршрут - мой абсолютный предел.
В настоящее время узлы хранятся как в списке смежности, так и в пространственном массиве 2D 100x100.
Я ищу методы, где я могу обменять время предварительной обработки, пространство и, если нужно, оптимальность маршрута, для более быстрых запросов. Прямая формула Хаверсина для эвристических затрат является самой дорогой функцией в соответствии с профилировщиком - я максимально оптимизировал свой основной A *.
Например, я думал, если бы я выбрал произвольный node X из каждого квадранта 2D-массива и запустил A * между каждым, я могу сохранить маршруты на диск для последующих симуляций. При запросе я могу запустить поиск A * только в квадрантах, чтобы пройти между предварительно вычисленным маршрутом и X.
Есть ли более совершенная версия того, что я описал выше, или, возможно, другой метод, который я должен преследовать. Большое спасибо!
Для записи здесь приведены некоторые результаты тестов для произвольного взвешивания эвристических затрат и вычисления пути между 10 парами случайно выбранных узлов:
Weight // AvgDist% // Time (ms)
1 1 1461.2
1.05 1 1327.2
1.1 1 900.7
1.2 1.019658848 196.4
1.3 1.027619169 53.6
1.4 1.044714394 33.6
1.5 1.063963413 25.5
1.6 1.071694171 24.1
1.7 1.084093229 24.3
1.8 1.092208509 22
1.9 1.109188175 22.5
2 1.122856792 18.2
2.2 1.131574742 16.9
2.4 1.139104895 15.4
2.6 1.140021962 16
2.8 1.14088128 15.5
3 1.156303676 16
4 1.20256964 13
5 1.19610861 12.9
Удивительно увеличивая коэффициент до 1,1, почти вдвое сократилось время выполнения, сохраняя тот же маршрут.
