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* 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 a 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’)