Heuristic Search Procedure
Heuristic search uses additional domain specific knowledge in the form of a heuristic function that guides the search process.
The heuristic provides an estimate of how close a state is to the goal and is used to prioritize the exploration of the most promising state first, making the search more efficient.
In heuristic search, the algorithm evaluates states based on both the current path taken and the estimated cost to reach the goal using heuristic.
Evaluation Function
It is a function that evaluates the "cost" or "value" of a given state, guiding the search algorithm to choose the most promising state to explore next.
The evaluation function is often expressed as:
where:
-
\(g(n) \rightarrow\) actual cost; this represents the total cost to reach the current state
nfrom the start state (often called path cost) -
\(h(n) \rightarrow\) heuristic estimate of the cost from the current state
nto the goal state. -
\(f(n) \rightarrow\) total estimated cost reaching the goal through state
n.
Based on the \(f(n)\) value, the algorithm will store or sort the nodes on the OPEN list such that the node having lowest \(f(n)\) value will be expanded first.
Example: Solving 8-Puzzle Problem Using Heuristic Search
In the following example, a heuristic search is used to solve the 8-puzzle problem.
Initial state:
@TODO: add 8-puzzle initial state
Final state:
@TODO: add 8-puzzle final state
Here, let us consider \(h(n) = \) number of misplaced tiles in the database. Let the path cost between each pair of nodes be unity.
@TODO: add 8-puzzle solution diagram using heuristic search
The choice of evaluation function critically determines the search results. The use of an evaluation function that fails to recognize the true promise of some nodes can result in non-minimal cost paths, whereas use of an evaluation function that overestimates the promise of all nodes results in the expansion of too many nodes.