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, D.S. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:58:51Z | |
| dc.date.available | 2007-05-23T09:58:51Z | |
| dc.date.issued | 1995 | 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*[2], and a generalized version of MREC [15]. 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 O(N) nodes in comparison to O(N log N) nodes generated by IDA*, where N is the number of nodes eligible for generation by A*.<P>2. Experimental tests show that if the heuristic branching factor is low and the node- generation time is high (as in most practical problems), then ITS can provide significant savings in both number of node generations and running time.<P>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 range of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the later case depends on the amount of memory available to it. | en_US |
| dc.format.extent | 1172719 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5623 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1995-35 | en_US |
| dc.subject | algorithms | en_US |
| dc.subject | combinatorics | en_US |
| dc.subject | computational complexity | en_US |
| dc.subject | heuristic search | en_US |
| dc.subject | node generation | en_US |
| dc.subject | pruning | en_US |
| dc.subject | memory bound | en_US |
| dc.subject | Systems Integration Methodology | en_US |
| dc.title | Improving the Efficiency of Limited-Memory Heuristic Search | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1