Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    My AI

    Uploaded by

    Pardeep Saini
    The document discusses various search algorithms used in artificial intelligence including breadth-first search, depth-first search, uniform-cost search, iterative deepening search, and A* search. It provides details on how each algorithm prioritizes which nodes to expand and examine in the search tree. Key aspects like completeness, time complexity, space complexity, and optimality are compared for each search strategy.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPSX, PDF, TXT or read online from Scribd

    My AI

    Uploaded by

    Pardeep Saini
    22 views34 pages
    The document discusses various search algorithms used in artificial intelligence including breadth-first search, depth-first search, uniform-cost search, iterative deepening search, and A* search. It provides details on how each algorithm prioritizes which nodes to expand and examine in the search tree. Key aspects like completeness, time complexity, space complexity, and optimality are compared for each search strategy.

    Original Description:

    Original Title

    myAI

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPSX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses various search algorithms used in artificial intelligence including breadth-first search, depth-first search, uniform-cost search, iterative deepening search, and A* search. It provides details on how each algorithm prioritizes which nodes to expand and examine in the search tree. Key aspects like completeness, time complexity, space complexity, and optimality are compared for each search strategy.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPSX, PDF, TXT or read online from Scribd
    Download as ppsx, pdf, or txt
    22 views34 pages

    My AI

    Uploaded by

    Pardeep Saini
    The document discusses various search algorithms used in artificial intelligence including breadth-first search, depth-first search, uniform-cost search, iterative deepening search, and A* search. It provides details on how each algorithm prioritizes which nodes to expand and examine in the search tree. Key aspects like completeness, time complexity, space complexity, and optimality are compared for each search strategy.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPSX, PDF, TXT or read online from Scribd
    Download as ppsx, pdf, or txt
    of 34

    ARTIFICIAL

    INTELLIGENCE
    UNIT -III
    Search:
    Informal and informal
    algorithms of depth 1st
    breadth 1st
    hill climbing
    beat 1st
    search and bound
    game playing
    Mini-max search
    alpha and beta pruning
    forward and backward reasoning
    Search Methods
    Ø State-based Search
    Ø Uninformed (blind) search
    algorithms
    Ø Breadth-First Search (BFS)
    Ø Uniform-Cost Search
    Ø Depth-First Search (DFS)
    Ø Depth-Limited Search
    Ø Iterative Deepening
    Ø Informed search
    Steps for Problem Solving
    Formulate — Search — Execute

    1. Goal formulation
    2. Problem formulation
    3. Search algorithm
    4. Execution
    Single-state problem formulation

    A problem is defined by four items:

    1. initial state
    2. actions or successor function
    3. goal test (explicit or implicit)
    4. path cost (∑ c(x,a,y) – sum of step costs)

    A solution is a sequence of actions leading


    from the initial state to a goal state
    Search Tree Basics
    Offline, simulated exploration of state space by generating successors of already-
    explored states
    Search algorithms have the following basic form:

    do until terminating condition is met


    if chosen node is a goal then return success;
    if no more nodes to consider then return fail;
    select node; {choose a node (leaf) on the tree}
    expand node; {generate successors & add to tree}
    A search strategy is defined by picking the order of node
    expansion

    idea: order the branches under each node so that the “most
    promising” ones are explored first
    Tree search example
    Tree search example
    Click to edit Master text styles
    Second level
    ● Third level

    ● Fourth level

    ● Fifth level
    Tree search example
    Click to edit Master text styles
    Second level
    ● Third level

    ● Fourth level

    ● Fifth level
    Implementation: general tree search
    states vs. nodes
    Ø A state is a (representation of) a physical configuration
    Ø A node is a data structure constituting part of a search tree
    includes state, parent node, action, path cost g(x), depth

    Ø The Expand function creates new nodes,


    filling in the various fields and using
    the SuccessorFn of the problem to create the
    corresponding states.
    Search strategies
    Ø A search strategy is defined by picking the order of node
    expansion

    Ø Strategies are evaluated along the following dimensions:


    Ø completeness: does it always find a solution if one exists?
    Ø time complexity: number of nodes generated
    Ø space complexity: maximum number of nodes in memory
    Ø optimality: does it always find a least-cost solution?

    Ø Time and space complexity are measured in terms of


    Ø b: maximum branching factor of the search tree
    Ø d: depth of the least-cost solution
    Ø m: maximum depth of the state space (may be ∞)
    Uninformed search strategies
    Uninformed search strategies use only the
    information available in the problem
    definition
    Breadth-first search
    Uniform-cost search
    Depth-first search
    Depth-limited search
    Iterative deepening search
    Breadth-first search
    Expand shallowest unexpanded node
    Implementation:
    fringe is a FIFO queue, i.e., new successors
    go at end
    Breadth-first search
    • Expand shallowest unexpanded node
    • Implementation:
    – fringe is a FIFO queue, i.e., new
    successors go at end
    Click to edit Master text styles
    Second level
    ● Third level

    ● Fourth level

    ● Fifth level
    Breadth-first search
    Expand shallowest unexpanded node
    Implementation:
    fringe is a FIFO queue, i.e., new successors
    go at end
    Breadth-first search
    Expand shallowest unexpanded node
    Implementation:
    fringe is a FIFO queue, i.e., new successors
    go at end
    Properties of breadth-first search
    Complete?
    Yes (if b is finite)
    Time?
    1+b+b2+b3+… +bd + b(bd-1) = O(bd+1)
    Space?
    O(bd+1) (keeps every node in memory)
    Optimal?
    Only if cost = 1 per step; not true in general

    Space is the bigger problem


    (more so than time, but time is still a problem)
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Depth-first search
    Expand deepest unexpanded node
    Implementation:
    fringe = LIFO queue, i.e., put successors at front
    Properties of depth-first search
    Complete?
    No: fails in infinite-depth spaces, spaces with loops
    Ø Modify to avoid repeated states along path
    Ø  complete in finite spaces

    Time?
    O(bm): terrible if m is much larger than d
    Ø but if solutions are dense, may be much faster than BFS

    Space?
    Ø O(bm), i.e., linear space!
    Optimal?
    No
    Depth-limited search
    = depth-first search with depth limit d ,
    i.e., nodes at depth d have no successors

    Recursive implementation:
    Example: 8-puzzle
    47 nodes
    generated

    Soluti
    on
    Example: 8-puzzle

    Generated
    and
    Explored
    31 nodes

    Generated
    but
    Not Explored
    4 nodes

    Soluti
    on

    You might also like