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