Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    21FE27 Artificial Intelligence - : III Year/V Semester IT

    Uploaded by

    dhurgadevi

    Copyright:

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

    21FE27 Artificial Intelligence - : III Year/V Semester IT

    Uploaded by

    dhurgadevi
    4 views15 pages

    Original Title

    2.1.2

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    4 views15 pages

    21FE27 Artificial Intelligence - : III Year/V Semester IT

    Uploaded by

    dhurgadevi

    Copyright:

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

    21FE27

    ARTIFICIAL INTELLIGENCE

    III YEAR/V SEMESTER - IT


    Module-2 Outline
    2.1 Problem solving by searching
    2.1.1. Problem solving agents and Example problems
    2.1.2. Searching for Solutions
    2.1.3. Uninformed search strategies
    2.1.4. Informed (heuristics search strategies
    2.1.5. Heuristics functions
    2.2.Beyond classical search
    2.2.1. Local search algorithms and optimization problems
    2.2.2. Searching with partial observations
    2.2.3. online search agents and unknown environments
    2.3 Adversial search
    2.3.1. Games
    2.3.2. optimal decisions in games
    2.3.3. Alpha-beta pruning
    2.4. Constraint satisfaction problems
    2.4.1. Backtracking search
    2.4.2. Local search for constraint satisfaction problems .
    Searching for solutions
    • Finding out a solution is done by
    – searching through the state space
    • All problems are transformed
    – as a search tree
    – generated by the initial state and
    successor function
    Search tree
    • Initial state
    – The root of the search tree is a search node
    • Expanding
    – applying successor function to the current state
    – thereby generating a new set of states
    • leaf nodes
    – the states having no successors
    Fringe : Set of search nodes that have not been
    expanded yet.
    • Refer to next figure
    Tree search example
    Tree search example
    Search tree
    • The essence of searching
    – in case the first choice is not correct
    – choosing one option and keep others for later
    inspection
    • Hence we have the search strategy
    – which determines the choice of which state to
    expand
    – good choice  fewer work  faster
    • Important:
    – state space ≠ search tree
    Search tree
    • State space
    – has unique states {A, B}
    – while a search tree may have cyclic paths: A-
    B-A-B-A-B- …
    • A good search strategy should avoid such
    paths
    Search tree
    • A node is having five components:
    – STATE: which state it is in the state space
    – PARENT-NODE: from which node it is generated
    – ACTION: which action applied to its parent-node
    to generate it
    – PATH-COST: the cost, g(n), from initial state to
    the node n itself
    – DEPTH: number of steps along the path from the
    initial state
    Measuring problem-solving performance
    • The evaluation of a search strategy
    – 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?
    – Time complexity:
    • how long does it take to find a solution?
    – Space complexity:
    • how much memory is needed to perform the search?
    Measuring problem-solving performance
    • In AI, complexity is expressed in
    – b, branching factor, maximum number of
    successors of any node
    – d, the depth of the shallowest goal node.
    (depth of the least-cost solution)
    – m, the maximum length of any path in the state
    space
    • Time and Space is measured in
    – number of nodes generated during the search
    – maximum number of nodes stored in memory
    Measuring problem-solving performance

    • For effectiveness of a search algorithm


    – we can just consider the total cost
    – The total cost = path cost (g) of the solution
    found + search cost
    • search cost = time necessary to find the solution
    • Tradeoff:
    – (long time, optimal solution with least g)
    – vs. (shorter time, solution with slightly larger
    path cost g)
    Test your skills
    Find the following nodes using graph
    •Root Node
    •Parent Node
    •Leaf Node
    Next Session…
    2.1.3. Uninformed search strategies

    You might also like