I.ITERATIVE DEEPENING DEPTH FIRST SEARCH(ID-DFS) II.INFORMED SEARCH IN ARTIFICIAL INTELLIGENCE III.HEURISTIC FUNCTION 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.ITERATIVE DEEPENING DEPTH FIRST SEARCH(ID-DFS)
II.INFORMED SEARCH IN ARTIFICIAL INTELLIGENCE
III.HEURISTIC FUNCTION 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. ITERATIVE DEEPENING DEPTH FIRST SEARCH(ID-DFS
This is type of Uninformed
search technique also called
as blind search.
This algo. Works on only
present value.
This algorithm is
combination of DFS & BFS
It uses STACK (LIFO) to
perform search operations
Utilizes Deepest &
shallowest Node

3. ITERATIVE DEEPENING DEPTH FIRST SEARCH(ID-DFS
Best depth limit is found out
by gradually increasing depth
limit on each iterations.
Initially depth limit is =0
On each iteration depth
increased by exactly one.
S->Initial Node Or Source Node
G->Goal Node Or Target Node

4. ITERATIVE DEEPENING DEPTH FIRST SEARCH(ID -DFS
Advantages of ID-DFS:
Combine the advantage of both DFS and BF
It is Complete & Optimal
Will not go in infinite loop
Disadvantages of ID-DFS:
Regressive Recursion is required
May required more memory

5. 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.

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

7. 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.

8. 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.

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

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

11. 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

12. 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

13. 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