Parallel bidirectional heuristic search with dynamic process re-direction

Author

Toptsis, Anestis A.

Author_Institution

Dept. of Comput. Sci. & Math., York Univ., UK

fYear

1994

fDate

26-29 Apr 1994

Firstpage

242

Lastpage

247

Abstract

Non-wave shaping parallel bidirectional heuristic search algorithms have been reported to suffer of the bidirectional search anomaly. Although wave-shaping is considered as the most natural approach, parallel bidirectional wave-shaping algorithms are extremely scarce. We introduce a wave-shaping algorithm for parallel bidirectional heuristic search in distributed memory environments. The method is inspired by the celebrated uniprocessor bidirectional wave-shaping algorithm of DeChampeaux-Sint (1977). Our performance evaluation shows that the proposed method scales well, maintains good performance for increasing problem sizes, and attains close to linear speedup over the sequential DeChampeaux-Sint algorithm

Keywords

heuristic programming; parallel algorithms; search problems; DeChampeaux-Sint algorithm; bidirectional search anomaly; distributed memory environments; dynamic process redirection; parallel bidirectional heuristic search algorithms; wave-shaping; Artificial intelligence; Computer science; Costs; Educational institutions; Heuristic algorithms; Joining processes; Mathematics; Parallel processing;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1994. Proceedings., Eighth International

Conference_Location

Cancun

Print_ISBN

0-8186-5602-6

Type

conf

DOI

10.1109/IPPS.1994.288294

Filename

288294