Consistency (or Monotone) Condition
We say ĥ satisfy the consistency condition if all pair of nodes such as (x, y) satisfy the following condition where y is successor of x,
ĥ(x) - ĥ(y) ≤ c(x, y)
Where c(x, y) is the cost of arc between nodes x and y.
The above condition is also defined as f^ values of the nodes in the search tree are monotonically non-decreasing as we proceed away from the start node.
∴ f^(x) ≥ f^(y) where y is successor of x.
The above condition is also known as monotone condition on f^
Argument for the admissibility of A* under the consistency condition might be,
- The first goal selected will have minimal f^ value.
- Monotonicity of f^: Search expands outward along arcs of increasing f^ values.
- For any goal node n, f^(g) = g^(n).
- Whenever a goal node, n is selected for expansion, we have found an optimal path to that goal node (g^(n) = g(n))
- The algorithm finds an optimal path by selecting first goal node.
