1Heuristic Search2Heuristic Search•Heuristic or informed search exploits additionalknowledge about the problem that helps direct search tomore promising paths.•A heuristic function, h(n), provides an estimate of the costof the path from a given node to the closest goal state.Must be zero if node represents a goal state.-Example: Straight-line distance from current location tothe goal location in a road navigation problem.•Many search problems are NP-complete so in the worstcase still have exponential time complexity; however a goodheuristic can:-Find a solution for an average problem efficiently.-Find a reasonably good but not optimal solutionefficiently.3Best-First Search•At each step, best-first search sorts the queue according to aheuristic function.function BEST-FIRST-SEARCH( problem,EVAL-FN) returns a solution sequenceinputs: problem, a problemEval-Fn, an evaluation functionQueueing-Fn a function that orders nodes by EVAL-FNreturn GENERAL-SEARCH(problem,Queueing-Fn)BucharestGiurgiuUrziceniHirsovaEforieNeamtOradeaZerindAradTimisoaraLugojMehadiaDobretaCraiovaSibiuFagarasPitestiRimnicu VilceaVasluiIasiStraight−line distanceto Bucharest 0160242161771512413661931782533298019924438022623437498GiurgiuUrziceniHirsovaEforieNeamtOradeaZerindAradTimisoaraLugojMehadiaDobretaCraiovaSibiuFagarasPitestiVasluiIasiRimnicu VilceaBucharest717511811170751201511409980971012111381468590981429287864Best-First Example•Does not find shortest path to goal (through Rimnicu) since it isonly focused on the cost remaining rather than the total cost.Aradh=366AradTimisoara ZerindSibiuh=253 h=329 h=374AradTimisoara ZerindSibiuh=329 h=374Arad OradeaFagaras Rimnicuh=380 h=193h=366 h=178AradTimisoara ZerindSibiuh=329 h=374Arad OradeaFagaras Rimnicuh=380 h=193h=366Sibiuh=253Bucharesth=05Best-First Properties•Not complete, may follow infinite path if heuristic rates eachstate on such a path as the best option. Most reasonableheuristics will not cause this problem however.•Worst case time complexity is still O(bm) where m is themaximum depth.•Since must maintain a queue of all unexpanded states,space-complexity is also O(bm).•However, a good heuristic will avoid this worst-casebehavior for most problems.6Beam Search•Space and time complexity of storing and sorting the completequeue can be too inefficient.•Beam search trims queue to the best n options (n is called thebeam width) at each point.•Focuses search more but may eliminate solution even for finiteseach graphs•Example for n=2.Aradh=366AradTimisoara ZerindSibiuh=253 h=329 h=374AradTimisoara ZerindSibiuh=329 h=374Arad OradeaFagaras Rimnicuh=380 h=193h=366 h=178AradTimisoara ZerindSibiuh=329 h=374Arad OradeaFagaras Rimnicuh=380 h=193h=366Sibiuh=253Bucharesth=07Hill-Climbing•Beam search with a beam-width of 1 is called hill-climbing.•Pursues locally best option at each point, i.e. the bestsuccessor to the current best node.•Subject to local maxima, plateaux, and ridges.evaluationcurrentstate8Minimizing Total Path Cost: A* Search•A* combines features of uniform cost search (complete,optimal, inefficient) with best-first (incomplete, non-optimal,efficient).•Sort queue by estimated total cost of the completion of apath.f(n) = g(n) + h(n)•If the heuristic function always underestimates the distanceto the goal, it is said to be admissible.•If h is admissible, then f(n) never overestimates the actualcost of the best solution through n.9A* Example•Finds the optimal path to Bucharest through Rimnicu and PitestiAradAradTimisoara ZerindSibiuSibiuArad OradeaFagaras RimnicuAradTimisoara ZerindSibiuArad OradeaFagaras RimnicuAradTimisoara ZerindCraiova Pitesti Sibiuf=0+366 =366f=140+253 =393f=118+329 =447f=75+374 =449f=280+366 =646f=239+178 =417f=146+380 =526f=118+329 =447f=220+193 =413f=75+374 =449f=280+366 =646f=239+178 =417f=146+380 =526f=118+329 =447f=75+374 =449f=300+253 =553f=317+98 =415f=366+160 =52610Optimality of A*•If h is admissible, A* will always find a least cost path to thegoal.•Proof by contradiction:Let G be an optimal goal state with a path cost f*Let G2 be a suboptimal goal state supposedly found by A*Let n be a current leaf node on an optimal path to GSince h is admissible:f* >= f(n)If G2 is chosen for expansion over n then:f(n) >= f(G2)Therefore:f* >= f(G2)Since G2 is a goal state, h(G2)=0, thereforef(G2) = g(G2)f* >= g(G2)Therefore G2 is optimal.Contradiction.Q.E.D.11Other Properties of A*•A* is complete as long as-Branching factor is always finite-Every operator adds cost at least δ > 0•Time and space complexity still O(bm) in the worst casesince must maintain and sort complete queue of unexploredoptions.•However, with a good heuristic can find optimal solutions formany problems in reasonable time.•Again, space complexity is a worse problem than time.12Heuristic Functions•8-puzzle search space-Typical solution length: 20 steps-Average branching factor: 3-Exhaustive search: 320=3.5 x 109-Bound on unique states: 9! = 362,880•Admissible Heuristics:-Number of tiles out of place (h1): 7-City-block (Manhattan) distance (h2):2+3+3+2+4+2+0+2=18Start StateGoal State2456781 2346781234567812345678513Heuristic Performance•Experiments on sample problems can determine the number ofnodes searched and CPU time for different strategies.•One other useful measure is effective branching factor: If amethod expands N nodes to find solution of depth d, and auniform tree of depth d would require a branching factor of b*to contain N nodes, the effective branching factor is b*N = 1 + b* + (b*)2+ ...+ (b*)d•Experimental Results on 8-puzzle problemsSearch 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.2614Quality of Heuristics•ISince A* expands all nodes whose f value is less than thatof an optimal solution, it is always better to use a heuristicwith a higher value as long as it does not over-estimate.•Therefore h2 is uniformly better than h1, or h2dominatesh1.•A heuristic should also be easy to compute, otherwise theoverhead of computing the heuristic could outweigh thetime saved by reducing search (e.g. using full breadth-firstsearch to estimate