Scribd Logo
Upload

Welcome to Scribd!

  • 24 views

    CSE860 - 11 - Informed Search Strategies

    Uploaded by

    Aqeel Ahmed
    This document discusses informed search techniques for artificial intelligence, specifically as taught in CSE 860. It covers the differences between uninformed and informed search, and describes best-first search, greedy best-first search, and the A* search algorithm. The document explains that A* uses an evaluation function of f(n) = g(n) + h(n) and requires an admissible and consistent heuristic to find optimal solutions.

    Copyright:

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

    CSE860 - 11 - Informed Search Strategies

    Uploaded by

    Aqeel Ahmed
    24 views15 pages
    This document discusses informed search techniques for artificial intelligence, specifically as taught in CSE 860. It covers the differences between uninformed and informed search, and describes best-first search, greedy best-first search, and the A* search algorithm. The document explains that A* uses an evaluation function of f(n) = g(n) + h(n) and requires an admissible and consistent heuristic to find optimal solutions.

    Original Description:

    AI informed search

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses informed search techniques for artificial intelligence, specifically as taught in CSE 860. It covers the differences between uninformed and informed search, and describes best-first search, greedy best-first search, and the A* search algorithm. The document explains that A* uses an evaluation function of f(n) = g(n) + h(n) and requires an admissible and consistent heuristic to find optimal solutions.

    Copyright:

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

    CSE860 - 11 - Informed Search Strategies

    Uploaded by

    Aqeel Ahmed
    This document discusses informed search techniques for artificial intelligence, specifically as taught in CSE 860. It covers the differences between uninformed and informed search, and describes best-first search, greedy best-first search, and the A* search algorithm. The document explains that A* uses an evaluation function of f(n) = g(n) + h(n) and requires an admissible and consistent heuristic to find optimal solutions.

    Copyright:

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

    CSE 860 Artificial Intelligence

    (Informed Search)

    Prof. Dr. Yasar Ayaz


    (Pride of Performance)

    Chairman / Central Project Director


    National Center of Artificial Intelligence (NCAI)
    Pakistan

    Professor & Founding Head


    Department of Robotics & AI
    NUST-SMME
    1
    • Uninformed (or Blind) Search:
    No additional information about states
    beyond that provided in the problem
    definition.
    • Informed (or Heuristic) Search:
    When it is possible to know whether one non-
    goal state is more promising than the other.

    2
    • Informed Search → Best-First Search

    • Evaluation Function f(n)

    • Heuristic Function h(n)


    Estimated cost of the cheapest path from the
    state at node n to a goal state.

    3
    • 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 the function by using just the
    heuristic function i.e.
    f(n) = h(n)

    4
    5
    6
    7
    f(n) = g(n) + h(n)

    • g(n) gives the path cost from the start node n


    and h(n) is the estimated cost of the cheapest
    path from n to the goal.

    f(n) = estimated cost of the cheapest


    solution through n
    8
    9
    10
    11
    12
    13
    14
    Conditions for Optimality of A* Search:

    • Admissible Heuristic
    A heuristic is admissible if it never
    overestimates the cost to reach the goal.
    • Consistency
    h(n) ≤ c(n,a,n/) + h(n/)
    ➔ Triangle Inequality

    15

    You might also like