AI Sample Question for DS-AI

Question

Imagine you are guiding a robot through a grid-based maze using the A* algorithm.  The robot is currently at node A (start) and wants to reach node B (goal). The heuristic function $h(n)$ is the Euclidean distance between a node and the goal. The cost function $g(n)$ is the cumulative cost to reach a particular node. Now, let's calculate the A* values for some nodes:

Node C: $g(C) = 10$, $h(C) = 8$

Node D: $g(D) = 5$, $h(D) = 12$

Node E: $g(E) = 12$, $h(E) = 6$

Which node should the algorithm explore next based on the A* calculation?

 A) Node C

B) Node D

C) Node E

D) Not enough information to decide

Answer 1

The A* algorithm selects the node with the minimum value of \(f(n) = g(n) + h(n)\) to explore next. Let's calculate \(f(n)\) for each node: Node C: $f(C) = 10 + 8 = 18$

Node D: $f(D) = 5 + 12 = 17$

Node E: $f(E) = 12 + 6 = 18$

The algorithm should explore Node D next, as it has the minimum \(f(n)\) value. Therefore, the correct answer is:

B) Node D