Heuristics

Heuristics are functions $h (n)$ that estimate the cost from a state $n$ to a goal state. They guide informed search algorithms by “preferring” nodes believed to be closer to a goal. Good heuristics often come from solving relaxed versions of the original problem, where constraints are removed so that the solution is easier to compute. Common heuristics for grid problems include Manhattan distance ( $ℓ^{1}$ norm) and Euclidean distance ( $ℓ^{2}$ norm).

Heuristics are crucial because they can dramatically reduce the number of expanded nodes compared to uninformed search, though their effectiveness depends on how well they approximate the true cost.

Properties

(Admissibility) For any node $n$ , $0 \leq h (n) \leq h^{} (n)$ , where $h^{} (n)$ is the actual minimal cost from $n$ to a goal.

(Consistency) A heuristic is consistent if, for every node $n$ , successor $n ’$ , and step cost $c (n, a, n ’)$ , it holds that $h (n) \leq c (n, a, n ’) + h (n ’)$ .

Project Alexandria

Explorer

4.1.4. Heuristics

Properties

(Admissibility) For any node $n$ , $0 \leq h (n) \leq h^{} (n)$ , where $h^{} (n)$ is the actual minimal cost from $n$ to a goal.

(Consistency) A heuristic is consistent if, for every node $n$ , successor $n ’$ , and step cost $c (n, a, n ’)$ , it holds that $h (n) \leq c (n, a, n ’) + h (n ’)$ .

Graph View

Project Alexandria

Explorer

4.1.4. Heuristics

Properties

(Admissibility) For any node n, 0≤h(n)≤h∗(n), where h∗(n) is the actual minimal cost from n to a goal.

(Consistency) A heuristic is consistent if, for every node n, successor n’, and step cost c(n,a,n’), it holds that h(n)≤c(n,a,n’)+h(n’).

Graph View

(Admissibility) For any node $n$ , $0 \leq h (n) \leq h^{} (n)$ , where $h^{} (n)$ is the actual minimal cost from $n$ to a goal.

(Consistency) A heuristic is consistent if, for every node $n$ , successor $n ’$ , and step cost $c (n, a, n ’)$ , it holds that $h (n) \leq c (n, a, n ’) + h (n ’)$ .