Introduction to Artificial Intelligence - Old Questions
3. Justify the searching is one of the important part of AI. Explain in detail about depth first search and breadth first search techniques with an example.
Answer
AI is thinking...
AI problems can be readily modeled as state spaces, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space. Using different searching algorithms we can find the best possible solution. So searching is important in AI.
Breadth First Search
It expands the shallowest unexpanded node first. Starting from the root node (initial state) explores all children of the root node, left to right. If no solution is found, expands the first (leftmost) child of the root node, then expands the second node at depth 1 and so on …until a solution is found.
E.g.
Depth First Search
It expands the deepest unexpanded node first.
It expands the root node, then the leftmost child of the root node, then the left most child of that node and so on. Only when the search hits dead end does the search backtrack.
E.g.
