• Both Depth-first search (DFS) and Breadth-first searches (BFS) are oblivious to the goal.
• Irrespective of where the goal is in the state space both algorithms set out on the same predetermined trajectories every time.

Heuristic Search

Idea

• Testing the neighbourhood and following the steepest gradient identifies which of the neighbours is the lowest.
• The idea of a heuristic function is that it takes a state or a node as input and computes a number which is an estimate of the distance of that node from the goal.
• Then a search algorithm can pick that node from OPEN which has the lowest heuristic value.
• The heuristic function h(N) is typically a user defined function.
  • in addition to the MoveGen and the GoalTest functions
• Since h(goal) = 0 we are effectively seeking to minimize h(N).

Heuristic Function

• informed search
• goal-directed
• The heuristic function estimates the distance to the goal.
• This estimate, h(n), can be used to decide which node to pick from OPEN.

Best-First Search

<aside> 💡 Best First Search inserts new candidates into OPEN sorted on h(n).

</aside>

OPEN = PRIORITY QUEUE