Lecture 3 : Uniformed Search Method

Problem Solving: Uninformed Search

• Uninformed search methods are blind or brute force, having no knowledge about the cost from the current state to the goal.
• Heuristic search methods, on the other hand, have access to extra problem-specific information, typically an estimate of the cost of getting from the current to the goal state.

Route Finding Problem

• The route finding problem involves finding a path from an initial node to a goal node.

General Search

• General search involves the following steps:
  • If the current state is a goal state, return the solution.
  • Apply all applicable operators to the current state, generating a new set of states (node expansion).
  • Decide which state to consider next, and continue from Step 1.

Terminology

• Fringe or frontier: The collection of generated nodes waiting to be expanded.
• Node expansion: Generating all successor nodes considering the available actions.
• Search strategy: Defines which node is expanded next.
• General search algorithm: Fringe or open list contains generated nodes yet to be expanded, and the explored list or closed list contains expanded nodes.

Search Strategies

• Uninformed (blind or brute force) search strategies:
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Depth-Limited Search (DLS)
  • Iterative Deepening Search (IDS)
  • Uniform Cost Search (UCS)
  • Bidirectional Search (BS)
• Heuristic (informed) search strategies have access to extra problem-specific information.

Uninformed Search Strategies

• Breadth-First Search (BFS):
  • Expands the shallowest nodes on the fringe first.
  • Expand all nodes at depth d before expanding any nodes at depth d+1.
  • Data structure: Convenient to use a queue to implement BFS.
• Mathematical analysis of algorithms:
  • Asymptotic analysis involves finding a parameter that characterizes the size of the input and a measure that reflects the running time of the algorithm.
  • Comparing algorithms involves finding the worst-case time complexity.

Comparing Algorithms

• Asymptotic analysis: t(n) is in O(g(n)) if t(n) ≤ c * g(n) for some c and n0, and for all n > n0.
• Comparing algorithms involves comparing the time complexity, considering only the highest-order term.

Criteria for Evaluating Search Methods

• Time complexity: How long does it take to find a solution?
• Space complexity: How much memory does it need to perform the search?
• Completeness: Is the strategy guaranteed to find a solution when there is one?
• Optimality: Does the strategy find the highest-quality solution when there are several different solutions?

Breadth-First Search (BFS)

• Time complexity: O(b^d), where b is the branching factor and d is the depth of the goal node.
• Space complexity: O(b^d), since each generated node being part of the fringe must be saved in memory.
• Optimality: UCS will find the optimal solution.

Bidirectional Search

• Runs two simultaneous searches: one forward from the initial state and the other backward from the goal state, stopping when the two searches meet.
• Motivation: Reduce the time complexity by searching in both directions simultaneously.
• Time complexity: O(b^(d/2)), where b is the branching factor and d is the depth of the goal node.
• Space complexity: O(b^(d/2)), since each generated node being part of the fringe must be saved in memory.
• Optimality: Bidirectional search can find the optimal solution.
• Additional considerations: Need a way to compute the successors of a node for forward search and the predecessors of a node for backward search.