Heuristic Search Techniques Unit -II.ppt

AI, Heuristic algorithms, generate and test,
Hill climbing Algorithm
A* algorithm

1. HEURISTIC SEARCH
TECHNIQUES
Dr.M.Karthika
Assistant Professor/ IT
MTNC,Madurai.

2. WHAT IS A HEURISTIC?
2/7/2023 2

3. WHAT IS A HEURISTIC SEARCH?
•AHeuristicisatechniquetosolveaproblemfasterthanclassic
methods,ortofindanapproximatesolutionwhenclassicmethods
cannot.
•AHeuristic(oraheuristicfunction)takesalookatsearchalgorithms.At
eachbranchingstep,itevaluatestheavailableinformationandmakesa
decisiononwhichbranchtofollow.
•Itdoessobyrankingalternatives.TheHeuristicisanydevicethatis
ofteneffectivebutwillnotguaranteeworkineverycase.
•Thisisakindofashortcutasweoftentradeoneofoptimality,
completeness,accuracy,orprecisionforspeed.
2/7/2023 3

4. 2/7/2023 4

5. WHY DO WE NEED HEURISTICS?
•Toproduceasolution,inareasonableamountoftime.It
doesn’thavetobethebest-anapproximatesolutionwilldo
sincethisisfastenough.
•Reducethepolynomialnumberformostproblemsthatare
exponential.Andinsituationswherewecan’tfindknown
algorithms.
•HeuristicTechniquesmaybeweakmethodsbecausethey
arevulnerabletocombinatorialexplosion.
2/7/2023 5

6. •OthernamesfortheseareBlindSearch,UninformedSearch,and
BlindControlStrategy.
•Thesearen’talwayspossiblesincetheydemandmuchtimeor
memory.
•Theysearchtheentirestatespaceforasolutionanduseanarbitrary
orderingofoperations.
•ExamplesoftheseareBreadthFirstSearch(BFS)andDepthFirst
Search(DFS).
DIRECT HEURISTIC SEARCH TECHNIQUES IN AI
2/7/2023 6

7. WEAKHEURISTIC SEARCH TECHNIQUES IN AI
•Other names for these are Informed Search, Heuristic Search, and
Heuristic Control Strategy.
•These are effective if applied correctly to the right types of tasks and
usually demand domain-specific information.
•Examples are Best First Search (BFS) and A*.
•Best-First Search
•A* Search
•Bidirectional Search
•TabuSearch
•Beam Search
•Simulated Annealing
•Hill Climbing
•Constraint Satisfaction Problems
2/7/2023 7

8. HEURISTIC ALGORITHMS
2/7/2023 8

9. HILL CLIMBING –ANOTHER EXAMPLE
•Problem: You have just arrived in Washington, D.C. You’re in your car, trying to get
downtown to the Washington Monument.
2/7/2023 9

10. FEATURES OF HILL CLIMBING IN AI
•GenerateandTestvariant:HillClimbingisthevariantof
GenerateandTestmethod.TheGenerateandTestmethod
producefeedbackwhichhelpstodecidewhichdirectionto
moveinthesearchspace.
•Greedyapproach:Hill-climbingalgorithmsearchmovesin
thedirectionwhichoptimizesthecost.
•Nobacktracking:Itdoesnotbacktrackthesearchspace,asit
doesnotrememberthepreviousstates.
2/7/2023 10

11. PROBLEMS WITH HILL CLIMBING IN AI
Three issues Addressed
•LocalMaximum-Allneighboringstateshavevaluesworsethanthecurrent.The
greedyapproachmeanswewon’tbemovingtoaworsestate.Thisterminatesthe
processeventhoughtheremayhavebeenabettersolution.Asaworkaround,we
usebacktracking.
•Plateau-Allneighborstoithavethesamevalue.Thismakesitimpossibletochoose
adirection.Toavoidthis,werandomlymakeabigjump.
•Ridge-Ataridge,movementinallpossibledirectionsisdownward.Thismakesit
looklikeapeakandterminatestheprocess.Toavoidthis,wemayusetwoormore
rulesbeforetesting.
2/7/2023 11

12. STATE-SPACE DIAGRAM ANALYSIS
2/7/2023 12

