ITERATIVE DEEPNING DEPTH FIRST PPT SEARCH

Iterative Deepening Depth-First Search (IDDFS) is a search algorithm that combines the benefits of both Depth-First Search (DFS) and Breadth-First Search (BFS). It is particularly useful in scenarios where the depth of the search tree is unknown and the solution could be located at any level. In this detailed explanation, we'll explore the various aspects of IDDFS, including its motivation, implementation, advantages, disadvantages, and applications.

1. NAME: VIVEK MAJUMDAR
SUBJECT: ARTIFICIAL INTELLIGENCE
COURSE: B-TECH
SEM: V
SEC: B
ROLL NO: 11900122094
YEAR: 2024-25
DEPARTMENT: COMPUTER SCIENCE & ENGINEERING
1

2. CONTENTS
SLIDE NOCONTENTSSL NO
03INTRODUCTIONTOSEARCHALGORITHM1
04DEPTHFIRSTSEARCH&BREATHFIRSTSEARCH2
05INTRODUCTIONTOIDDFS3
06IDDFSALGORITHM4
07ADVANTAGES5
08DISADVANTAGES6
09TIME&SPACECOMPLEXITY7
10EXAMPLES8
11CONCLUSION9
12REFERENCES10
2

3. INTRODUCTION TO SEARCH ALGORITHM
SearchAlgorithmsaremethodsfornavigatingandexploringdatastructuresor
graphstolocateaparticularitemorsetofitems.Theyplayacrucialrolein
variouscomputationaltasks.
Types:
Uninformed Search (Blind Search):
Examples:Depth-FirstSearch(DFS),Breadth-
FirstSearch(BFS),Uniform-CostSearch.
Informed Search (Heuristic Search):
Examples: A*, Greedy Best-First Search.
Purpose:
Pathfinding
Problem Solving
Data Retrieval
3

4. DEPTH FIRST SEARCH & BREATH FIRST SEARCH
Depth-FirstSearch(DFS)isafundamentalsearch
algorithmusedtotraverseorsearchthroughtreeor
graphdatastructures.Itexploresasfardowna
branchaspossiblebeforebacktracking.
Works:
LIFOStructure
Traversal
Backtracking
Limitations:
InfiniteLoops:Maygetstuckininfiniteloopsif
cyclesexistinthegraphandcycledetectionisnot
implemented.
NotAlwaysOptimal:Maynotfindtheshortest
pathtothegoalinunweightedgraphs.
Breadth-FirstSearch(BFS)isafundamentalsearch
algorithmusedfortraversingorsearchingtreeand
graphstructures.Itexploresalltheneighbornodesat
thepresentdepthpriortomovingontonodesatthe
nextdepthlevel.
Works:
Queue-Based Approach:
Traversal process
Limitations:
MemoryConsumption:BFScanconsumealarge
amountofmemory,especiallyinwideorinfinite
graphs.
SlowerforDeepSolutions:Itexploreseachdepth
levelcompletelybeforemovingdeeper,whichcan
beinefficientfordeepsolutionsinlargegraphs.
4

5. INTRODUCTION TO IDDFS
Definition:
IterativeDeepeningDepth-FirstSearch(IDDFS)isasearchalgorithmthatcombinesthespaceefficiencyofDepth-
FirstSearch(DFS)withtheoptimalityandcompletenessofBreadth-FirstSearch(BFS).
Concept:
CombinationofDFSandBFS:IDDFSperformsaseriesofdepth-limitedDFS,increasingthedepthlimitwitheach
iteration.
Purpose:
Tofindtheshortestpathtoatargetnodeinanunweightedgraph.
ToensurecompletenessandoptimalitywhileusinglessmemorythanBFS.
5

6. IDDFS ALGORITHM
Overview:
IDDFS involves running a series of depth-limited depth-first searches, increasing the depth limit
incrementally until the goal is found or all nodes are explored.
Steps of the Algorithm:
1.Initialize Depth Limit: Start with a depth limit of 0.
2.Perform Depth-Limited DFS:
a)Use DFS to explore nodes up to the current depth limit.
b)If the goal node is found, terminate the search.
c)If not found, return to the root node.
3.Increment Depth Limit: Increase the depth limit by one.
4.Repeat: Continue until the goal is found or all possible nodes have been explored.
6

