U

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
SEE ALSO:  Frontier, Uninformed Search Strategy
APPLICATIONS:  desktopUSS
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.
SEE ALSO:  Problem Formulation, Search, Systematic Search
APPLICATIONS:  desktopUSS