State-Space Search, Problem Reduction, and Iterative Deepening: A Comparative Analysis
| dc.contributor.author | Nau, D.S. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:53:53Z | |
| dc.date.available | 2007-05-23T09:53:53Z | |
| dc.date.issued | 1993 | en_US |
| dc.description.abstract | In previous work, Korf showed that by introducing one problem- reduction step into a state- space search, one could reduce the number of node generations from 0 ((2b)2d ) to 0 (bd ), where b and d are the branching factor and search depth. My results are as follows: 1. The 0(bd) bound is tight, but the 0((bd)2d ) bound is not: the A* procedure does only Q(b2d ) node generations. Thus, the improvement produced by one problem- reduction step is not always as great as the previous results might suggest.<P>2. In an AND/OR tree where multiple problem- reduction steps are possible, problem reduction produces a much more dramatic improvement: both the time complexity and the space complexity decrease from doubly exponential to singly exponential.<P>3. For iterative-deepening procedures like IDA* that only remember the nodes on the current path, the space complexity decreases but the time complexity increases - by exponential amounts in Korf's model, and doubly exponential amounts in the AND/OR-tree model. This is true even for IDAO*, a new procedure that improves IDA*'s performance by combining it with problem reduction.<P>These results lead to the following conclusions: In general, problem reduction can save huge amounts of both time and space.<P> Whether to use a procedure that remembers every node it has visited, or instead use a limited-memory iterative-deepening procedure, depends on whether the primary objective is to save space or save time.<P> | en_US |
| dc.format.extent | 793696 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5383 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1993-38 | en_US |
| dc.subject | algorithms | en_US |
| dc.subject | computational complexity | en_US |
| dc.subject | path planning | en_US |
| dc.subject | Systems Integration | en_US |
| dc.title | State-Space Search, Problem Reduction, and Iterative Deepening: A Comparative Analysis | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1