Transcription
Heuristic Search A heuristic is a rule for choosing abranch in a state space search that willmost likely lead to a problem solution Heuristics are used when– there is no exact solution to a problem, asin medical diagnosis– there is an exact solution but thecomputation is prohibitively expensive,as in the game of chess Heuristics are fallible– they may find suboptimal solutions– they may find no solution at all Heuristics are problem dependent andthere may be many alternativeheuristics for the same problemTic-Tac-Toe Without considering symmetry the searchspace is 9!; using symmetry the searchspace is 12 * 7! A simple heuristicis the number ofsolution paths stillopen when thereare 8 total paths (3rows, 3 columns, 2diagonals) Here is the searchspace using thisheuristic The total searchspace is nowreduced to about40, depending onthe opponents play1
Another Heuristic Try to devise any alternative heuristicfor tic-tac-toe that is either entirelydifferent than the heuristic on theprevious page or that uses thatheuristic plus some othermeasurements (such as blocking theopponent)Hill Climbing The basic steps are– expand the current node and evaluate thechildren using your heuristic– select the child with the best heuristicvalue and discard the other children Although this algorithm is simple toimplement, it has many severeproblems– the algorithm may halt with the parent isbetter than all the children and where ithalts may not be a solution– since a history is not maintained it cannotrecover from this failure– this approach is susceptible to gettingstuck in a local maxima2
Best-first SearchExample search space Here is a hypothetical search space Notice theheuristic is notperfect; O-2 isnot a goal buthas a lowervalue that P-3which is a value Since the heuristic value changes as thecurrent state changes, what happens if anode is revisited and now has a lower value– if still on the open list, reduce the value– if on the closed list, assign the new value andput it back on the open list (may be useful whenthe exact form of the goal is not known)3
Heuristics for the Eight Puzzle Three possible heuristics– count # tiles out of place– sum of the distances out of place– 2 times the number of direct reversalsApplying Heuristics Use the heuristic of adding the numberof tiles out of place to two times thenumber of direct reversals Start with2 8 316745and apply this heuristic relative to thegoal shown below; find the next fivemoves Reversals only works well if you are near agoal; a combined heuristic (sum of distancesand reversals) might work better187263454
Avoiding the “garden path”A heuristic search We need to penalize long searches so weinclude path depth as another factorf(n) g(n) h(n) where g(n) is the pathlength and h(n) is the heuristic value Path length starts at 0 and is incremented by1 for each move The search space isdrastically reducedin size by theevaluation function5
Applying Another HeuristicsOpen and closed lists Use the heuristic of adding the sum ofdistances out of place to the pathlength Start with2 8 316745and apply this heuristic relative to thegoal shown below; find the next fivemoves187263456
The basic approach When a state is examined all of itschildren are generated Any children already visited (on theopen or closed lists) are discarded The value of f(n) is the sum of theheuristic function and the length of thesearch path The set of open states is sorted by thevalues for f(n) The algorithm can be more efficientby choosing appropriate datastructures for the open and closed listsAdmissibility An algorithm is admissible if it isguaranteed to find a minimal path to asolution (assuming one exists) Breadth-first search is admissible Suppose g*(n) is the cost of the shortestpath from the start node to n Suppose the h*(n) is the actual cost of theshortest path from node n to the goal if f*(n) g*(n) h*(n) then a best firstsearch using f* is admissible7
A* Algorithms In general, g(n) g*(n) If h(n) h*(n) for all n, then any evaluationfunction f using h(n) and best first searchwill result in an A* algorithmIs it A* ? Consider the eight puzzle Is the heuristics of counting thenumber of tiles out of place A* ? Is the heuristics of counting the sumof direct distances A* ? Breadth first search is an A* algorithmwhere h(n) 0 Examples with the eight puzzle– # tiles out of place # moves to the goal– sum of direct distances # moves to the goal8
A Blocks World Problem Suppose a blocks world has problemsof the form “stack block X on blockY”. Give a heuristic that might solvesuch problems. Is it admissible?Informedness Three heuristics for the eight puzzle– h1(n) 0 for all states, this is a breadth firstsearch; it is admissible but it has the problem ofmaintaining too many open states– h2(n) is the number of tiles out of place, whichis admissible– 0 h1(n) h2(n) h*(n) so we say h2 is moreinformed than h1– being more informed means you will searchfewer states to find an optimal solution9
A Third Heuristic Let h3(n) be the sum of the distancesout of place How does h3 compare with h2 and h1on the previous page? Whichheuristic is most informed?Comparison of three searches Breadth first searches every state shown Using the number of tiles out of place is ingray; 14 states are searched Optimal searches only 6 states10
Tic-Tac-Toe Without considering symmetry the search space is 9!; using symmetry the search space is 12 * 7! A simple heuristic is the number of solution paths still open when there are 8 total paths (3 rows, 3 columns, 2 diagonals) Here is the search space using this heuristic The total search space is now reduced to about
