Explain Heuristic function with respect to: - What is a heuristic function? How do we calculate the Heuristic function ?

A heuristic function \(h(n)\) estimates the cost of the cheapest path from node \(n\) to a goal; informed searches such as greedy best-first and A* use it to decide which node to expand next.

What it is. It is problem-specific knowledge turned into a number. \(h(\text{goal}) = 0\). Greedy best-first search expands the node with the smallest \(h(n)\); A* uses \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost so far.

How it is calculated (examples)

• Route finding: straight-line (Euclidean) distance from the city to the destination, \(h = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\). The real road can never be shorter than a straight line.
• Grid movement: Manhattan distance \(|x_1 - x_2| + |y_1 - y_2|\).
• 8-puzzle: \(h_1\) = number of misplaced tiles; \(h_2\) = sum of Manhattan distances of each tile from its goal position.

Example (standard 8-puzzle): start 7 2 4 / 5 _ 6 / 8 3 1, goal _ 1 2 / 3 4 5 / 6 7 8. All 8 tiles are out of place, so \(h_1 = 8\). Manhattan distances of tiles 1 to 8 are 3, 1, 2, 2, 2, 3, 3, 2, so \(h_2 = 18\).

General ways to design heuristics: solve a relaxed problem (remove some rules; e.g. letting a tile move anywhere gives \(h_1\), letting it move to any adjacent square gives \(h_2\)); use pattern databases of subproblems; or learn from experience.

Types / properties of heuristics

• Admissible: never overestimates, \(h(n) \le h^*(n)\). A* with an admissible heuristic is optimal (tree search).
• Consistent (monotonic): \(h(n) \le c(n, n') + h(n')\) for every successor \(n'\). Consistent implies admissible; needed for optimal A* graph search.
• Non-admissible: may overestimate; faster but may give non-optimal solutions.
• Dominance: if \(h_2(n) \ge h_1(n)\) for all \(n\) and both are admissible, \(h_2\) dominates and expands fewer nodes (Manhattan beats misplaced tiles).
• Trivial heuristic \(h = 0\): A* becomes uniform cost search.