B

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 variant of depth-first search where only one successor is generated at a time rather than all successors. Each partially expanded node remembers which successor to generate next. This means less space complexity.
A uninformed search strategy that runs two simultaneous searches: one forward from the initial state and the other backward from the goal. It is implemented by replacing the goal test with a test to see whether the frontiers of the two searches intersect. It can enormously reduce time complexity, but it is not always applicable and may require too much space.
SEE example with fragment of the Travel Through Switzerland problem HERE
See Also:  Frontier, Uninformed Search Strategy
Applications:  desktopUSS
A uninformed search strategy that generates one level of the search tree at a time. The frontier is implemented as a FIFO queue and the goal test is applied when a node is generated. It is complete, optimal if the path cost is a non-decreasing function of the depth of the node, but has exponential space complexity.

BREADTH-FIRST SEARCH ALGORITHM

node ← create node with        
       STATE = problem.INITIAL-STATE, 
       PATH-COST = 0, 
       DEPTH = 0
IF problem.GOAL-TEST(node.STATE) THEN
   return node as solution

frontier ← create FIFO queue
frontier.INSERT(node)
closed-list ← create empty set
WHILE NOT (frontier.EMPTY)     
      node ← frontier.POP()
      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 or frontier 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 problem.GOAL-TEST(child.STATE) THEN
                return child as solution
             frontier.INSERT(child)
      END
END
return failure
SEE example with fragment of the Travel Through Switzerland problem HERE