function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
if problem's initial state is a goal then return empty path to initial state
frontier ← a priority queue ordered by pathCost, with a node for the initial state
reached ← a table of {state: the best path that reached state}; initially empty
solution ← failure
while frontier is not empty and top(frontier) is cheaper than solution do
parent ← pop(frontier)
for child in successors(parent) do
s ← child.state
if s is not in reached or child is a cheaper path than reached[s] then
reached[s] ← child
add child to the frontier
if child is a goal and is cheaper than solution then
solution = child
return solution
Figure 3.11 Uniform-cost search on a graph. Finds optimal paths for problems with vary- ing step costs.
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
if EMPTY?(frontier) then return failure
node ← POP(frontier) /* chooses the lowest-cost node in frontier */
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 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
Figure ?? Uniform-cost search on a graph. The algorithm is identical to the general graph search algorithm in Figure ??, except for the use of a priority queue and the addition of an extra check in case a shorter path to a frontier state is discovered. The data structure for frontier needs to support efficient membership testing, so it should combine the capabilities of a priority queue and a hash table.