Premium
Parallel search using transformation‐ordering Lterative‐Deepening‐A*
Author(s) -
Cook Diane J.,
Hall Lawrence O.,
Thomas Willard
Publication year - 1993
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.4550080804
Subject(s) - iterative deepening depth first search , computer science , transformation (genetics) , hypercube , bidirectional search , reduction (mathematics) , mathematical optimization , node (physics) , algorithm , search algorithm , parallel computing , incremental heuristic search , beam search , mathematics , biochemistry , chemistry , geometry , structural engineering , engineering , gene
Iterative‐Deepening‐A (IDA*) is an optimal search technique which is useful for large search spaces, because it requires no intermediate state storage. We show how Transformation‐Ordering Iterative‐Deepening‐A* (TOIDA*) improves the performance of IDA* by dynamically modifying the node expansion order based on results from previous cost limits. We then describe a window parallel implementation of TOIDA* on a Hypercube, and present empirical evidence that the parallel implementation dramatically reduces time spent in search. Finally, we analyze the best and worst case results of sequential and parallel TOIDA*, and compare the results with those of standard IDA* search. Empirical and analytical results show that TOIDA* can provide significant improvements in search speed over IDA* with no penalty in storage requirements, and parallel TOIDA* offers substantial cost reduction over sequential TOIDA*, though at the cost of optimality. © 1993 John Wiley & Sons, Inc.