Improving the Efficiency of Limited-Memory Heuristic Search
| dc.contributor.author | Ghosh, Subrata | en_US |
| dc.contributor.author | Mahanti, Ambuj | en_US |
| dc.contributor.author | Nau, Dana S. | en_US |
| dc.date.accessioned | 2004-05-31T22:30:34Z | |
| dc.date.available | 2004-05-31T22:30:34Z | |
| dc.date.created | 1995-02 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | This paper describes a new admissible tree search algorithm called Iterative Threshold Search (ITS). ITS can be viewed as a much-simplified version of MA*, and a generalized version of MREC ITS's node selection and retraction (pruning) overhead is much less expensive than MA*'s. We also present the following results: 1. Every node generated by ITS is also generated by IDA*, even if ITS is given no more memory than IDA*. In addition, there are trees on which ITS generates 0(N) nodes in comparison to 0(N log N) nodes generated by IDA*, where N is the number of nodes eligible for generation by A*. 2. Experimental tests show that if the heuristic branching factor is low and the nodegeneration time is high (as in most practical problems), then ITS can provide significant savings in both number of node generations and running time. 3. Our experimental results also suggest that on the Traveling Salesman Problem, both IDA* and ITS are asymptotically optimal on the average if the costs between the cities are drawn from a fixed range. However, if the rake of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the latter case depends on the amount of memory available to it. (Also cross-referenced as UMIACS-TR-95-23) | en_US |
| dc.format.extent | 329223 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/702 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3420 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-95-23 | en_US |
| dc.title | Improving the Efficiency of Limited-Memory Heuristic Search | en_US |
| dc.type | Technical Report | en_US |