Home » Machine Learning/Artificial Intelligence

# Solving problem by searching in Artificial Intelligence

In this article, we will study the **searching approach of an agent to find a solution to the problem**. We will also learn about the **various search techniques used**.

Submitted by Monika Sharma, on May 29, 2019

Whenever the agent is confronted by a problem, its first action is seeking a solution is its knowledge system. This is known as the search for the solution in the knowledge base. Another attempt can be to search for a solution by going into different states. The search of the agent stops in the state when the agent reaches the goal state.

There are many approaches for searching a particular goal state from all the states that the agent can be in.

There are many search algorithms which are followed by an agent for **solving the problems by searching**. Some of them are:

**Random search:**

In this search technique, an agent just keeps checking any random state for being it the goal state. This is not an effective way to search the solution because, in this search, each node can be searched again and again, there is no fixed path followed, problems like infinite searching can be faced.**Breadth-first search (BFS):**

In this type of search, the agent considers every state as a node of a tree data structure. It first checks the current node and then evaluates all the neighboring nodes. After all the neighboring nodes are checked, it moves towards the next set of neighboring nodes for any of the neighbor nodes, and this process continues until the search is ended. In BFS, the nodes of the tree are traversed level after level.**Depth-first search (DFS):**

In the DFS, the search first begins from the root node and first one of the child node’s sub-tree is completely traversed. That is, first all the one-sided nodes are checked, and then the other sided nodes are checked.**Best First Search (Heuristic Search):**

In the best first search, which is also known as the heuristic search, the agent picks up the best node based upon the heuristic value irrespective of where the node is.**A* search:**

It is one of the best and popular techniques used in pathfinding and graph traversals. It decides the node to be traversed on the basis of an f-score which is calculated according to some norms and the node with the highest f-score gets traversed. Here, the f-score is calculated on the basis of misplaced events and number of nodes which needs to be moved to in order to replace the nodes.

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