COS3751
Techniques of Artificial Intelligence

Assignment 3 - Q3

Consider the following state graph. The start node is L, with the aim to reach node V. Numbers on the edges indicate the path cost to get from one node to the next. RED numbers (h=8, for example) next to the node indicate the heuristic estimate to get to V.

Perform an A* search on the state space above. The start node is L and the goal node is V. For each step of the algorithm, show:
1. the node that gets expanded
2. the current path
3. the Frontier with f, g and h values

Use the heuristic values and path costs as indicated on the graph.

The first iteration of the algorithm gives:
• Node Expanded: L
• Current Path: L
• Child M: f=10, g=3, h=7
• Child N: f=10, g=2, h=8
• Frontier: M (f=10, g=3, h=7), N (f=10, g=2, h=8)

Figure 1 for Assignment 3 - Q3
Figure 1

Concepts

Sign in to vote on these concepts or add one.