I.INFORMED SEARCH IN ARTIFICIAL INTELLIGENCE II. HEURISTIC FUNCTION IN AI III. BEST FIRST SEARCH IN AI

Artificial Intelligence: Introduction, Typical Applications. State Space Search: Depth Bounded
DFS, Depth First Iterative Deepening. Heuristic Search: Heuristic Functions, Best First Search,
Hill Climbing, Variable Neighborhood Descent, Beam Search, Tabu Search. Optimal Search: A
*

algorithm, Iterative Deepening A*
, Recursive Best First Search, Pruning the CLOSED and OPEN
Lists

1. Topic To Be Covered:
I.INFORMED SEARCH IN ARTIFICIAL INTELLIGENCE
II. HEURISTIC FUNCTION IN AI
III. BEST FIRST SEARCH IN AI
Jagdamba Education Society's
SND College of Engineering & Research Centre
Department of Computer Engineering
SUBJECT: Artificial Intelligence & Robotics
Lecture No-08
Prof.Dhakane Vikas N

2. Types of search in ai
II. Informed Search In AI
It is search with information.
It is greedy search method
Use knowledge to find steps to solution.
Less Complexity(Time, Space)
Quick Solution
Know about Start state and Goal state & Also
know how to reach.
informedsearchalgorithmcontainsan
arrayofknowledgesuchashowfarweare
fromthegoal,pathcost,howtoreachto
goalnode,etc.Thisknowledgehelpagents
toexplorelesstothesearchspaceandfind
moreefficientlythegoalnode.
Theinformedsearchalgorithmismore
usefulforlargesearchspace.Informed
searchalgorithmusestheideaof
heuristic,soitisalsocalledHeuristic
search.

3. HEURISTIC FUNCTION in ai
Heuristicisafunctionwhichisusedin
InformedSearch,anditfindsthemost
promisingpath.
Ittakesthecurrentstateoftheagentasits
inputandproducestheestimationofhow
closeagentisfromthegoal.
Heuristicfunctionestimateshowclosea
stateistothegoal.Itisrepresentedby
h(n),anditcalculatesthecostofan
optimalpathbetweenthepairofstates.
Theheuristicmethod,however,mightnot
alwaysgivethebestsolution,butit
guaranteedtofindagoodsolutionin
reasonabletime.
Thistechniquealwaysusetofindsolution
quickly.

4. HEURISTIC FUNCTION in ai
Heuristicisafunctionwhichis
usedinInformedSearch,andit
findsthemostpromisingpath.
Ittakesthecurrentstateofthe
agentasitsinputandproduces
theestimationofhowclose
agentisfromthegoal.
Heuristicfunctionestimates
howcloseastateistothegoal.
Itisrepresentedbyh(n),andit
calculatesthecostofan
optimalpathbetweenthepair
ofstates.
The heuristicmethod,
however,mightnotalways
givethebestsolution,butit
guaranteedtofindagood
solutioninreasonabletime.

5. HEURISTIC FUNCTION in ai
Different Method Used To Estimate Heuristic Value
---------------------------------------------------------------------------
I.Euclidian Distance (Straight Line Distance Method)
Euclideandistanceisthedistancebetweentwopoints
inEuclideanspace.EuclideanspacewasoriginallydevisedbytheGreek
mathematicianEuclidaround300B.C.E.tostudytherelationships
betweenanglesanddistances.

6. HEURISTIC FUNCTION in ai
Different Method Used To
Estimate Heuristic Value
II. Manhattan Distance
Incaseof8-Puzzleproblem
Manhattandistancesare
nothingbutNumberof
movesneedtobemadebyAI
agentsothatitcanreachto
itsgoalstate.

7. HEURISTIC FUNCTION in ai
Different Method Used
To Estimate Heuristic
Value
-------------------------------
III. No.of Misplaced
Tiles

8. BEST FIRST SEARCH(BFS)
This is informed search technique
also called as HEURISTIC search.
This algo. Works using heuristic
value.
This algorithm uses evaluation
function to decide which adjacent
node is most promising and then
explore.
Priority queue is used to store cost
of function.
Space & Time Complexity of BFS is
also O(V+E)where V is vertices and E
is edges.
Also Written as:-O(b)^d
Where, b->Branching factor
d->depth

9. BEST FIRST SEARCH(BFS)
Algorithm
Priority queue ‘PQ’ containing
initial states
Loop
If PQ=Empty Return Fail
Else
NODE<-Remove_First(PQ)
If NODE=GOAL
Return path from initial state to
NODE
ELSE
Generate all successor of NODE
and insert newly generated NODE
into ‘PQ’ according to cost value.
END LOOP

10. BEST FIRST SEARCH(BFS)
Advantages of BFS:
Memory efficient as compared with DFS & BFS
It is Complete
Disadvantages of BFS:
It gives good solution but not optimal solution.
In worst case it may behave like unguided DFS