Alternative pseudocode for priority queue based graph search (related to Uniform-Cost-Search description - aima3e Figure 3.14)

[ctjoreilly]

The following is an alternative version of priority queue graph search pseudocode as described in the Uniform-Cost-Search description in AIMA3e, based on code developed by Ruediger Lunde (on the aima-java AIMA3e branch):

AIMA4e

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
 node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
 frontier ← a priority queue ordered by PATH-COST, with node as the only element
 explored ← an empty set
 loop do
   repeat
     if EMPTY?(frontier) then return failure
     node ← POP(frontier) /* chooses the lowest-cost node in frontier /
   until node.STATE not in explored / ensures not already visited by lower cost node */
   if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
   add node.STATE to explored
   for each action in problem.ACTIONS(node.STATE) do
     child ← CHILD-NODE(problem,node,action)
     if child.STATE is not in explored then
       frontier ← INSERT(child, frontier)

The advantages of this version over the current one as described in AIMA3e, is that it is no longer necessary to perform the containment and replacement functionality on the frontier (which can be expensive and tricky to implement), i.e.:

AIMA3e fragment

if child.STATE is not in explored or frontier then
  frontier ← INSERT(child,frontier)
else if child.STATE is in frontier with higher PATH-COST then
  replace that frontier node with child

Instead duplicate states are dropped when popped off the frontier if they exist in the explored set. Due to being a priority queue the lower cost node will be processed first. The main perceived disadvantage is that the frontier will be larger during processing in the case where you encounter duplicate states before you explore them.

[norvig]

I think you're right -- This looks like the best way forward, but let me try to implement everything before committing 100% to this.