Outline
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.
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
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.
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
Greedy Best-First Search Evaluation function ?(?) = (?) ? ? = ???(?) Good correlations with road distances
Greedy Search for Bucharest Closer to Bucharest than is Zerind or Timisoara
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.
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.
A* on Route Planning ? ? = ? ? + ???(?) ???(????) ???: straight-line distance
Working of A* Search ???: straight-line distance
Working of A* ???: straight-line distance
Working of A* ???: straight-line distance
Working of A* ???: straight-line distance