function greedyBestFirst(grid: Grid, start: Cell, goal: Cell) {const open = new MinHeap<Cell>([start]);
const seen = new Set([start]), parent = new Map();
while (open.size > 0) {const current = open.pop(); // lowest heuristic, cost so far ignored
if (current === goal) return rebuild(parent, current);
for (const neighbor of neighbors(grid, current)) {if (seen.has(neighbor)) continue;
seen.add(neighbor);
parent.set(neighbor, current);
open.push(neighbor, heuristic(neighbor, goal));
}
}
return null;
}
Start at (12, 1), goal at (5, 42). The open set holds only the start.
Understanding Greedy best-first
The idea
Greedy best-first search ranks the open cells by the heuristic alone, the estimated distance to the goal, and ignores how far each one is from the start. It therefore runs straight at the goal, expanding very few cells when the way is clear.
The price is the path. Because the cost so far is never considered, a cell reached by a long detour is as good as one reached directly, and the path it returns can be much longer than the shortest. It is A* with g dropped: fast, memory-light, and not optimal.
The four stages
Complexity
Versus its siblings
Pseudocode
GREEDY(start, goal)
open ← {start}; seen ← {start}while open not empty
current ← the open cell with the lowest h(current, goal)
if current = goal: return path via parent
for each unseen neighbour of current: mark seen; parent[neighbour] ← current; add to open
When to use
Pitfalls
History
Best-first search with a heuristic goes back to Judea Pearl's 1984 book Heuristics, where greedy best-first is the simplest member of the family and A* the one with the optimality proof. Game programmers rediscover it every time a map is open enough that the detours do not show.