Crowdly
Add to Chrome
We have a simplified road map of Romania. Length of each road segment is shown. ...
✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
We have a simplified road map of Romania. Length of each road segment is shown.
Problem: find the path from S (Sibiu) to B (Bucharest).
We will use A* search. We need a heuristic function, for that we can use the distance of each point from the goal Bucharest:
Simulate the steps of the A* search with pen and paper (or a spreadsheet). The following table will help:
| n | g(n) | h(n) | f(n) |
|---|---|---|---|
| S | 0 | 253 | 253 |
Mark down the current node in search tree (n) and the matching path length so far g(n) and heuristic value h(n). In the initial state, Sibiu, the path so far has length 0. h(n) can be taken directly from the table of distances. f(n) = g(n) + h(n).
Then follow the algorithm:
- select the row from the table with lowest f(n) that you haven't used yet. Mark it as "used".
- If on this row the last city is "B" then the row contains the solution and its path length.
- if it's not, find the cities you can move to from the last city. Add a row for each of these neighbor nodes to the table
Table after adding the neighbors of the initial state:
| n | g(n) | h(n) | f(n) |
|---|---|---|---|
| SF | 99 | 176 | 275 |
| SR | 80 | 193 | 273 |
| SO | 151 | 380 | 531 |
| SA | 140 | 366 | 506 |