Brian Williams, Spring 03 1Analysis of Uninformed Search MethodsBrian C. Williams16.410 Feb 18th, 2003Slides adapted from:6.034 Tomas Lozano Perez,Russell and Norvig AIMABrian Williams, Spring 03 2Assignment• Reading: – Solving problems by searching: AIMA Ch. 3– Informed search and exploration: AIMA Ch. 4.1-2• Homework:– Online problem set 2 due next Monday Feb 24thBrian Williams, Spring 03 3Outline• Recap• Analysis– Depth-first search– Breadth-first search• Iterative deepeningBrian Williams, Spring 03 4Complex missions must carefully:• Plan complex sequences of actions• Schedule tight resources• Monitor and diagnose behavior• Repair or reconfigure hardware.ð Most AI problems, like these, may be formulated as state space search.Brian Williams, Spring 03 5AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAstronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAstronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautAstronautGooseGrainFox• Formulate Goal• Formulate Problem– States– Operators• Generate Solution– Sequence of statesProblem Solving Searches Paths in a GraphBrian Williams, Spring 03 6Depth First Search (DFS)SDBAC GC GDC GSDBAC GC GDC GBreadth First Search (BFS)Depth-first:Add path extensions to front of QPick first element of QBreadth-first:Add path extensions to back of QPick first element of QBrian Williams, Spring 03 7Simple Search AlgorithmLet Q be a list of partial paths, Let S be the start node and Let G be the Goal node.1. Initialize Q with partial path (S) as only entry; set Visited = ( )2. If Q is empty, fail. Else, pick some partial path N from Q3. If head(N) = G, return N (goal reached!)4. Elsea) Remove N from Qb) Find all children of head(N) not in Visited and create all the one-step extensions of N to each child.c) Add to Q all the extended paths; d) Add children of head(N) to Visitede) Go to step 2.Brian Williams, Spring 03 8Outline• Recap• Analysis– Depth-first search– Breadth-first search• Iterative deepeningBrian Williams, Spring 03 9Elements of Algorithmic Analysis• Soundness: – is a solution returned by the algorithm guaranteed to be correct?• Completeness: – is the algorithm guaranteed to find a solution when there is one?• Optimality:– is the algorithm guaranteed to find a best solution when there is one?• Time complexity: – how long does it take to find a solution?• Space complexity: – how much memory does it need to perform search?Brian Williams, Spring 03 10Characterizing Search Algorithmsd = 1Level 1Level 2Level 0b = 3b = maximum branching factor, number of childrend = depth of the shallowest goal nodem = maximum length of any path in the state spacem = 1Brian Williams, Spring 03 11Cost and PerformanceBreadth-firstDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWhich is better, depth-first or breadth-first?Worst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QSDBAC GC GDC GCSBGADBrian Williams, Spring 03 12Worst Case Time for Depth-firstWorst case time T is proportional to number of nodes visitedTdfs= bm+ … b + 1b * Tdfs= bm+1 + bm+ … b Solve recurrence[b – 1] * Tdfs= bm+1– 1Tdfs= [bm+1– 1]/[b – 1] *cdfswhere cdfsis time per nodeLevel 1Level 2Level 0b*1b*bb*bm-1. . .Level m1Brian Williams, Spring 03 13Cost Using Order NotationWorst case time T is proportional to number of nodes visitedLevel 1Level 2Level 0b*1b*bb*bm-1. . .Order Notation• T = O(e) if T = c * e for some constant cTdfs= [bm+ … b + 1]*cdfs= O(bm) for large b= O(bm+1) more conservatively1Brian Williams, Spring 03 14Cost and PerformanceBreadth-firstbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWhich is better, depth-first or breadth-first?Worst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QSDBAC GC GDC GCSBGADBrian Williams, Spring 03 15Worst Case Space for Depth-firstWorst case space Sdfsis proportional to maximal length of Q• If a node is queued its parent and parent’s siblings have been queued. è Sdfs= (b-1)*m+1 The children of at most one sibling is expanded at each level. è Sdfs= (b-1)*m+1• Sdfs= O(b*m)Level 1Level mLevel 0b-1b-1b. . .Brian Williams, Spring 03 16Cost and PerformanceBreadth-firstb*mbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWorst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QWhich is better, depth-first or breadth-first?SDBAC GC GDC GCSBGADBrian Williams, Spring 03 17Cost and PerformanceBreadth-firstNob*mbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWorst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QWhich is better, depth-first or breadth-first?SDBAC GC GDC GCSBGADBrian Williams, Spring 03 18Cost and PerformanceBreadth-firstYes for finite graphNob*mbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWorst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QWhich is better, depth-first or breadth-first?SDBAC GC GDC GCSBGADBrian Williams, Spring 03 19Cost and PerformanceBreadth-firstYes for finite graphNob*mbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodSDBAC GC GDC GWorst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QWhich is better, depth-first or breadth-first?CSBGADBrian Williams, Spring 03 20Worst Case Time for Breadth-firstWorst case time T is proportional to number of nodes visitedLevel 1Level dLevel 0Tbfs= [bd+1+ bd+ … b + 1 - b]*cbfs= O(bd+1)Level d+1bbd+1- b. . .1bdBrian Williams, Spring 03 21Cost and Performancebd+1Breadth-firstYes for finite graphNob*mbmDepth-firstGuaranteed tofind path?ShortestPath?WorstSpaceWorstTimeSearchMethodWorst case time is proportional to number of nodes visitedWorst case space is proportional to maximal length of QSDBAC GC GDC GWhich is better, depth-first or breadth-first?CSBGADBrian Williams, Spring 03 22Worst Case Space for Breadth-firstLevel 1Level dLevel 0Sbfs= [bd+1- b + 1]*cbfs=