Greedy Best-first Search Algorithm

My last post on here was an implementation of Breadth-first Seach. This is the same thing except it takes it one step further by adding what’s known as a heuristic. This is called Greedy Best-first Search and it follows the path that it “thinks” is closer to the goal. It won’t always be 100% right.


(sorry for the music btw. I didn’t realize my computer audio would get recorded to so that’s what i was listening on spotify :sweat_smile: )

3 Likes

To compare Greedy best-first search with Breadth-first search and A* search:

The goal of A* search is to minimize f(n) where f(n) = g(n) + h(n) where g(n) is the cost of the path from the starting node to n and h(n) is a heuristic that is an estimate of the cost from n to the final node.

You can think of Greedy best-first search as minimizing only h(n) and Breadth-first search as minimizing only g(n).

Breadth-first search guarantees a shortest path because the cost from the starting node to the current node is always minimized, and when the current node is the final node that means the cost from the starting node to the final node is minimized.

Greedy best-first search does not guarantee a shortest path because it only seeks to minimize the cost from the current node to the final node, but if at some point it cannot advance it only backtracks to the last point in which an advancement can be made. That’s not to say Greedy best-first search is useless. For maps that aren’t quite maze-like, Greedy best-first search tends to be quite efficient when compared to A* search.

2 Likes