Search code examples
javaalgorithmstackqueuegreedy

Does Greedy Best First Search use a Queue or Stack?

I'm just trying to implement the best first search and I am not sure if there are any LIFO or FIFO properties for this algorithm. If so which one should I use? Do I need to use it?

Solution

  • See http://en.wikipedia.org/wiki/Best-first_search#Algorithm_.5B3.5D for this pseudocode:

    OPEN = [initial state]
while OPEN is not empty or until a goal is found
do
 1. Remove the best node from OPEN, call it n.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. Evaluate each successor, add it to OPEN, and record its parent.
done

    Step 1 says "remove the best node" - this implies the use of a Priority Queue.