Greedy Best-First Search Theory Guide

Rules & Common Mistakes

• Exam Trap: Never Update Nodes Already in the Open List

  This is the biggest time-saver in a Greedy Search trace and the clearest sign that you understand the algorithm. If a neighbour is already sitting in the `openList`, ignore it completely and move on. Unlike A* or UCS, there is no $g(n)$ to recalculate and no cheaper path to compare. The $h(n)$ value is a fixed property of the node itself — it does not change based on how you arrived there. Attempting to update it wastes time and signals to the examiner that you are mixing up algorithms.
• Exam Trap: Do Not Panic When Greedy Search Hits a Dead End

  When Greedy Search takes the bait and reaches a node with no unvisited neighbours, students often freeze, cross out their work, or try to backtrack manually. Do none of those things. Simply move the dead-end node to the `closedList` as normal and scan the `openList` for the next lowest $h(n)$. The algorithm has not broken — it just hit an expensive corner. The `openList` is still alive, and the trace continues exactly as before from whatever candidate is left.
• Exam Trap: Do Not Stop When the Goal Enters the Open List

  Seeing the goal node appear as a neighbour and get added to the `openList` is just discovery — it means nothing about termination. Greedy Search only stops when the goal node is formally selected as the lowest $h(n)$ entry in the `openList` and moved to the `closedList`. Until that pop happens, a different node with a lower $h(n)$ could still be sitting in the `openList` and would be expanded first. Terminating on discovery is the most common single-point mark loss in a Greedy Search trace.
• Pro Tip: Tied $h(n)$ Values — Break Alphabetically and Keep Moving

  If two nodes in the `openList` share the exact same $h(n)$ score, do not freeze and do not guess randomly. Break the tie alphabetically — select the node whose label comes first in the alphabet. This keeps the trace consistent with standard grading rubrics and makes it straightforward for the examiner to follow the logic. Both choices lead to the same final outcome in terms of path cost, but only one will match the expected answer key.

Strengths, Weaknesses & When To Use It

When to use it:In the real world, Greedy Search gets used when speed matters far more than perfection. Think of basic NPC movement in a video game — the enemy character just needs to start charging toward the player immediately, and a slightly inefficient path is completely acceptable. Pixel-perfect routing would be overkill. On an exam, however, Greedy Search is almost never the right tool for finding a good path. It will be tested specifically so students can watch it fall into a heuristic trap and explain exactly why A* was built to fix the problem.

Greedy Search vs. A* Search

Greedy Search and A* both use a heuristic $h(n)$ to steer the search toward the goal — but they have fundamentally different philosophies about what else matters. A* balances the future estimate $h(n)$ against the real cost of the journey so far $g(n)$, keeping the algorithm honest about expensive detours. Greedy Search strips the past away completely. It is A* with amnesia — same compass, no memory.

• The Formula — Half of A*'s Brain: Greedy Search uses $f(n) = h(n)$, which is exactly half of A*'s formula $f(n) = g(n) + h(n)$. The $g(n)$ term is gone entirely. That single missing variable is the entire reason Greedy Search is fast, reckless, and non-optimal — all at the same time.
• The Mindset — Taking the Bait Every Time: When A* evaluates a node with a tempting low $h(n)$ but a brutal accumulated cost, the $g(n)$ penalty inflates the total $f(n)$ score and pushes that node down the priority queue. Greedy Search cannot see the penalty at all. The tempting node looks just as attractive as a cheap one, and Greedy takes the bait without hesitation every single time.
• The Optimality Guarantee — Night and Day: A* with an admissible heuristic is mathematically guaranteed to find the absolute shortest path. Greedy Search guarantees exactly one thing: it will try to get to the goal quickly. The path it returns could be optimal by coincidence, or it could be four times more expensive than necessary. There is no way to know without checking independently.
• What Your Exam Is Actually Testing: The classic exam setup is to ask for both A* and Greedy traced on the exact same graph. That graph was deliberately designed so Greedy walks into a trap and A* avoids it. If both traces return the same path, double-check the working — the question was almost certainly built so they diverge, and matching results usually means a $g(n)$ calculation was skipped somewhere in the A* trace.

