Greedy search is the most basic search, just choose the best option in front of you.
A* algo
Local search
| GBFS | A* |
|---|---|
| h(n) | h(n) + g(n) |
| O(b^m) | O(b^d) |
Admissibility
In the A* algorithm, admissibility refers to the property of the heuristic function used to estimate the cost of reaching the goal from a given state. A heuristic is admissible if it never overestimates the cost to reach the goal from any given state. In other words, the heuristic must be optimistic; it can underestimate the actual cost but should never overestimate it. This property ensures that A* will always find the optimal solution when using an admissible heuristic.
Consistent
Mathematically, for all nodes (n) and (n') where (n') is a neighbor of (n), the following must hold true:
(h(n) \leq c(n, n') + h(n'))