Question

problem 1 (10 points): trace the operation of \\(a^*\\) search (use the tree version, i.e. without using a closed list) applied to the problem of getting to bucharest from lugoj using the straight-line distance heuristic. that is, show the sequence of nodes that the algorithm will consider and the \\(f\\), \\(g\\), and \\(h\\) score for each node. you dont need to draw the graph, just right down a sequence of \\((city, f(city), g(city), h(city))\\) in the order in which the nodes are expanded.

Explanation:

Initialize search from Lugoj

Using the A Search Algorithm, Heuristic Search, and Tree Search* knowledge points

$$
LATEXBLOCK0
$$

Expand Lugoj

Using the A Search Algorithm, Heuristic Search, and Tree Search* knowledge points

$$
LATEXBLOCK1
$$

Expand Mehadia

Using the A Search Algorithm, Heuristic Search, and Tree Search* knowledge points

$$
LATEXBLOCK2
$$

Expand Lugoj (from Mehadia)

Using the A Search Algorithm, Heuristic Search, and Tree Search* knowledge points

$$
LATEXBLOCK3
$$

Expand Drobeta

Using the A Search Algorithm, Heuristic Search, and Tree Search* knowledge points

$$
LATEXBLOCK4
$$

Answer:

The sequence of nodes expanded in the tree-version of \(A^*\) search from Lugoj to Bucharest is:

1. Lugoj: \(f = 244\), \(g = 0\), \(h = 244\)
2. Mehadia: \(f = 311\), \(g = 70\), \(h = 241\)
3. Lugoj: \(f = 384\), \(g = 140\), \(h = 244\)
4. Drobeta: \(f = 387\), \(g = 145\), \(h = 242\)