7. ADVANTAGES
Completeness:
GuaranteesFindingaSolution:IDDFSiscomplete,meaningitwillfindasolutionifoneexists,evenininfinitestate
spaces.
Optimality:
ShortestPathinUnweightedGraphs:IDDFSfindstheshortestpathtothegoalintermsofthenumberofedges
(depth)whenappliedtounweightedgraphs.
MemoryEfficiency:
LowMemoryUsage:LikeDepth-FirstSearch(DFS),IDDFSuseslinearspace,proportionaltothedepthofthesearch
tree.
Simplicity:
EasytoImplement:IDDFSisrelativelystraightforwardtoimplementusingasimplemodificationofDFStoinclude
depthlimits.
Flexibility:
VersatileinVariousEnvironments:IDDFScanbeadaptedtodifferenttypesofgraphsandsearchproblems,especially
whenmemoryconstraintsareaconcern.
7

8. DISADVANTAGES
oThe time taken is exponential to reach the goal node.
oThe main problem with IDDFS is the time and wasted calculations that take place at
each depth.
oThe situation is not as bad as we may think of especially when the branching factor is
found to be high.
oThe IDDFS might fail when the BFS fails. When we are to find multiple answers from
the IDDFS, it gives back the success nodes and its path once even if it needs to be
found again after multiple iterations. To stop the depth bound is not increased further.
8

9. TIME & SPACE COMPLEXITY
Depth-First Search (DFS):
Time Complexity: O(b^m)
•b is the branching factor (average number of
child nodes per node).
•m is the maximum depth of the search tree.
Breadth-First Search (BFS):
Time Complexity: O(b^d)
•d is the depth of the shallowest solution.
Iterative Deepening Depth-First Search (IDDFS):
Time Complexity: O(b^d)
•Althoughitrepeatedlyvisitsnodes,thenumber
ofvisitsdoesnotchangetheasymptotic
complexitycomparedtoBFS,
Depth-First Search (DFS):
Space Complexity:O(b×m)
Breadth-First Search (BFS):
Space Complexity: O(b^d)
Iterative Deepening Depth-First Search (IDDFS):
Space Complexity: O(b×d)
9

10. EXAMPLES
ArtificialIntelligence:
•GameTreeSearch:IDDFSisusedinAIforsearchinggametrees,suchasinchessorcheckers.
Pathfinding:
•NavigationSystems:IDDFSisappliedinroboticsandautonomousnavigationsystemstofind
maps.
ProblemSolving:
•PuzzlesandMazes:Solvingpuzzleslikethe8-puzzleornavigatingmazes.
SearchinInfiniteStateSpaces:
•TheoreticalComputerScience:IDDFSisusedinalgorithmsthatoperateonpotentiallyinfinitestate
spaces.
TreeTraversal:
•FileSystemSearches:Efficientlysearchingfilesystemsorhierarchicaldatastructureswhere
memoryusageisaconcern.
ArtificialIntelligence:
•GameTreeSearch:IDDFSisusedinAIforsearchinggametrees,suchasinchessorcheckers.
Pathfinding:
•NavigationSystems:IDDFSisappliedinroboticsandautonomousnavigationsystemstofind
maps.
ProblemSolving:
•PuzzlesandMazes:Solvingpuzzleslikethe8-puzzleornavigatingmazes.
SearchinInfiniteStateSpaces:
•TheoreticalComputerScience:IDDFSisusedinalgorithmsthatoperateonpotentiallyinfinitestate
spaces.
TreeTraversal:
•FileSystemSearches:Efficientlysearchingfilesystemsorhierarchicaldatastructureswhere
memoryusageisaconcern.
10

11. CONCLUSION
11
•IterativeDeepeningDepth-FirstSearch(IDDFS)isapowerfulsearchalgorithmthat
combinesthedepth-firstandbreadth-firstapproachestoaddresstheirindividual
limitations.
•IDDFSisbothcompleteandoptimalforunweightedgraphs,andituseslessmemorythan
Breadth-FirstSearch(BFS).
•Despiteitsstrengths,IDDFScanbecomputationallyexpensiveduetotherepeated
explorationofnodes.

12. REFERENCES
www.GeeksforGeeks.com
www.TutorialsPoint.com
www.youtube.com
www.Wikipedia.org
StuartRussellandPeterNorvig,ArtificialIntelligenceBook
SubjectTeacher
12

13. 13