SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE
A uninformed search strategy that expands the the node with the lowest path cost first. The frontier is implemented as a priority queue ordered by path cost and the goal test is applied to a node when it is selected for expansion. It is complete and optimal.
UNIFORM-COST SEARCH ALGORITHM
node ← create node with STATE = problem.INITIAL-STATE, PATH-COST = 0, DEPTH = 0 frontier ← create priority queue ordered by PATH-COST frontier.INSERT(node) closed-list ← create empty set WHILE NOT (frontier.EMPTY) node ← frontier.POP() IF problem.GOAL-TEST(node.STATE) THEN return node as solution closed-list.ADD(node.STATE) // NODE EXPANSION FOR EACH operator IN problem.LEGAL-OPERATORS(node.STATE) successor ← problem.APPLY(operator, node.STATE) IF NOT successor in closed-list THEN // NODE GENERATION child ← create node with STATE = successor, PARENT = node, ACTION = action represented by operator, PATH-COST = node.PATH-COST + problem.COST(ACTION, node.STATE) DEPTH = node.DEPTH + 1 IF NOT successor in frontier THEN frontier.INSERT(child) ELSE IF successor in frontier with higher PATH-COST frontier.REMOVE(node with STATE == successor) frontier.INSERT(child) END END return failure
UNINFORMED SEARCH STRATEGY
A systematic search strategy that applies operators to nodes without using any special knowledge about the problem domain (other than the problem formulation). Exponential-complexity search problems cannot be solved by uninformed strategies for any but the smallest instances.