Algorithms/Search Types
Jump to navigation
Jump to search
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().
- Space is O().
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().
- 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 ().
- Technically, DFS can be considered a DLS problem, but with =∞.
Evaluation:
- Complete only if goal is within depth.
- Similar to DFS, is often not optimal.
- Time is O().
- Space is O(b * ).
Iterative Deepening Search (IDS)
- Combines the benefits of BFS and DFS.
- Finds the "best depth limit" by gradually increasing depth.
- Ex: =1, then =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() (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.