Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Problem Solving Mod 3

    Uploaded by

    Shankar Paikira

    Copyright:

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

    Problem Solving Mod 3

    Uploaded by

    Shankar Paikira
    4 views9 pages

    Original Title

    Problem‐Solving Mod 3

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    4 views9 pages

    Problem Solving Mod 3

    Uploaded by

    Shankar Paikira

    Copyright:

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

    Problem‐solving

    INFORMED SEARCH STRATEGIES, HEURISTIC FUNCTIONS


    Informed search strategy

     Informed search strategy is the one that uses problem-specific knowledge beyond
    the definition of the problem itself, can find solutions more efficiently than can an
    uninformed strategy.
     Best-first search
     Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in
    which a node is selected for expansion based on an evaluation function, f(n).
     The evaluation function is construed as a cost estimate, so the node with the lowest evaluation
    is expanded first
     The implementation of best-first graph search is identical to that for uniform-cost search except
    for the use the priority queue.
     Best-first algorithms include as a component of a heuristic function,
     h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
     For example, in Romania, one might estimate the cost of the cheapest path from Arad to
    Bucharest via the straight-line distance from Arad to Bucharest.
    Greedy best-first search

     Greedy best-first search tries to expand the node that is closest to the goal, on the
    grounds that this is likely to lead to a solution quickly.
     It evaluates nodes by using just the heuristic function; that is, f(n) = h(n).
    Greedy best-first search
    A* search: Minimizing the total estimated solution
    cost

     The most widely known form of best-first search is called A∗ search.


     It evaluates nodes by combining g(n) ,the cost tor each the node, and h(n),the cost to
    get from the node to the goal.

     Since g(n) gives the path cost from the start node to node n, and h(n)is the estimated
    cost of the cheapest path from n to the goal, then f(n)

     Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is
    the node with the lowest value of g(n)+h(n).
     It turns out that this strategy is more than just reasonable: provided that the heuristic
    function h(n)satisfies certain conditions, A∗ search is both complete and
    optimal. The algorithm is identical to UNIFORM-COST-SEARCH except that A∗
    uses g+h instead of g.
    Conditions for optimality: Admissibility and
    consistency

     Admissible heuristic
    • An admissible heuristic is one that never overestimates the cost to reach the goal.
    Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n) + h(n).
    • Admissible heuristics are by nature optimistic because they think the cost of solving the
    problem is less than it actually is.
    • Example of an admissible heuristic is the straight-line distance hSLD that we used in
    getting to Bucharest. Straight-line distance is admissible because the shortest path
    between any two points is a straight line, so the straight line cannot be an over
    estimate.
    Consistency

     A second, slightly stronger condition called consistency (or sometimes


    monotonicity) is required only for applications of A∗ to graph search.
     A heuristic h(n) is consistent if, for every node n and every successor n′
    of n generated by any action a, the estimated cost of reaching the goal
    from n is no greater than the step cost of getting to n′ plus the
    estimated cost of reaching the goal from n′
    RECURSIVE-BEST-FIRST-SEARCH

    You might also like