Finding a Path Using Greedy Best-First Search

Last updated

Problem Setup

Scenario:Find a route from the start node S to the goal node G in the given weighted graph. Each node has a heuristic value estimating how close it is to G, while each connection has a travel cost.

Given:A directed graph with S as the start node and G as the goal node. The graph includes heuristic values for every node and edge costs for each available connection. The search trace records the nodes considered at each stage.

Task:Apply Greedy Best-First Search to the graph, trace the node selected at each step, and determine the path reached from S to G along with its total path cost.

Need a quick refresher? Review Greedy Best-First theory

Search Graph

Arrows show the permitted direction of travel, edge labels show travel costs, and the values beside nodes show heuristic estimates of the remaining cost to G. Greedy uses these estimates to select nodes, not the edge costs.

Start Node: S (Heuristic: 10)Goal Node: G (Heuristic: 0)
1
1
1
1
9
2
10
S
7
A
6
C
2
B
4
D
0
G
Want to edit this data in the live solver?

Step-by-Step Resolution

1

Evaluating Node: S

f(S)=h(S)=10f(S) = h(S) = 10
Open List

[ S(10) ]

Closed List

[ ]

Evaluating Neighbors
Evaluated neighbor A (via SA)
h(A)=h(A) = 7
Evaluated neighbor C (via SC)
h(C)=h(C) = 6
2

Evaluating Node: SC

f(C)=h(C)=6f(C) = h(C) = 6
Open List

[ SC(6), SA(7) ]

Closed List

[ S(10) ]

Evaluating Neighbors
Evaluated neighbor D (via SCD)
h(D)=h(D) = 4
3

Evaluating Node: SCD

f(D)=h(D)=4f(D) = h(D) = 4
Open List

[ SCD(4), SA(7) ]

Closed List

[ S(10), SC(6) ]

Evaluating Neighbors
Evaluated neighbor G (via SCDG)
h(G)=h(G) = 0
4

Evaluating Node: SCDG

f(G)=h(G)=0f(G) = h(G) = 0
Open List

[ SCDG(0), SA(7) ]

Closed List

[ S(10), SC(6), SCD(4) ]

Evaluating Neighbors
No valid neighbors to explore.
5

Goal Reached: SCDG

Goal Found
Open List

[ SA(7) ]

Closed List

[ S(10), SC(6), SCD(4), SCDG(0) ]

Final Answer

The search reaches the goal through the following path:

Path reached:S → C → D → G

Total path cost:4

Greedy selects C over A because C has the lower heuristic estimate, then reaches G through D. The resulting route costs 4, compared with 11 through A and B. In this example, the heuristic-driven choice also produces the cheaper route, although Greedy does not guarantee this in general.

Exam Takeaway

  • Select from the entire open list: Greedy chooses the node with the lowest h(n)h(n) among all available candidates, not just the neighbors of the most recently expanded node. Follow the specified tie-breaking rule when heuristic values are equal.
  • Do not use edge costs to rank candidates: Greedy uses f(n)=h(n)f(n)=h(n), so a low heuristic can lead to an expensive route. Edge weights are still needed to calculate the cost of the final path.
  • Finding a route does not prove it is optimal: Greedy stops when the goal is selected, but its heuristic-only decisions do not guarantee the lowest total cost. The route found should not be labelled optimal without separate justification.