Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    AI Lec5 ClassNotes

    Uploaded by

    Mariam shahid
    The document discusses several uninformed search strategies including breadth-first search, uniform-cost search, depth-first search, and depth-limited search. Breadth-first search expands the shallowest nodes first using a FIFO queue. Uniform-cost search prioritizes expanding the lowest cost node using a priority queue. Depth-first search uses a LIFO queue to expand the deepest nodes first but may not terminate for infinite search spaces. Depth-limited search addresses this by limiting the depth of exploration.

    Copyright:

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

    AI Lec5 ClassNotes

    Uploaded by

    Mariam shahid
    18 views5 pages
    The document discusses several uninformed search strategies including breadth-first search, uniform-cost search, depth-first search, and depth-limited search. Breadth-first search expands the shallowest nodes first using a FIFO queue. Uniform-cost search prioritizes expanding the lowest cost node using a priority queue. Depth-first search uses a LIFO queue to expand the deepest nodes first but may not terminate for infinite search spaces. Depth-limited search addresses this by limiting the depth of exploration.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses several uninformed search strategies including breadth-first search, uniform-cost search, depth-first search, and depth-limited search. Breadth-first search expands the shallowest nodes first using a FIFO queue. Uniform-cost search prioritizes expanding the lowest cost node using a priority queue. Depth-first search uses a LIFO queue to expand the deepest nodes first but may not terminate for infinite search spaces. Depth-limited search addresses this by limiting the depth of exploration.

    Copyright:

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

    AI Lec5 ClassNotes

    Uploaded by

    Mariam shahid
    The document discusses several uninformed search strategies including breadth-first search, uniform-cost search, depth-first search, and depth-limited search. Breadth-first search expands the shallowest nodes first using a FIFO queue. Uniform-cost search prioritizes expanding the lowest cost node using a priority queue. Depth-first search uses a LIFO queue to expand the deepest nodes first but may not terminate for infinite search spaces. Depth-limited search addresses this by limiting the depth of exploration.

    Copyright:

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

    Uninformed Search

    Monday, November 2, 2020 1:05 PM

    Uninformed search (also called blind search).


    • The term means that the strategies have no additional information about
    states beyond that provided in the problem definition.
    • All they can do is generate successors and distinguish a goal state from a
    non-goal state.
    • All search strategies are distinguished by the order in which nodes are
    expanded.

    Breadth-first search, Uniform-cost search, Depth-first search, Depth-limited


    search, Iterative deepening depth-first search and Bidirectional search

    Breadth-first search is a simple strategy in which the root node is


    expanded first, then all the successors of the root node are expanded
    next, then their successors, and so on.
    Breadth-first search is an instance of the general graph-search algorithm
    in which the shallowest unexpanded node is chosen for expansion. This is
    achieved very simply by using a FIFO queue for the frontier.
    Performance
    • Complete? Yes (if b is finite)
    • Time?
    • Space? (keeps every node in memory)
    • Optimal? Yes (if all nodes have same cost)
    Important Lesson
    1. The memory requirements are a bigger problem for breadth-first search
    than is the execution time.
    2. Exponential-complexity search problems cannot be solved by uninformed
    methods for any but the smallest instances.

    Uniformed-cost Search
    Breadth-First Search find the shallowest goal state, but this may not
    always be the least-cost solution.
    •Uniform-Cost Search modifies the Breadth-First Search strategy by
    always expanding the lowest path cost g(n) node on the fringe.

    AI-Lec5 Page 1
    always expanding the lowest path cost g(n) node on the fringe.
    •Frontier is a priority queue, i.e., new successors are merged into the
    queue sorted by g(n).
    •Can remove successors already on queue w/higher g(n).
    •Saves memory, costs time; another space-time trade-off.

    Performance:
    Complete? Does it always find a solution if one exists?
    •Yes (If b is finite and If step costs ≥ small +ve constant epsilon
    •Optimal? Does it always find a least-cost solution? Yes, if step cost ≥
    small +ve constant epsilon
    •Time Complexity: O(b^ceiling(C*/epsilon) ) ~ O(bC*) where C*is the cost
    of the optimal solution
    •Space Complexity: O(b^ceiling(C*/epsilon) ) ~ O(bC*)where C∗is the cost
    of the optimal solution

    Depth-First Search always expands DEPTH-FIRST the deepest node in the


    current frontier of the search tree.
    • The search proceeds immediately to the deepest level of the search tree,
    where the nodes have no successors.
    • As those nodes are expanded, they are dropped from the frontier, so then
    the search “backs up” to the next deepest node that still has unexplored
    successors.
    • Depth-first search uses a LIFO queue.
    • As an alternative to the GRAPH-SEARCH-style implementation, it is
    common to implement depth-first search with a recursive function that
    calls itself on each of its children in turn.

    Performance
    • Complete? No: fails in infinite-depth spaces, spaces with loops. Modify to
    avoid repeated states along path. Complete in finite spaces
    • Time? O(b^m): terrible if mis much larger than d but if solutions are
    dense, may be much faster than breadth-first
    • Space? O(bm), i.e., linear space!
    • Optimal? No

    Depth-Limited Search: The embarrassing failure of depth-first search in


    infinite state spaces can be alleviated by supplying depth-first search with a
    AI-Lec5 Page 2
    infinite state spaces can be alleviated by supplying depth-first search with a
    predetermined depth limit l. That is, nodes at depth l are treated as if they
    have no successors. This approach is called depth-limited search.
    • Searching is not permitted beyond the depth bound.
    • Works well if we know what is the depth of the solution.
    • If the solution is beneath the depth bound, the search cannot find the goal
    (hence this search algorithm is incomplete).
    Main idea
    Expand node at the deepest level, but limit depth to D.
    Implementation: Enqueue nodes in LIFO (last-in, first-out) order. But limit
    depth to D
    Performance
    •Complete? No, Yes: if there is a goal state at a depth less than D
    •Optimal? No
    •Time Complexity: ( ^ ), where D is the cutoff.
    •Space Complexity: ( ^ ), where D is the cutoff.

    AI-Lec5 Page 3
    AI-Lec5 Page 4
    AI-Lec5 Page 5

    You might also like