Informed SearchCS472/CS473 — Fall 2005Slide CS472 – Heuristic Search 1Informed Methods: Heuristic SearchIdea : Informed search by using problem-specific knowledge.Best-First Search : Nodes are selected for expansionbasedonanevaluation function, f (n). Traditionally, fis a cost measure.Heuristic : Problem specific knowledge that (tries to) leadthe search algorithm faster towards a goal state.→ Heuristic search is an attempt to search the most promisingpaths first. Uses heuristics, or rules of thumb, to find the bestnode to expand next.Slide CS472 – Heuristic Search 2Generic Best-First Search1. Set L to be the initial node(s) representing the initialstate(s).2. If L is empty, fail. Let n be the node on L that is “mostpromising” according to f.Removen from L.3. If n is a goal node, stop and return it (and the pathfrom the initial node to n).4. Otherwise, add successors(n) to L.Returntostep2.Slide CS472 – Heuristic Search 3Greedy Best-First SearchHeuristic function h(n) : estimated cost from node n tonearest goal node.Greedy Search :Letf (n)=h(n).Example : 8-puzzleStart StateGoal State245678123467812345678123456785Slide CS472 – Heuristic Search 4Suboptimal Best-First Searcha,3b,4c,2d,1e,1f,1g,1goal1h,1goal2There exist strategies that enable optimal paths to be foundwithout examining all possible paths.Slide CS472 – Heuristic Search 5A* SearchIdea: Use total estimated solution cost:g(n)Costofreachingnoden from initial nodeh(n) Estimated cost from node n to nearest goalA* evaluation function: f (n)=g(n)+h(n)→ f (n) is estimated cost of cheapest solution through n.Slide CS472 – Heuristic Search 6Comparison of Search Costs on 8-Puzzleh1: numb er of misplaced tilesh2: Manhattan distanceSearch Cost Effective Branching Factord IDS A*(h1) A*(h2) IDS A*(h1) A*(h2)2 10 6 6 2.45 1.79 1.794 112 13 12 2.87 1.48 1.456 680 20 18 2.73 1.34 1.308 6384 39 25 2.80 1.33 1.2410 47127 93 39 2.79 1.38 1.2212 364404 227 73 2.78 1.42 1.2414 3473941 539 113 2.83 1.44 1.2316 – 1301 211 – 1.45 1.2518 – 3056 363 – 1.46 1.2620 – 7276 676 – 1.47 1.2722 – 18094 1219 – 1.48 1.2824 – 39135 1641 – 1.48 1.26Slide CS472 – Heuristic Search 7Examplea,3b,4c,2d,1e,1f,1g,1goal1h,1goal2Slide CS472 – Heuristic Search 8Admissibilityh∗(n) Actual cost to reach a goal from n.A heuristic function h is optimistic or admissible ifh(n) ≤ h∗(n) f or all nodes n.If h is admissible, then the A* algorithm will never returna suboptimal goal node. (h never overestimates the costof reaching the goal.)Slide CS472 – Heuristic Search 9Example322111goal1goalgoal?Slide CS472 – Heuristic Search 10Example: Admissible HeuristicWhat if h(n)=h∗(n)?f(n)=g(n )+h∗(n)The perfect heuristic function!Slide CS472 – Heuristic Search 11Example: Admissible HeuristicWhat if h(n)=0?f(n)=g(n )+h(n)Slide CS472 – Heuristic Search 128-puzzle1. hC= number of misplaced tiles2. hM= Manhattan distanceWhich one should we use?hC≤ hM≤ h∗Slide CS472 – Heuristic Search 13Comparison of Search Costs on 8-PuzzleSearch Cost Effective Branching Factord IDS A*(h1) A*(h2) IDS A*(h1) A*(h2)2 10 6 6 2.45 1.79 1.794 112 13 12 2.87 1.48 1.456 680 20 18 2.73 1.34 1.308 6384 39 25 2.80 1.33 1.2410 47127 93 39 2.79 1.38 1.2212 364404 227 73 2.78 1.42 1.2414 3473941 539 113 2.83 1.44 1.2316 – 1301 211 – 1.45 1.2518 – 3056 363 – 1.46 1.2620 – 7276 676 – 1.47 1.2722 – 18094 1219 – 1.48 1.2824 – 39135 1641 – 1.48 1.26Slide CS472 – Heuristic Search 14Constructing Admissible Heuristics• Use an admissible heuristic derived from a relaxedversion of the problem.• Use information from pattern databases that storeexact solutions to subproblems of the problem.• Use inductive learning methods.Slide CS472 – Heuristic Search 15Proving the optimality of A∗Lemma: If h is admissible, then f = g + h can be madenon-decreasing.1. g is non-decreasing since cost positive.2. But h can be increasing, while still admissible. Example:Node p,withf = 3 + 4 = 7; child n,withf =4+2=6.3. But because any path through n is also a path throughp, we can see that the value 6 is meaningless, b ecause wealready know the true cost is at least 7 (because h isadmissible).4. So, make f = max(f(p),g( n )+h(n))Slide CS472 – Heuristic Search 16ProofoftheoptimalityofA∗Assume: h admissible; f non-decreasing along any path.Proof:Let G be an optimal goal state, with path cost f∗.Let G2be a suboptimal goal state, with path cost g(G2) >f∗.Let n isanodeonanoptimalpathtoG.Because h is admissible, we must havef∗≥ f (n).Also, if n is not chosen over G2,wemusthavef(n) ≥ f(G2).Gives us f∗≥ f (G2)=g(G2). (Contradiction to G2suboptimal!)Slide CS472 – Heuristic Search