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