Consider following sentences regarding A*, an informed search str
Consider following sentences regarding A*, an informed search strategy in Artificial
Intelligence (AI).
(a) A* expands all nodes with f(n) < C*.
(b) A* expands no nodes with f(n) /C*.
(c) Pruning is integral to A*.
Here, C* is the cost of the optimal solution path.
Which of the following is correct with respect to the above statements ?
A. Both statement (a) and statement (b) are true.
B. Both statement (a) and statement (c) are true.
C. Both statement (b) and statement (c) are true.
D. All the statements (a), (b) and (c) are true.
Please scroll down to see the correct answer and solution guide.
Right Answer is: B
SOLUTION
A* search algorithm finds the shortest path from a node to the goal node. It combines the value of heuristic function h(n) and cost to reach the goal node.
Evaluation is done as : f(n) = g(n) + h(n)
It first goes to the node having the minimum f(n) value. It can be seen as optimal search algorithm.
Some properties of A* search algorithm are mentioned here:
1) A* generates an optimal solution if h(n) is admissible heuristic and search space is a tree. A function is admissible if it never overestimates the cost to reach the goal node.
2) A* generates an optimal solution if h(n) is consistent heuristic and search space is a graph. H(n) is consistent if for every node n and for every successor node n’ :
h(n) <= c(n, n’) + h(n’)
3) A* expands no nodes with f(n) /C* and pruning is integral to A*. Pruning is selectively removing the branches of a tree that are unwanted.