Algorithms/Search Types

The following describes various types of searches using tree data structures.

Terminology

• State - A possible configuration in attempting to solve the problem.
• Initial State - The problem starting state. Represented by the tree root.
• Successor State - Any state reachable by a single action, from the current state.
• Tree Node - A data structure that contains information for a single state, as well as any additional relevant data.
• Expanded Node - A node that has been checked.
• Unexpanded Node - A node that has not been checked.
• Frontier - The set of all "unexpanded nodes" in the tree which can be accessed by a single action from a given expanded node.

Search Evaluation

The following can be used to evaluate a given search algorithm:

• Completeness - Ability to always find a complete solution, if one exists.
• Optimality - Ability to always find the lowest-cost/most-efficient solution, when it does find a solution.
• Time Complexity - Number of nodes generated or expanded. For our purposes, we assume each node takes 1 unit of time to evaluate.
• Space Complexity - The maximum nodes in memory at any given point.

Time/space complexity are often evaluated in terms of:

• Branching Factor (b) - Max number of successors of any node in the tree.
• Depth (d) - The shallowest goal node in the tree.
• Maximum Depth (m) - The deepest branch in the tree. May be ∞.

Uninformed Search Algorithms

Algorithms which only directly use information supplied in the problem definition.

Breadth First Search (BFS)

• Always expands the shallowest unexpanded node first.
• The frontier acts as a "First-In, First-Out" (FIFO) queue.

Evaluation:

• Is complete when b is finite.
• Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.
• Time is O($b^{d}$
• Space is O($b^{d}$

Uniform Cost Search (UCS)

• Similar to BFS, except instead of expanding the shallowest node, it always expands the node with the lowest path-cost factor.
• Stores frontier as a priority queue.
• To avoid infinite loops, all costs should be a positive, non-zero integer.

Evaluation:

• Is complete if the minimum step cost for all nodes is greater than 0.
• Is always optimal.
• If all step costs are equal, then has identical space/time complexity to BFS.
  • Otherwise, has slightly worse space/time complexity than BFS.

Depth First Search (DFS)

• Expands deepest unexpanded node first.
• Stores frontier as a "Last-In, First-Out" (LIFO) stack.

Evaluation:

• Is complete when depth space is finite.
• Often is not optimal.
• Time is O($b^{m}$).
• Space is O(b * m).

Depth-Limited Search (DLS)

• Similar to DFS, but puts an artificial limit on how deep it searches.
  • This allows bypassing issues with infinite-depth trees, such as when there are loops or repeating states.
• Requires setting a predetermined limit ($\ell$).
• Technically, DFS can be considered a DLS problem, but with $\ell$=∞.

Evaluation:

• Complete only if goal is within $\ell$ depth.
• Similar to DFS, is often not optimal.
• Time is O($b^{\ell }$).
• Space is O(b * $\ell$).

Iterative Deepening Search (IDS)

• Combines the benefits of BFS and DFS.
• Finds the "best depth limit" by gradually increasing depth.
  • Ex: $\ell$=1, then $\ell$=2, etc.
• Generally, this is the preferred uninformed search space method, if search space is large and depth of solution is unknown.

Evaluation:

• Complete when branching factor (b) is finite.
• Optimal when all step costs are positive, non-zero integers.
• Time is O($b^{d}$) (same as BFS).
• Space is O(b * d) (same as DFS).

Informed Search Algorithms

Algorithms which make use of some form of "outside" or "domain-specific" knowledge, in addition to base problem description.