Introduction to Artificial Intelligence - Old Questions

5.  Justify that AI can’t exist without searching. Explain in detail about any two types of informed search with practical examples.

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.

Informed search uses 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. The function is used to estimate the cost from  a state n to the closest goal.

Types of Informed Search:

• Greedy Best-first Search
• A* Search

In above given search, nodes are expanded based on the value of evaluation function. Nodes having minimal value of evaluation function are expanded first.

Greedy Best-first Search

• It expands the node that appears to be closest to the goal.
• The evaluation function is defined by    f(n) = h(n)

                Where, h(n) is an estimate of cost from node n to goal node

                            h(n) = 0 for goal node.

A* Search

The evaluation function is defined by    f(n) = g(n) + h(n) 

            Where, g(n) is sum of actual costs incurred while travelling from root node (start node) to node n.

                         h(n) is an estimate of cost from node n to goal node

                         f(n) is estimated total cost of path through n to goal.