Implementation Pseudocode

// Greedy Search maintains two lists throughout the entire search
// openList  = discovered nodes not yet finalized — sorted purely by h(n), nothing else
// closedList = fully processed nodes — never revisited, never updated
// Notice what is missing: there is no g(n) anywhere in this algorithm

function greedySearch(startNode, goalNode):

    // ── INITIALIZATION ──────────────────────────────────────────────────

    // Read h(n) directly from the heuristic table — no calculation required
    // There is no g(n) to initialize, no f(n) to compute — just one static number
    startNode.h = heuristic(startNode)
    startNode.parent = null

    // Add the start node to the openList as the only initial candidate
    openList  = [startNode]
    closedList = []


    // ── MAIN LOOP ────────────────────────────────────────────────────────

    while openList is not empty:

        // Always pop the node with the lowest h(n) — this is the only metric Greedy trusts
        // No g(n) penalty, no accumulated cost — just the raw heuristic estimate
        current = node in openList with the lowest h(n)
        remove current from openList

        // EXAM TRAP — Goal check happens HERE, after popping, not when generating neighbours
        // Seeing the goal node appear as a neighbour does NOT terminate the algorithm
        if current == goalNode:
            return reconstruct_path(current)  // trace parent pointers back to start

        // Move current to the closedList — it has been fully processed
        add current to closedList


        // ── EXPAND NEIGHBOURS ───────────────────────────────────────────

        for each neighbour in getNeighbours(current):

            // MASSIVE SHORTCUT — Skip the neighbour if it lives in EITHER list
            // In A* and UCS, you must check if a cheaper g(n) path exists for openList nodes
            // In Greedy Search, h(n) is a fixed property of the node — it never changes
            // A discovered node will never get a better score, so skip it immediately
            if neighbour is in closedList or neighbour is in openList:
                continue

            // Brand new node — read its h(n) from the table and add it to the openList
            // This is the entire 'update' step — one lookup, one insertion, nothing more
            neighbour.h = heuristic(neighbour)
            neighbour.parent = current
            add neighbour to openList

    // openList is empty and goal was never popped — no path exists in this graph
    return failure


// ── INITIAL CALL ─────────────────────────────────────────────────────
// greedySearch(startNode, goalNode)

Time & Space Complexity

Greedy Search Exam Questions Students Always Get Wrong

• Why can't I stop the algorithm the second the Goal node appears in my openList?

  Generating the goal just means it was discovered — not that it is next in line. A different node with a lower $h(n)$ might still be sitting in the `openList`, and Greedy Search must always expand the absolute lowest $h(n)$ first. The algorithm only terminates when the Goal node is formally popped and moved to the `closedList`.

• I found a neighbour that is already sitting in my openList. Should I update its score?

  No — skip it completely and move on. Unlike A*, Greedy Search has no $g(n)$ to recalculate. The $h(n)$ value is a static number pulled directly from the heuristic table and will never change regardless of the path taken to reach it. Attempting to update it wastes exam time and signals to the grader that you are mixing up algorithms.

• All of my current node's neighbours are already in the closedList. Did I make a math error?

  No error was made — Greedy Search just walked into a dead end by chasing a tempting heuristic. Do not panic, do not erase the work, and do not attempt to trace backwards manually. Simply move the dead-end node to the `closedList` as normal and pop the next lowest $h(n)$ from whatever remains in the `openList`.

• Two nodes in the openList have the exact same $h(n)$ score. Which one do I pop first?

  Break the tie alphabetically — pick whichever node comes first in the alphabet. This keeps the trace consistent with standard grading rubrics and makes it straightforward for the examiner to follow the working. Both choices lead to the same final path cost, but only one will match the expected answer key.

• My Greedy Search and A* traces returned the exact same path. Is this normal?

  That is a major red flag — treat it as a sign to double-check the A* working immediately. Exam questions asking for both algorithms on the same graph are almost always designed so Greedy falls into a heuristic trap that A* avoids. If both paths match, a $g(n)$ calculation was almost certainly skipped or miscalculated somewhere in the A* trace.