recategorized
2,545 views
0 votes
0 votes

Consider following sentences regarding $A^*$, an informed search strategy in Artificial Intelligence (AI).

  1. $A^*$ expands all nodes with $f(n)<C^*$
  2. $A^*$ expands no nodes with $f(n) \geq C^*$
  3. 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?

  1. Both statements a and statement b are true
  2. Both statements a and statement c are true
  3. Both statements b and statement c are true
  4. All the statements a, b and c are true
recategorized

4 Answers

0 votes
0 votes
  • 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’)

  • 3) A* expands no nodes with f(n) /C*. Pruning is selectively removing the branches of a tree that are unwanted

0 votes
0 votes
a. $A∗$  expands all nodes with $f(n)<C∗$  - This statement is true. $A∗$ expands nodes based on the total estimated cost $(f(n))$, and it prioritizes nodes with lower costs. $C∗$ represents the cost of the optimal solution path.

b. $A∗$ expands no nodes with $f(n)>C∗$ - This statement is false. $A∗$ uses an admissible heuristic, and nodes with estimated costs $(f(n))$ higher than the cost of the optimal solution $(C*)$
 ) are not expanded.

c. Pruning is integral to  $A∗$ - This statement is true. $A∗$ employs pruning to avoid exploring paths that are guaranteed to be suboptimal. This is achieved through the use of heuristics that guide the search process efficiently.

So, the correct answer is:

B. Both statements a and statement c are true

Related questions

0 votes
0 votes
2 answers
1