A* Search Simulation

CSC-266 · Semester IV · Artificial Intelligence

intermediate30 minAvailable

A* Search

Best-first with f = g + h (Manhattan heuristic), start → goal.

Grid (dark = obstacle)

Open list (1 nodes):

(0,0) g=0 h=8 f=8

1/19

Path cost so far

goal not reached yet

With an admissible heuristic (never overestimating), A* is optimal and complete. It expands the frontier in order of total estimated cost, so the goal, once popped, is guaranteed shortest.

Lab brief

Objective

Simulate A* search on a weighted graph, watch f = g + h decide the expansion order, and verify the returned path is optimal.

Theory & concepts

A* expands the node with the smallest f(n) = g(n) + h(n), where g is the cost already paid and h estimates the remaining cost to the goal. When h never overestimates (admissible), the first goal popped from the frontier is reached by an optimal path.

Rendering diagram…

A* expands nodes by f(n) = g(n) + h(n)

The simulation lets you set the heuristic: the true distance (perfect guidance), a weaker estimate, or a deliberately inadmissible one. Comparing runs shows exactly how heuristic quality changes how many nodes A* must expand.

Heuristic	Property	Effect on A*
True distance	Admissible, consistent	Expands only nodes on the optimal path (best case)
Weak estimate	Admissible but far below truth	Expands many extra nodes
Inadmissible	Overestimates somewhere	Faster, but optimality is not guaranteed

Prerequisites

Lesson: Informed search: greedy and A*
Lesson: Heuristic functions

Instructions

1Load the weighted sample graph with start S and goal G, and the preset heuristic values.
2Step through A* and watch the f-value priority queue update after each expansion.
3Record the nodes expanded and the final path cost.
4Switch the heuristic to a weaker admissible one and compare the node count.
5Enable the inadmissible heuristic and check whether the returned path is still optimal.

Tasks

Trace A* with the true heuristic
List the expansion order and show f = g + h for each expanded node.
Weaken the heuristic
Halve all h values and count the extra nodes A* expands.
Break optimality
Set an inadmissible heuristic that overestimates and observe the suboptimal path.
Explain the guarantee
State why an admissible heuristic guarantees the optimal path.

Self-check

The A* expansion order and f-values match hand computation for the sample graph.
The optimal path is found whenever the heuristic is admissible.
The student identifies when an inadmissible heuristic returns a suboptimal path.
The student explains the trade-off between heuristic strength and search effort.

Environment

weighted graph editorheuristic editorf-value priority queueexpansion step controlpath cost summary