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

Zarembo Imants () and Uzhga-Rebrov Oleg ()
Additional contact information
Uzhga-Rebrov Oleg: Rezekne Higher Education Institution

Information Technology and Management Science, 2012, vol. 15, issue 1, 26-31

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

Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.2478/v10313-012-0004-9 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:vrs:itmasc:v:15:y:2012:i:1:p:26-31:n:4

DOI: 10.2478/v10313-012-0004-9

Access Statistics for this article

Information Technology and Management Science is currently edited by J. Merkurjevs

More articles in Information Technology and Management Science from Sciendo
Bibliographic data for series maintained by Peter Golla ().