A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm (Q761039)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm |
scientific article |
Statements
A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm (English)
0 references
1984
0 references
The performance of a new heuristic search algorithm is analyzed. The algorithm uses a formal representation (semantic representation) that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of \(A^*\), without requiring a human expert to provide it. The heuristic is computed by solving less constrained subproblems (auxiliary problems) of the given problem. The new algorithm is shown to be less efficient than the Dijkstra algorithm, according to the complexity measure ''number of node expansion.'' This proves that it is not efficient to compute heuristics for \(A^*\) by solving auxiliary problems with backtracking.
0 references
heuristic search algorithm
0 references
semantic representation
0 references
heuristic evaluation function
0 references
0 references