Home » Machine Learning/Artificial Intelligence

# Best first search in Artificial Intelligence

In this article, we are going to learn about the **Best First search method** used by the Artificial Intelligent agent in solving problems by the search. We will discuss **what the best first search method is** and what is the algorithm followed to implement it in intelligent agents?

Submitted by Monika Sharma, on May 29, 2019

**Best First Search** is another method to solve the problem by searching in an Intelligent Agent. In this search method, the agent simply chooses the best node based on heuristic value irrespective of where the node is. The heuristic value is attained by using the heuristic function which accepts the current state as an input and returns a heuristic value which is an integer value between -10 and +10. The state which has the maximum heuristic value is chosen to be the best state. The goal state always has a heuristic value of +10.

After getting the heuristic value of all the neighboring states, the agent gets the best value by simply sorting all the values in descending order and then simply choosing the first node in the order.

The **best first search** is efficient to use in many manners such as there is no need for the agent to go to each and every state and check for it to be the goal state. The agent can simply jump on to the best node which it gets from the sorted array.

The only drawback of this searching method is that if there are many numbers of neighboring nodes present, then finding all their heuristic values and sorting them and then finding the best node is a lengthy process.

## Algorithm for Best First Search

**Step 1:** Evaluate the initial state. If it is the goal state, then quit and return the node.

**Step 2:** Evaluate the neighboring nodes.

**Step 3:** Loop until all the neighboring nodes or child nodes are explored and store them in an array.

**Step 4:** Sort the array in descending order according to their heuristic value.

**Step 5:** Choose the best node, which is the first node in the array.

**Step 6:** This is our goal state, so quit and return the node.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions