Admissible heuristics Relaxed problems Eg.for the 8-puzzle If the rules of the 8-puzzle are relaxed so that a tile can move anywhere (i.e.,no.of squares from des location of each tile) then)gives the shortest solution ⑦24 123 If the rules are relaxed so that a tile can move to any adjacent square 456 then ha(n)gives the shortest solution 83 78 roblem Admissible heuristics Relaxed problems contd. Egfor the 8-puzzle (i.e.no.of squares from desired location of each tile) 24 456 78 8043431404241=4 Minimum spanning tree can be computed in (n and is a lower bound on the shortest(open)tou Dominance Summary Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cos Typical search costs: Greedy best-first search expands lowest -incomplete and not always optimal d=241D5≈54.000.000.000nods Admissible heuristics can be derived from exact solution of relaxed problem Given any admissible heuristics h(n)=max(ha(n).ho(n)) is also admissible and dominates Admissible heuristics E.g., for the 8-puzzle: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 h1(S) =?? h2(S) =?? Chapter 4, Sections 1–2 31 Admissible heuristics E.g., for the 8-puzzle: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 h1(S) =?? 6 h2(S) =?? 4+0+3+3+1+0+2+1 = 14 Chapter 4, Sections 1–2 32 Dominance If h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1 and is better for search Typical search costs: d = 14 IDS = 3,473,941 nodes A ∗ (h1) = 539 nodes A ∗ (h2) = 113 nodes d = 24 IDS ≈ 54,000,000,000 nodes A ∗ (h1) = 39,135 nodes A ∗ (h2) = 1,641 nodes Given any admissible heuristics ha, hb , h(n) = max(ha(n), hb(n)) is also admissible and dominates ha, hb Chapter 4, Sections 1–2 33 Relaxed problems Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem Chapter 4, Sections 1–2 34 Relaxed problems contd. Well-known example: travelling salesperson problem (TSP) Find the shortest tour visiting all cities exactly once Minimum spanning tree can be computed in O(n 2 ) and is a lower bound on the shortest (open) tour Chapter 4, Sections 1–2 35 Summary Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h – incomplete and not always optimal A ∗ search expands lowest g + h – complete and optimal – also optimally efficient (up to tie-breaks, for forward search) Admissible heuristics can be derived from exact solution of relaxed problems Chapter 4, Sections 1–2 36