The Analysis of Efficiency Dependence of the Shortest Path Finding Algorithms A* and HPA

В реальном мире многие задачи поиска кратчайшего пути требуют нахождения пути между двумя точками в реальном времени. В то время как некоторые алгоритмы поиска кратчайшего пути в одних обстоятельствах работают приемлемо, в других они неприемлемы. А* - универсальный алгоритм, который применяется как для нахождения кратчайшего пути, так и для обхождения графов. HPA* - относительно новый алгоритм, который быстрее и употребляет меньше памяти, чем А* в сравнительно больших статичных решетках, но это преимущество может не применяться к очень маленьким или очень большим решеткам. В статье определяется эффективность алгоритмов А* и HPA*, примененных к двумерным решеткам разных размеров, учитывая такие параметры, как количество уровней иерархии и размеры кластеров. Алгоритмы были реализованы и над ними проведены эксперименты. Чтобы продемонстрировать эффективность алгоритмов в разных обстоятельствах, была проведена серия экспериментов, которая показала преимущество алгоритма HPA* над А*. В использованных двумерных решетках, заполненных препятствиями случайным образом, производительность HPA* была равна А* только в решетке с размером 64х64 узлов при размере кластера 16. Во всех других случаях скорость выполнения HPA* была выше А*. Использование нескольких уровней иерархии в алгоритме HPA* снижало потребляемое время для поиска кратчайшего пути, что особенно хорошо было заметно в решетках большого размера. Увеличение размера кластеров снижает количество пройденных узлов, таким образом, снижая количество используемой памяти. С увеличением количества используемых уровней иерархии HPA* снизилось время выполнения фазы поиска пути в реальном времени и возросло время выполнения предварительной обработки, снижая в результате суммарное время выполнения алгоритма. Преимущество HPA* по сравнению с А* было бы еще больше в случае, когда в статичной решетке нужен многократный поиск пути. Достаточно было бы провести фазу предварительной обработки только один раз, и эти результаты в дальнейшем использовать для всех поисков пути в реальном времени. В то время как для А* понадобилось бы начинать поиски заново каждый раз.