13. GENERATE AND TEST SEARCH
•IsaheuristicsearchtechniquebasedonDepthFirstSearchwithBacktracking
whichguaranteestofindasolutionifdonesystematicallyandthereexistsa
solution.
•Inthistechnique,allthesolutionsaregeneratedandtestedforthebestsolution.
•Itensuresthatthebestsolutionischeckedagainstallpossiblegeneratedsolutions.
•ItisalsoknownasBritishMuseumSearchAlgorithmasit’slikelookingforan
exhibitatrandomorfindinganobjectintheBritishMuseumbywandering
randomly.
2/7/2023 13

14. GENERATE AND TEST SEARCH
Step:1Generateapossiblesolution.For
example,generatingaparticularpointin
theproblemspaceorgeneratingapathfor
astartstate.
Step:2Testtoseeifthisisaactualsolution
bycomparingthechosenpointorthe
endpointofthechosenpathtothesetof
acceptablegoalstates
Step:3Ifasolutionisfound,quit.
OtherwisegotoStep1
2/7/2023 14

15. TYPES OF HILL CLIMBING IN AI
2/7/2023 15

16. SIMPLE HILL CLIMBING
•Examines one neighboring node at a time and selects the first one that optimizes the
current cost to be the next node.
•Algorithm:
1. Evaluate initial state-if goal state, stop and return success. Else, make initial state
current.
2. Loop until the solution reached or until no new operators left to apply to current
state:
a. Select new operator to apply to the current producing new state.
b. Evaluate new state:
•If a goal state, stop and return success.
•If better than the current state, make it current state, proceed.
•Even if not better than the current state, continue until the solution
reached.
3. Exit.
2/7/2023 16

17. FEATURES:
•Lesstimeconsuming
•Lessoptimalsolutionandthesolutionisnot
guaranteed
2/7/2023 17

18. STEEPEST-ASCENT HILL CLIMBING:
•The steepest-Ascent algorithm is a variation of simple hill climbing algorithm. This
algorithm examines all the neighboring nodes of the current state and selects one
neighbor node which is closest to the goal state. This algorithm consumes more time
as it searches for multiple neighbors
2/7/2023 18

19. ALGORITHM FOR STEEPEST -ASCENT HILL
CLIMBING
•Step 1:Evaluate the initial state, if it is goal state then return success and stop, else
make current state as initial state.
•Step 2:Loop until a solution is found or the current state does not change.
•Let SUCC be a state such that any successor of the current state will be better than it.
•For each operator that applies to the current state:
•Apply the new operator and generate a new state.
•Evaluate the new state.
•If it is goal state, then return it and quit, else compare it to the SUCC.
•If it is better than SUCC, then set new state as SUCC.
•If the SUCC is better than the current state, then set current state to SUCC.
•Step 3:Exit.
2/7/2023 19

20. ANNEALING
•Annealingisathermalprocessforobtaininglowenergy
statesofasolidinaheatbath.
•Theprocesscontainstwosteps:
•Increasethetemperatureoftheheatbathtoamaximumvalueat
whichthesolidmelts.
•Decreasecarefullythetemperatureoftheheatbathuntilthe
particlesarrangethemselvesinthegroundstateofthesolid.
Groundstateisaminimumenergystateofthesolid.
•Thegroundstateofthesolidisobtainedonlyifthe
maximumtemperatureishighenoughandthecoolingis
doneslowly.
2/7/2023 20

21. SIMULATED ANNEALING
•Simulatedannealingmaintainsacurrentassignmentofvaluestovariables.
•Ateachstep,itpicksavariableatrandom,thenpicksavalueatrandom.If
assigningthatvaluetothevariableisanimprovementordoesnotincreasethe
numberofconflicts,thealgorithmacceptstheassignmentandthereisanew
currentassignment.
•Otherwise,itacceptstheassignmentwithsomeprobability,dependingonthe
temperatureandhowmuchworseitisthanthecurrentassignment.Ifthechangeis
notaccepted,thecurrentassignmentisunchanged.
2/7/2023 21

