AI Search Algorithms Notes - 3

Introduction

  • Problem-Solving in AI:
    • Solutions can be viewed as a series of actions that transform the environment.
    • The problem space is modeled as a graph, where finding a solution is equivalent to searching for a path in this graph.
  • Nature of Search:
    • Not all paths lead to solutions; some may lead to dead ends.
    • There can be multiple solutions, each differing in quality.
    • The main task is to identify a sequence of operators that moves from the start state to the goal state.

Types of Search in AI

  • Two main categories of searches:
    • Uninformed (Blind) Search: No additional information is used.
    • Informed (Heuristic) Search: Utilizes problem-specific knowledge to find a solution more efficiently.
  • The chapter focuses on various uninformed search techniques.

Evaluating Search Strategies

  • Completeness: Assesses if the strategy guarantees a solution when one exists.
  • Optimality: Determines whether the solution is the lowest cost possible.
  • Complexity:
    • Time Complexity: Amount of time taken, measured in the number of nodes expanded (worst/average case).
    • Space Complexity: Memory required by the algorithm, measured by the maximum size of the fringe.
  • Big-O Notation: Used to compare algorithms based on the depth of the search tree (d) and the average number of branches (b).

Uninformed Search

  • Definition: General algorithms that perform search in a brute-force manner, without any guidance.
  • Outline of a Basic Search Algorithm:
    1. Initialize: Open = {s}
    2. Fail: If Open is empty, return FAIL.
    3. Select: Choose a state n from Open.
    4. Terminate: If n is a goal, terminate successfully.
    5. Expand: Generate successors of n using operators O and add them to Open.
    6. Loop: Return to step 2.

Improved Search Algorithm

  • Steps:
    1. Initialize: Open = {s}, Closed = {}.
    2. Fail: If Open is empty, return FAIL.
    3. Select: Choose state n from Open and save n in Closed.
    4. Terminate: If n is a goal state, terminate successfully.
    5. Expand: Generate successors of n and add them to Open, checking if they are not in Open or Closed.
    6. Loop: Return to step 2.

Depth First Search (DFS)

  • Mechanics:
    • Explores each branch to its maximum depth before backtracking.
    • Uses a stack (LIFO) for its Open list. Nodes already visited are not re-added.
  • Space Complexity: O(b^m), where m is the maximum depth.
  • Time Complexity: O(b^m) as well, which is exponential in nature.
  • Illustration: Example given with nodes indicating traversal path {1, 2, 3, 5, 7}.

Comments on DFS

  • Completeness: Complete if the graph has no cycles; otherwise, it may get stuck in loops.
  • Disadvantages:
    • Can stumble into long paths before finding shorter solutions.
    • Time complexity can lead to examining every node, inefficient in large trees.
    • Maintains paths to unexplored siblings, keeping memory for alternatives.

Breadth First Search (BFS)

  • Mechanics:
    • Explores all nearby nodes before moving deeper into the tree (FIFO queue).
    • Nodes already in the queue are not visited again.
  • Path Extraction Example: Path found as {1, 2, 3, 4, 7}.

Complexity of BFS

  • Space Complexity: O(b^d).
  • Time Complexity: O(b^d), progressively increases with the depth (d).
    • Example values provided for varying depths illustrating time and space consumption.

Comments on BFS

  • Completeness: Guaranteed to find a solution if one exists.
  • Optimality: Can provide the shortest path solution.

Comparison of DFS and BFS

  • Complete: Both can find a solution if present, but BFS is more reliable in cyclic graphs.
  • Optimal: BFS is optimal; DFS may not be.
  • Time Complexity: Both have O(b^m) and O(b^d) respectively.
    • BFS is effective when target states are closer to the root; suitable for shallow searches.
    • DFS is efficient for deeper searches.