Increasing search efficiency using multiple heuristics
The authors present an extension called QA(\(\epsilon)\) of the classic heuristic graph search procedure \(A^*\) thoroughly developed and discussed in \textit{N. J. Nilsson}'s ``Principles of artificial intelligence (1982; Zbl 0474.68094). Notations and definitions refer to that presentation. QA(\(\epsilon)\) is designed to be a 2-pass variation of \(A^*\)-combining two heuristics for increasing search efficiency. The first heuristic is an efficient estimate but does not guarantee admissibility. Thus the number of nodes expanded is minimized. The second one is an underestimate and guarantees admissibility. The first pass, performing search using algorithm A with the first heuristic evaluation function f1, yields after termination with path P the intermediate result max\(\{\) f1(n)\(\}\). The second pass, performing search using algorithm \(A^*\) with the second heuristic evaluation function f2, checks each newly generated node bound to be discarded if \(f2(n)>\max \{f1(n)\}\cdot (1+\epsilon)\) with \(\epsilon >\emptyset\) holds. Now they claim that for some suitable choice \(\epsilon^*\) of \(\epsilon\), there exist a minimal cost path P such that \[ \max \{f1(n)\}\leq \min \{\max (f1(n)\}\}\cdot (1+\epsilon^*) \] for all admissible paths \(P'\) and node n element of P. Then \(QA(\epsilon^*)\) provides minimal cost solutions. Hence QA(\(\epsilon)\) performs better than A on the average, in particular for harder problems, though admissibility for arbitrary \(\epsilon\) is not guaranteed. Performance tests on the 8-puzzle problem, presented in the paper, tend to confirm this property.
- scientific article; zbMATH DE number 4162311
- scientific article; zbMATH DE number 168209
- Maximizing over multiple pattern databases speeds up heuristic search
- A unifying approach to heuristic search
- Improving search efficiency using possible subgoals
- Combining Multiple Heuristics
- Heuristic search when time matters
- scientific article; zbMATH DE number 5547847
- Hyper-Heuristics: An Emerging Direction in Modern Search Technology
- Generalized best first search using single and multiple heuristics
- Effective use of memory in iterative deepening search
- Rational deployment of multiple heuristics in optimal state-space search
- A more effective version of algorithm A
- scientific article; zbMATH DE number 4162311 (Why is no real title available?)
- Improving the performance of multidimensional search using fingers
- scientific article; zbMATH DE number 1322819 (Why is no real title available?)
- Inconsistent heuristics in theory and practice
- Heuristically ordered search in state graphs
- Domain-independent dynamic programming
This page was built for publication: Increasing search efficiency using multiple heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119028)