22. •Tocontrolhowmanyworseningstepsareaccepted,thereisapositivereal-valued
temperatureT.
•SupposeAisthecurrentassignmentofavaluetoeachvariable.Supposethath(A)is
theevaluationofassignmentAtobeminimized.
•Forsolvingconstraints,histypicallythenumberofconflicts.Simulatedannealing
selectsaneighboratrandom,whichgivesanewassignmentA'.Ifh(A')≤h(A),it
acceptstheassignmentandA'becomesthenewassignment.Otherwise,the
assignmentisonlyacceptedrandomlywithprobability
• e(h(A)-h(A'))/T.
•Thus,ifh(A')isclosetoh(A),theassignmentismorelikelytobeaccepted.Ifthe
temperatureishigh,theexponentwillbeclosetozero,andsotheprobabilitywillbe
closeto1.Asthetemperatureapproacheszero,theexponentapproaches-∞,andthe
probabilityapproacheszero.
2/7/2023 22

23. BEST FIRST SEARCH
•OR Graphs
•The A* Algorithm
2/7/2023 23

24. OR GRAPHS
•BFS uses the concept of a Priority queue and heuristic search.
•To search the graph space, the BFS method uses two lists for tracking
the traversal.
•An ‘Open’ list that keeps track of the current ‘immediate’ nodes
available for traversal and a ‘CLOSED’ list that keeps track of the
nodes already traversed.
2/7/2023 24

25. BEST FIRST SEARCH ALGORITHM
•Create 2 empty lists: OPEN and CLOSED
•Start from the initial node (say N) and put it in the ‘ordered’ OPEN list
•Repeat the next steps until the GOAL node is reached
•If the OPEN list is empty, then EXIT the loop returning ‘False’
•Select the first/top node (say N) in the OPEN list and move it to the CLOSED list. Also,
capture the information of the parent node
•If N is a GOAL node, then move the node to the Closed list and exit the loop returning ‘True’.
The solution can be found by backtracking the path
•If N is not the GOAL node, expand node N to generate the ‘immediate’ next nodes linked to
node N and add all those to the OPEN list
•Reorder the nodes in the OPEN list in ascending order according to an evaluation function f(n)
2/7/2023 25

26. 2/7/2023 26

27. ADVANTAGES AND DISADVANTAGES OF
BEST FIRST SEARCH
•Advantages:
1. Can switch between BFS and DFS, thus gaining the advantages of
both.
2. More efficient when compared to DFS.
•Disadvantages:
1. Chances of getting stuck in a loop are higher.
2/7/2023 27

28. A* SEARCH ALGORITHM
A*searchisthemostcommonlyknownformofbest-firstsearch.Itusesheuristicfunctionh(n),
andcosttoreachthenodenfromthestartstateg(n).IthascombinedfeaturesofUCSand
greedybest-firstsearch,bywhichitsolvetheproblemefficiently.
A*searchalgorithmfindstheshortestpaththroughthesearchspaceusingtheheuristic
function.Thissearchalgorithmexpandslesssearchtreeandprovidesoptimalresultfaster.A*
algorithmissimilartoUCSexceptthatitusesg(n)+h(n)insteadofg(n).
InA*searchalgorithm,weusesearchheuristicaswellasthecosttoreachthenode.Hencewe
cancombinebothcostsasfollowing,andthissumiscalledasafitnessnumber.
Example
2/7/2023 28

29. ALGORITHM
Step1:Place the starting node in the OPEN list.
Step 2:Check if the OPEN list is empty or not, if the list is empty then return failure and
stops.
Step 3:Select the node from the OPEN list which has the smallest value of evaluation
function (g+h), if node n is goal node then return success and stop, otherwise
Step 4:Expand node n and generate all of its successors, and put n into the closed list.
For each successor n', check whether n' is already in the OPEN or CLOSED list, if not
then compute evaluation function for n' and place into Open list.
Step 5:Else if node n' is already in OPEN and CLOSED, then it should be attached to the
back pointer which reflects the lowest g(n') value.
Step 6:Return toStep 2.
2/7/2023 29

30. Advantages:
•A* search algorithm is the best algorithm than other search algorithms.
•A* search algorithm is optimal and complete.
•This algorithm can solve very complex problems.
Disadvantages:
•It does not always produce the shortest path as it mostly based on heuristics and
approximation.
•A* search algorithm has some complexity issues.
•The main drawback of A* is memory requirement as it keeps all generated nodes in the
memory, so it is not practical for various large-scale problems.
2/7/2023 30

31. THANK YOU
2/7/2023 31