Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Lecture05 Informed Search (Part 1)

    Uploaded by

    Dream Maker
    The document discusses informed search techniques for problem solving including best first search, greedy search, and A* search. It provides examples of using heuristic functions to estimate the cost of reaching the goal state to guide the search in finding optimal solutions more efficiently. A* search is described as a best first search that combines the path cost with an admissible heuristic estimate to find the lowest total cost path to the goal.

    Copyright:

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

    Lecture05 Informed Search (Part 1)

    Uploaded by

    Dream Maker
    9 views26 pages
    The document discusses informed search techniques for problem solving including best first search, greedy search, and A* search. It provides examples of using heuristic functions to estimate the cost of reaching the goal state to guide the search in finding optimal solutions more efficiently. A* search is described as a best first search that combines the path cost with an admissible heuristic estimate to find the lowest total cost path to the goal.

    Original Title

    371942_Lecture05 Informed Search (Part 1)

    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 informed search techniques for problem solving including best first search, greedy search, and A* search. It provides examples of using heuristic functions to estimate the cost of reaching the goal state to guide the search in finding optimal solutions more efficiently. A* search is described as a best first search that combines the path cost with an admissible heuristic estimate to find the lowest total cost path to the goal.

    Copyright:

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

    Lecture05 Informed Search (Part 1)

    Uploaded by

    Dream Maker
    The document discusses informed search techniques for problem solving including best first search, greedy search, and A* search. It provides examples of using heuristic functions to estimate the cost of reaching the goal state to guide the search in finding optimal solutions more efficiently. A* search is described as a best first search that combines the path cost with an admissible heuristic estimate to find the lowest total cost path to the goal.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 26

    TAI2151 – ARTIFICIAL INTELLIGENCE

    FUNDAMENTALS

    LECTURE 5 – SOLVING
    PROBLEMS BY SEARCHING
    (INFORMED SEARCHES)
    PART 1

    Solving Problems By Searching – Informed Searches


    LECTURE OUTLINE

    • Part 1: Best First Search


    • Greedy search
    • A* search
    • Part 2: Heuristic functions

    Solving Problems By Searching – Informed Searches


    INFORMED SEARCH

    • Problems:
    • How to achieve goal?
    • Goal: get a solution, get the best solution
    • How to maximise the utility/profit?
    • Ideally, we want AI to know the knowledge and draw
    conclusion
    • Knowledge: a sequence of action that I took
    • Conclusion: predict the result from the actions

    Solving Problems By Searching – Informed Searches


    INFORMED SEARCH
    • Search strategy that uses problem
    specific knowledge beyond the
    definition of the problem itself
    • To fine a goal with less search
    space (that is informed)
    • Can find solutions more efficiently

    Solving Problems By Searching – Informed Searches


    INFORMED VS UNINFORMED SEARCH

    • Uninformed search:
    • Use only available information in the problem
    • For e.g.:
    • From City A to D: look only the available path from A to D

    • Informed search:
    • Use knowledge specific to a particular problem
    • Interpret the problem and available information
    • Involve reasoning
    • For e.g.:
    • From City A to D: getting the shortest path from A to D, is better than the longest path from A
    to D; or find the path with least traffic jam

    Solving Problems By Searching – Informed Searches


    PROBLEM: FINDING A MINIMUM COST PATH
    • Previously we wanted an arbitrary path to a goal.
    • Now, we want the minimum cost path to a goal G
    • Cost of a path = sum of individual transitions along path
    • How to obtain the path cost? By defining a heuristic function, commonly write as h(n)
    • Heuristics: serving to aid discovery
    • An estimation function that estimates how good a node is
    • “Good”, define based on domain specific information. For e.g.: could be the shortest path in a
    map, number of pieces moved for 8-puzzle
    • Examples of path-cost:
    • Navigation
    • path-cost g(n) = distance to node (n) from start node in miles
    • minimum => minimum time, least fuel, least distance

    • 8-Puzzle
    • path-cost = number of pieces moved
    • minimum => least time to solve the puzzle

    Solving Problems By Searching – Informed Searches


    TERMINOLOGY
    • Agent: AI or someone who try to solve the problem
    • States: configuration of the agent in its environment.
    • Initial state: initial starting state
    • Goal state: solution state
    • Operators/Actions: a kind of (movement) that make within a state
    (choices that can be made within a state)
    • Goal test: way to determine whether a given state is a goal state
    • A machine needs some way to encode whether a state happens to be in
    is the goal state
    • Path Cost: numerical cost associated with a given path
    • Transition Model: returns the state resulting from performing action a
    in state s
    • State space: the set of all states reachable from the initial state by any
    sequence of actions

    Solving Problems By Searching – Informed Searches


    INFORMED SEARCHES

     Best-First Search
    * Greedy Search
    * A* Search

     Heuristic Functions
    * Designing a Heuristic Function

    Solving Problems By Searching – Informed Searches


    BEST FIRST SEARCH

    • A search algorithm that expands the node (from one state


    to another state) that is closest to the goal
    • We use a heuristic function to make estimation (we guess,
    but guess with mathematics, i.e. probability and statistics
    logic rules & facts)

    Solving Problems By Searching – Informed Searches


    Informed search strategy uses problem-specific knowledge

    Solving Problems By Searching – Informed Searches


    GREEDY SEARCHES

     Search algorithm: expands node that is closest


    to the goal

     Estimate through heuristic function (a function


    that calculates an approximate cost (ranks
    alternatives) in search algorithm at each
    branching step based on available information
    to decide which branch to follow)

     Since it is approximate, so not necessary it will


    be the best solution (most optimize)

    Solving Problems By Searching – Informed Searches


    Minimize estimated cost to reach a goal: Greedy search

    Solving Problems By Searching – Informed Searches


    GREEDY SEARCH
    • Let evaluation function h(n) be an estimate of cost from node n
    to goal; this function is often called a heuristic function
    (heuristic means to find or to discover) and is denoted by h(n).
    e.g., hSLD(n) = straight-line distance from n to Bucharest
    • Greedy search expands the node that appears to be closest to
    goal
    • Contrast with uniform-cost search in which lowest cost path
    from start is expanded
    • Greedy search resembles depth-first search since it prefers to
    follows a single path all the way to the goal, but it will backup
    when it hits a dead end. So
    • it is not complete
    • it is not optimal
    • time complexity is O(bm) and space complexity is O(bm)

    Solving Problems By Searching – Informed Searches


    Map of Romania with road distances in km, and straight-line distances to Bucharest.
    Goal: Bucharest
    Initial state: Arad
    States: various cities
    Actions: drive between cities or choose
    Minimizenext
    estimated
    city cost to reach a goal: Greedy Search
    Solution: Sequence of cities to reach
    Bucharest

    Solving Problems By Searching – Informed Searches


    Solving Problems By Searching – Informed Searches
    GREEDY SEARCH - EXAMPLE

    Solving Problems By Searching – Informed Searches


    GREEDY SEARCH – EXAMPLE (CONT.)

    Solving Problems By Searching – Informed Searches


    GREEDY SEARCH – EXAMPLE (CONT.)

    Arad → Sibiu → Fagaras → Bucharest : not optimal (140 + 99 +211 = 450)


    ( 32 kilometer longer than Arad → Sibiu → Rimnicu → Pitesti → Bucharest): Optimal
    (140 + 80 + 97 + 101 = 418)
    Solving Problems By Searching – Informed Searches
    PROPERTIES OF GREEDY SEARCH
    • Complete:
    No:
    • Fails in infinite-depth spaces -- example
    • Spaces with loops (e.g. going from Lasi to Oradea)
    → Complete in finite spaces with repeated state
    checking
    • Optimal:
    No - optimal path goes through Pitesti.
    O(bm): like depth first, but a good heuristic function
    • Time:
    gives dramatic improvement on average
    O(bm): Potentially keeps all nodes in memory
    • Space:

    Let b: Branching factor


    m: Maximum Depth
    Solving Problems By Searching – Informed Searches
    A*- a special Best-first search
    • Goal: find a minimum total cost path
    • Notation:
    – g(n) = cost of current path from start to node n in the search tree.
    – h(n) = estimate of the cheapest cost of a path from n to a goal.
    – evaluation function: f = g + h
    • f(n) estimates the cheapest cost solution path that goes through n.
    – h*(n) is the true cheapest cost from n to a goal.
    – g(n) is the true shortest path from the start s, to n.

    • If the heuristic function, h(n), always underestimate the true cost (h(n)
    is smaller than h*(n)), then A* is guaranteed to find an optimal
    solution.

    Solving Problems By Searching – Informed Searches


    MINIMIZING THE TOTAL PATH COST: A* IDEA

    Solving Problems By Searching – Informed Searches


    A* Search

    Straight-line distance is admissible because the shortest


    path between any two points is a straight line.

    Solving Problems By Searching – Informed Searches


    EXAMPLE – CONT.

    Solving Problems By Searching – Informed Searches


    EXAMPLE – CONT.

    Solving Problems By Searching – Informed Searches


    EXAMPLE – FINALLY…

    Solving Problems By Searching – Informed Searches


    PROPERTIES OF A*
    • Complete: Yes, unless there are infinitely many
    nodes with f  f(G)
    • Optimal: Yes
    • Time: Exponential with path length
    • Space: Potentially keeps all nodes in memory
    (runs out of space before it runs out of time)

    Note, A* is also optimally efficient


    for a given heuristic: That is, no other
    optimal search algorithm is guaranteed to
    open fewer nodes. Let b: Branching factor
    m: Maximum Depth
    Solving Problems By Searching – Informed Searches

    You might also like