Increasing search efficiency using multiple heuristics (Q1119028): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Search Algorithms Under Different Kinds of Heuristics—A Comparative Study / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized best-first search strategies and the optimality of A* / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3856120 / rank | |||
Normal rank |
Latest revision as of 15:00, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Increasing search efficiency using multiple heuristics |
scientific article |
Statements
Increasing search efficiency using multiple heuristics (English)
0 references
1989
0 references
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.
0 references
artificial intelligence
0 references
search algorithms
0 references
heuristic evaluation functions
0 references