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 CLOSED: evaluate it, add it to OPEN, and record its parent. 

b. Otherwise: change the recorded parent if this new path is better than the 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 the CURRENT node 

2. Add CURRENT to Path [and optionally, 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

In the case of Best First Search, when we are at a node, we can consider any of the adjacent as the next node. It explores paths without considering any cost function. The idea of BFS is to use an evaluation function to decide which adjacent is most promising and then explore. Best First Search falls under the category of Heuristic Search or Informed Search. It allows revising the decision of the algorithm.

And in the case of the greedy algorithm, it builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global solution is the best fit for Greedy. In this algorithm, the decisions are final, and not revised.

Coming to your question, greedy BFS doesn't need an "OPEN list" and should base its decisions only on the current node as it always chooses the next piece that has more benefits. Hence, greedy BFS tries to expand the node that is thought to be closest to the goal, without taking into account previously gathered knowledge.

Your algorithm is missing some steps, you can refer to the following algorithm:

• Set START as the CURRENT node 

• Add the start node as the head. The priority does not matter since we remove it anyway.

• Now search the node that we have already searched for adding to another position. 

• Insert the start node into the HashSet.

• Repeat till we have no element in the queue left.

• Add CURRENT to Path [and optionally, to CLOSED?] 

• If CURRENT is GOAL, exit 

• Evaluate CURRENT's successors 

• Set BEST successor as CURRENT and go to 2.

Interested in learning Artificial Intelligence? Click to learn more Artificial Intelligence Online Course!