Introduction to Artificial Intelligence - Old Questions
5. Searching is an important part of AI, justify it. Explain any two types of blind search with suitable examples. How can you expand it to informed search?
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.
Blind Search does not use any domain knowledge. This means it does not any information to judge where the solution is likely to lie. E.g. Breadth first search, Depth first search, Uniform cost search etc.
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.
Blind search is extended to informed search by using domain-dependent (heuristic) information in order to search the space more efficiently. It uses the heuristic function h(n) that estimates how close we are to a goal.