What is a heuristic search?

Overview

A Best fit search is an informed search strategy that uses domain knowledge and is a also called Heuristic Search. It follows the greedy method strategy.

What is a heuristic function?

• A Heuristic function is used to evaluate how close the agent is to the goal state. It is represented as $h(n)$.
• Here, $h(n)$ <= $h^*(n)$
  • $h(n)$= Heuristic Cost
  • $h^*(n)$= Estimated Cost

Note: For best fit algorithm, the function is defined as:

• $f(n)$=$h(n)$

Advantages

1. It can use either breadth-first search(BFS) or depth-first search(DFS) for traversal along the node to find the path.
2. It is more efficient than BFS and DFS.

Disadvantages

1. It might get stuck in an infinite loop while switching between the BFS and DFS.
2. It is not optimal because it does not check for all possible nodes.

Algorithm

1. Place the starting node in an open list.
2. If the open list is empty, return to the start node.
3. We’ll place the node with the least value of $h(n)$ in a closed list.
4. Next, we’ll move forward and check for the successors of node n, and put it in the open list.
5. The process is repeated, and nodes are added based on heuristic value to reach goal node. It is then added in a closed list.
6. The process is repeated till the goal node is reached, and the closed list is returned.

Explanation

Open List	Closed List
open[A,B]	close[S]
open[A]	close[S,B]
open[A,E,F]	close[S,B]
open[A,E]	close[S,B,F]
open[A,E,H,I]	close[S,B,F]
open[A,E,H]	close[S,B,F,I]

• Return close [S,B,F,I] it is the required path

Space and Time complexity: O($b^{d}$)

• Where b is branching factor and d is the depth.