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.