Outline

Outline
Slide Note
Embed
Share

Informed search techniques like Greedy Best-First Search and A* Search use domain-specific hints to efficiently find solutions. Greedy search prioritizes nodes closer to the goal, while A* considers both estimated and actual costs for optimal paths. Explore how these algorithms work with heuristic functions and evaluation measures.

  • Informed search
  • Greedy Best-First
  • A* Algorithm
  • Heuristic functions
  • Optimal path

Uploaded on Feb 24, 2025 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


  1. Outline Informed search (using domain-specific hints about the goal) I. Greedy best-first search II. A* search * Figures are from the textbook site (or drawn by the instructor) unless the source is specifically cited.

  2. I. Informed (Heuristic) Search Use of domain-specific hints about the location of a goal can find a solution more efficiently. Heuristic function: ? =estimated cost of the cheapest path from the state at node ? to a goal state e.g., straight-line distance ??? on the map between two sites Straight-line distance to Bucharest

  3. Greedy Best-First Search Evaluation function ?(?) = (?) ? ? = ???(?) Good correlations with road distances

  4. Greedy Search for Bucharest Closer to Bucharest than is Zerind or Timisoara

  5. Search for Bucharest (contd)

  6. Greedy Optimal Greedy solution: Arad Sibiu Fagaras Bucharest (450) Optimal solution: Arad Sibiu Rimnicu Vilcea Pitesti Bucharest (418) This greedy strategy does not account for the cost to get to the current state.

  7. II. A* Search P. E. Hart, N. J. Nilsson, and B. Raphael (1968) ? ? = ? ? + (?) estimated cost from ? to goal actual cost from start to ? goal state ? initial state ?(?): estimated cost of the best path that continues from ? to a goal.

  8. A* on Route Planning ? ? = ? ? + ???(?) ???(????) ???: straight-line distance

  9. Working of A* Search ???: straight-line distance

  10. Working of A* ???: straight-line distance

  11. Working of A* ???: straight-line distance

  12. Working of A* ???: straight-line distance

More Related Content