Persistent A*: uma melhoria do algoritmo A* usando Árvore de Segmento Persistente e Hashing incremental

Abstract

State space search is a method used to solve several computational problems applied in several areas of computing, especially in Artificial Intelligence. One of the most studied algorithms in this area is A*. Such search algorithm uses heuristic information to perform a better exploration of the search space. However, A* has a memory limitation when it addresses problems whose search state representation is large. To circumvent this problem, this work presents the Persistent A*, whose purpose is to reduce the memory and time complexity of the classic A* implementation. This was possible using the incremental hashing technique and the data structure called persistent segment tree. To validate the implementation, tests were performed using several instances of the problem (N 2 −1) - Puzzle. Finally, we made a comparison between some algorithms in the literature.