PNBA*: A Parallel Bidirectional Heuristic Search Algorithm

Luis Henrique Oliveira RiosLuiz Chaimowicz

A* (A-star) is a heuristic search algorithm used in various domains, such as robotics, digital games, DNA alignment, among others. In spite of its large use, A* can be a computationally expensive depending on the characteris- tics of the state space and heuristics used. Aiming at improving its performance, in this paper we propose a parallel implementation of a bidirectional version of A*. Named PNBA* (Parallel New Bidirectional A*) the proposed algorithm combines the benefits of bidirectional search and parallel execution in the de- velopment of an efficient A* based search algorithm. Experiments performed in different domains show that PNBA* is more efficient than the original A* and NBA*, the bidirectional version of A* it is based on.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: