Is the greedy best-first search algorithm differen

Question

Is the greedy best-first search algorithm different from the best-first search algorithm?

The wiki page has a separate paragraph about Greedy BFS but it's a little unclear.

My understanding is that Greedy BFS is just BFS where the "best node from OPEN" in wikipedia's algorithm is a heuristic function one calculates for a node. So implementing this:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

with "best node from OPEN" being a heuristic function estimating how close the node is to the goal, is actually Greedy BFS. Am I right?

EDIT: Comment on Anonymouse's answer:

So essentially a greedy BFS doesn't need an "OPEN list" and should base its decisions only on the current node? Is this algorithm GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.

Answer 1

"Best first" could allow revising the decision, whereas, in a greedy algorithm, the decisions should be final, and not revised.

For example, A*-search is a best-first-search, but it is not greedy.

However, note that these terms are not always used with the same definitions. "Greedy" usually means that the decision is never revised, eventually accepting suboptimal solutions at the benefit of improvements in running time. However, I bet you will find situations where "greedy" is used for the combination of "best first + depth first" as in "try to expand the best next step until we hit a dead end, then return to the previous step and continue with the next best there" (which I would call a "prioritized depth first").

Also, it depends on which level of abstraction you are talking about. A* is not greedy in "building a path". It's fine with keeping a large set of open paths around. It is however greedy in "expanding the search space" towards the true shortest path.

Answer 2

As far as I understand, "best-first search" is only a collective name of a particular search technique in which you use a heuristic evaluation function h(n). So, A* and greedy best-first search are algorithms that fall into this category.

Answer 3

BFS is an instance of tree search and graph search algorithms in which a node is selected for expansion based on the evaluation function f(n) = g(n) + h(n), where g(n) is length of the path from the root to n and h(n) is an estimate of the length of the path from n to the goal node. In a BFS algorithm, the node with the lowest evaluation (i.e. lowest f(n)) is selected for expansion.

Greedy BFS uses the following evaluation function f(n) = h(n), which is just the heuristic function h(n), which estimates the closeness of n to the goal. Hence, greedy BFS tries to expand the node that is thought to be closest to the goal, without taking into account previously gathered knowledge (i.e. g(n)).

To summarize, the main difference between these (similar) search methods is the evaluation function.

As a side note, the A* algorithm is a best-first search algorithm in which the heuristic function h is an admissible heuristic (i.e. h is always an underestimation of the perfect heuristic function h*, for all n). A* is not a gredy BFS algorithm because its evaluation function is f(n) = g(n) + h(n).