SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE

BACKTRACKING SEARCH

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.

BIDIRECTIONAL SEARCH

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

BREADTH-FIRST SEARCH

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