Informed Search - Greedy Search

The greedy algorithm uses a so-called $h$ value as an evaluation function ($h$ from heuristic). The $h(n)$ for a node $n$ is the estimated cost from $n$ to a goal node. Greedy best-first search algorithm tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly.

• Completeness: Yes, if the search space is finite (m is finite)
• Optimality: No, recall the greedy algorithm that it always finds a local optimal path which might not be global optimal solution

Pseudocode

GreedyBestFirstSearch(Graph, start, goal):
    1. Create a priority queue (min-heap) named fringe and add (start, h(start))
    2. Create an empty set named visited to track explored nodes
    3. While the fringe is not empty:
        a. Dequeue the node with the lowest heuristic value h(n) (current)
        b. If current is the goal, return the path
        c. If current is not in visited:
            i. Add current to visited set
            ii. For each neighbor (next) of current:
                - If next is not in visited:
                    - Add (next, h(next)) to the priority queue
    4. If the goal is not found, return failure

Time complexity

$O(b^m)$ But a good heuristic can give dramatic improvement.

Space complexity

$O(b^m)$ Keeps every node in the memory.

---

Back to parent page: Problem Solving and Search

AI AI_Algorithm Problem_Solving Informed_Search Greedy