SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE

UNIFORM-COST SEARCH

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.