Scribd Logo
Upload

Welcome to Scribd!

  • 43 views

    CSE860 - 10 - Uninformed Search Strategies

    Uploaded by

    Aqeel Ahmed
    This document discusses uninformed search techniques in artificial intelligence, including breadth-first search, uniform cost search, depth-first search, depth-limited search, and iterative deepening search. It provides examples of each technique and compares their time and space complexity, showing that breadth-first search has the highest space complexity while depth-first search has the lowest.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CSE860 - 10 - Uninformed Search Strategies

    Uploaded by

    Aqeel Ahmed
    43 views21 pages
    This document discusses uninformed search techniques in artificial intelligence, including breadth-first search, uniform cost search, depth-first search, depth-limited search, and iterative deepening search. It provides examples of each technique and compares their time and space complexity, showing that breadth-first search has the highest space complexity while depth-first search has the lowest.

    Original Description:

    AI lectures

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses uninformed search techniques in artificial intelligence, including breadth-first search, uniform cost search, depth-first search, depth-limited search, and iterative deepening search. It provides examples of each technique and compares their time and space complexity, showing that breadth-first search has the highest space complexity while depth-first search has the lowest.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    43 views21 pages

    CSE860 - 10 - Uninformed Search Strategies

    Uploaded by

    Aqeel Ahmed
    This document discusses uninformed search techniques in artificial intelligence, including breadth-first search, uniform cost search, depth-first search, depth-limited search, and iterative deepening search. It provides examples of each technique and compares their time and space complexity, showing that breadth-first search has the highest space complexity while depth-first search has the lowest.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 21

    CSE 860 Artificial Intelligence

    (Uninformed Search)

    Prof. Dr. Yasar Ayaz


    (Pride of Performance)

    Chairman / Central Project Director


    National Center of Artificial Intelligence (NCAI)
    Pakistan

    Professor & Founding Head


    Department of Robotics & AI
    NUST-SMME
    1
    • Uninformed (or Blind) Search:
    No additional information about states
    beyond that provided in the problem
    definition.
    • Informed (or Heuristic) Search:
    When it is possible to know whether one non-
    goal state is more promising than the other.

    2
    • Root node is expanded first,
    • Then all the successors of the root node are
    expanded next,
    • Then their successors and so on!

    In general, all the nodes at a given depth in the


    search tree are expanded before the nodes at
    the next level.
    3
    4
    • Breadth First search is an instance of the
    general graph search algorithm in which the
    shallowest unexpanded node is chosen for
    expansion.

    → FIFO queue for the frontier.


    → Goal test is applied to nodes upon
    generation rather than upon expansion!

    5
    6
    Number of nodes generated:
    b + b2 + b3 + … + bd = O(bd)

    7
    • Breadth First Search (BFS) is Optimal when all
    step costs are equal because it always expands
    the shallowest unexpanded node.

    • Uniform Cost Search (UCS) expands the node


    n with the lowest path cost g(n).
    → This is done by storing the frontier as a
    priority queue ordered by g.

    8
    9
    Other differences with BFS:
    • Goal test is applied upon expansion of the
    node (as in generic graph search algorithm)
    rather than at the time of generation.

    • A test is added in case a better path is found


    to a node currently on the frontier.

    10
    11
    • Uniform Cost Search is Optimal in general!!

    • Space Complexity:

    O(b1+C*/ε)
    where:
    C* is cost of the optimal solution
    ε is minimum permissible cost of an action.

    12
    • Depth First Search always expands the
    deepest node in the current frontier of the
    search tree.
    • It is also an instance of the Graph Search
    Algorithm but with a LIFO queue (stack) as
    frontier.
    • It is usually implemented using Recursion.

    13
    14
    • Space Complexity: O(bm)
    m: Maximum depth of a node in the search
    tree.
    • If the nodes are discarded after Goal Check,
    then the depth first search requires storage of
    only O(bm) nodes!!
    • At d=16 depth first search requires 156 kB of
    memory space … 7 trillion times less than BFS!

    15
    • Depth Limited Search (DLS) is Depth First
    Search with a limit applied on the depth of the
    tree.

    • Applying a bound l on the maximum depth of


    the tree the space complexity of a depth the
    space complexity is O(bl)

    16
    17
    18
    Number of nodes
    • N(IDS) = d(b) + (d-1)b2+ …. + (1) bd
    If b = 10 and d = 5

    19
    • Space Complexity: O(bd/2)

    20
    • Comparison

    21

    You might also like