1. Open set
open contains discovered nodes still waiting to be explored.
const open = new Set([start])Typorithm · hard
A* Search
▷ Interactive algorithm laba-star-searchsearchgraphheuristicweighted-search
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn A* Search
Search Algorithms
A* Search explores weighted graphs by combining known path cost with a heuristic estimate toward the goal.
A* keeps an open set of discovered nodes.
gScore tracks the cost already paid from start to each node.
fScore adds heuristic(node, goal), an estimate of remaining cost.
The algorithm expands the open node with the smallest fScore.
This lesson returns reachability; full path reconstruction can use cameFrom.
Preparing algorithm lab…
01
open stores candidates.
02
gScore is known cost so far.
03
fScore is gScore plus heuristic.
04
Update neighbors only on better paths.
05
Heuristic quality controls efficiency.
function aStarSearch(graph, start, goal, heuristic) {
const open = new Set([start]);
const cameFrom = new Map();
const gScore = new Map([[start, 0]]);
const fScore = new Map([[start, heuristic(start, goal)]]);
while (open.size > 0) {
const current = [...open].reduce((best, node) =>
(fScore.get(node) ?? Infinity) < (fScore.get(best) ?? Infinity) ? node : best
);
if (current === goal) return true;
open.delete(current);
for (const edge of graph[current] ?? []) {
const tentative = (gScore.get(current) ?? Infinity) + edge.cost;
if (tentative < (gScore.get(edge.to) ?? Infinity)) {
cameFrom.set(edge.to, current);
gScore.set(edge.to, tentative);
fScore.set(edge.to, tentative + heuristic(edge.to, goal));
open.add(edge.to);
}
}
}
return false;
}Read the implementation
Connect each part of the code to the concept before you type.
2. gScore
gScore is the known cost from start to a node.
const gScore = new Map([[start, 0]])3. fScore
fScore combines known cost and estimated remaining cost.
const fScore = new Map([[start, heuristic(start, goal)]])4. Best candidate
Choose the open node with the smallest fScore.
const current = [...open].reduce((best, node) =>5. Goal check
Stop when the best candidate is the goal.
if (current === goal) return true6. Tentative cost
Compute the cost of reaching a neighbor through current.
const tentative = (gScore.get(current) ?? Infinity) + edge.cost7. Better path
Only update a neighbor when this path improves its known cost.
if (tentative < (gScore.get(edge.to) ?? Infinity))A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.