UGC NET CSE | June 2012 | Part 3 | Question: 21

Question

$A^*$ algorithm uses $f’=g+h’$ to estimate the cost of getting from the initial state to the goal state, where $g$ is a measure of cost getting from initial state to the current node and the function $h’$ is an estimate of the cost of getting from the current node to the goal state. To find a path involving the fewest number of steps, we should test,

• A. $g=1$
• B. $g=0$
• C. $h’=0$
• D. $h’=1$

Answer 1

A* algorithm is the most important form of Best first search (greedy search which may move either depth wise or breadth wise as needed to get the best solution also known as OR graph) 

f=g+h'

′=g+h′

 g    is a measure of cost getting from initial state to the current node and the function 

h′

h'  is an estimate of the cost of getting from the current node to the goal state.  

now if we want to find a path involving the fewest number of steps then we set the cost of going from from a node to its successor(i.e.   g ) as a constant usually 1

hence ans is A

Answer 2

In the A* algorithm, the cost function

$f(n)=g(n)+h′(n)$ , where:

$g(n)$ is the actual cost of getting from the initial state to the current node,

$h′(n)$ is an estimate of the cost of getting from the current node to the goal state.
To find a path involving the fewest number of steps, you should minimize the actual cost of getting from the initial state to the current node $(g(n))$. Therefore, in this context, you should test:

B. $g=0$

This implies that you are only considering the estimated cost $h’$ in the evaluation function, favoring paths that have the lowest estimate of the cost of getting from the current node to the goal state.

So, the correct option is B.