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

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.

Toxoid

Answer 1

Ten years after I asked this question, I got back to it and finally understood what that article in Wikipedia was saying.

Greedy BFS is greedy in expanding a potentially better successor of the current node. The difference between the two algorithms is in the loop that handles the evaluation of successors. Best-first search always exhausts the current node's successors by evaluating them and continues with the best one from them:

    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.

Greedy BFS doesn't expand all successors of a node if it finds one that has a better heuristic than the current node. Instead it greedily expands this potentially better node, leaving some of the current node's successors unexpanded. This means the current node shouldn't be removed from the OPEN list unless all its successors have been evaluated. This is the pseudo-code:

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. For each successor do:
   a. If it is not in CLOSED: 
       i. Evaluate it, add it to OPEN, and record its parent
       ii. If it has a better heuristic than n: remove n from CLOSED, add n to OPEN 
           (after the current successor) and break from loop 3.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

I have removed the step 3. Create n's successors. from the BFS code above because some of n's successors may not be evaluated, so there is no use creating them. Instead each successor should be created and immediately evaluated in 3. For each successor do:.

Toxoid

Answer 2

"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.

Johnathon

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).

Fennel

Answer 4

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.

Madrid