Abstract | ||
---|---|---|
We study a simple, general framework for search called bootstrap search, which is defined as global search using only a local search procedure along with some memory for learning intermediate subgoals. We present a simple algorithm for bootstrap search, and provide some initial theory on its performance. In our theoretical analysis, we develop a random digraph problem model and use it to make some performance predictions and comparisons. We also use it to provide some techniques for approximating the optimal resource bound on the local search to achieve the best global search. We validate our theoretical results with empirical demonstration on the 15-puzzle. We show how to reduce the cost of a global search by 2 orders of magnitude using bootstrap search. We also demonstrate a natural but not widely recognized connection between search costs and the lognormal distribution. |
Year | Venue | Keywords |
---|---|---|
1995 | IJCAI | bootstrap search,performance prediction,theoretical result,local search procedure,search cost,empirical demonstration,theoretical analysis,global search,simple algorithm,local search,lognormal distribution |
Field | DocType | ISSN |
Data mining,Incremental heuristic search,Search algorithm,Guided Local Search,Computer science,Artificial intelligence,Iterative deepening depth-first search,Mathematical optimization,Beam search,Local search (optimization),Combinatorial search,Best-first search,Machine learning | Conference | 1045-0823 |
ISBN | Citations | PageRank |
1-55860-363-8 | 0 | 0.34 |
References | Authors | |
5 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pang C. Chen | 1 | 85 | 20.60 |