Trusted answers to developer questions

Adithya Challa

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.

- 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)$

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

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

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

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
bis branching factor anddis the depth.

RELATED TAGS

algorithm

communitycreator

heuristic

CONTRIBUTOR

Adithya Challa

RELATED COURSES

View all Courses

Keep Exploring

Related Courses