Paper
1 March 1992 SIMD approach to IDA* search
Gary Lyons, Dianne J. Cook
Author Affiliations +
Abstract
Heuristic search is a fundamental component of artificial intelligence applications. Because search routines are frequently a computational bottleneck, numerous methods have been explored to increase the efficiency of search. While sequential search methods use exponential amounts of storage and yield exponential run times, parallel algorithms designed for MIMD machines significantly reduce the time spent in search. In this paper, we present a massively- parallel SIMD approach to search named MIDA* search. The components of MIDA* include a very fast distribution algorithm which biases the search to one side of the tree, and an incrementally-deepening depth-first search of all the processors in parallel. We show the results of applying MIDA* to instances of the fifteen puzzle problem. Results reveal an efficiency of 76% and a speedup of 8553% and 492% over serial and 16- processor MIMD algorithms, respectively.
© (1992) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Gary Lyons and Dianne J. Cook "SIMD approach to IDA* search", Proc. SPIE 1707, Applications of Artificial Intelligence X: Knowledge-Based Systems, (1 March 1992); https://doi.org/10.1117/12.56879
Lens.org Logo
CITATIONS
Cited by 1 scholarly publication.
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Evolutionary algorithms

Artificial intelligence

Intelligence systems

Algorithm development

Parallel computing

Sun

Transform theory

RELATED CONTENT


Back to Top