Analysis of Uninformed Search methods Brian C Williams 16410-13 Slides adapted from Sept.17,2003 6.034 Tomas Lozano perez, Russell and Norvig AIMA Sian willams, Spring o3 Outline Analysis Depth-first search Breadth-first search · Iterative deepening williams, Spring a3
1 Brian Williams, Spring 03 1 Analysis of Uninformed Search Methods Brian C. Williams 16.410-13 Sept. 17, 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Russell and Norvig AIMA Brian Williams, Spring 03 7 Outline • Analysis – Depth-first search – Breadth-first search • Iterative deepening
Elements of Algorithmic analysis · Soundness is a solution returned by the algorithm guaranteed to be Completeness is the algorithm guaranteed to find a solution when there is Time complexity how long does it take to find a solution? Space complexity how much memory does it need to perform search? Sian willams, Spring o3 Characterizing Search algorithms Level o Level 1 Level 2 b= maximum branching factor, number of children d= depth of the shallowest goal node m= maximum length of any path in the state space williams, Spring a3
2 Brian Williams, Spring 03 8 Elements 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? • 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 9 Characterizing Search Algorithms d = 1 Level 1 Level 2 Level 0 b = 3 b = maximum branching factor, number of children d = depth of the shallowest goal node m = maximum length of any path in the state space m = 1
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad williams, Spring a3
3 Brian Williams, Spring 03 10 Cost and Performance Breadth-first Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Which is better, depth-first or breadth-first? Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 11 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Tdfs = bm + … b + 1 Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1
Cost Using Order notation Worst case time T is proportional to number of nodes visited evel 1 b*1 b*b Level 2 Order Notation ·T=Oe)ifT≤c* e for some constant c Ts=[bm+…b+lcds O(bm) for large b O(bm+) more conservatively Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad b* Tas=bmt Tas=[bm-1][b-1]*c where caf is time per node williams, Spring a3
4 Brian Williams, Spring 03 12 Cost Using Order Notation Worst case time T is proportional to number of nodes visited Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Order Notation • T = O(e) if T ≤ c * e for some constant c Tdfs = [bm + … b + 1]*cdfs = O(bm) for large b = O(bm+1) more conservatively 1 Brian Williams, Spring 03 13 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Tdfs = bm + … b + 1 b * Tdfs = bm+1 + bm + … b Solve recurrence [b – 1] * Tdfs = bm+1 – 1 Tdfs = [bm+1 – 1] / [b – 1] *cdfs where cdfs is time per node Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? b Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Worst Case Space for Depth-first Worst case space Sas is proportional to maximal length of Q Level m 0○b1 If a node is queued its parent and parents siblings have been queued Ss≥(b-1)*m+1 The children of at most one sibling is expanded at each level 少Sa5=(b-1)m+1 Sat =o(b*m) williams, Spring a3 5
5 Brian Williams, Spring 03 14 Cost and Performance Breadth-first b Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Which is better, depth-first or breadth-first? Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 15 Worst Case Space for Depth-first Worst case space Sdfs is 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 1 Level m Level 0 b-1 b-1 b . .
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Space Path? find path? Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? Method Time Space Path? find path? Depth-first b"m Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian willams, Spring (3
6 Brian Williams, Spring 03 16 Cost and Performance Breadth-first Depth-first bm b*m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 17 Cost and Performance Breadth-first b b*m No Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Depth-first b*m Yes for finite graph Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? (D G Method Time Space Path? find path? b"m Yes for finite graph Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian willams, Spring (3
7 Brian Williams, Spring 03 18 Cost and Performance Breadth-first b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 19 Cost and Performance Breadth-first b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method S D A B C G C G D C G Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? C S B G A D
Worst case time for Breadth-first Worst case time T is proportional to number of nodes visited Level 1 b Level d Level d+1 b+1-b Tbs=[b+l+ bd+.b+1-b]cbts Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? (D G Method Time Space Path? find path? b"m Yes for finite graph Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q
8 Brian Williams, Spring 03 20 Worst Case Time for Breadth-first Worst case time T is proportional to number of nodes visited Level 1 Level d Level 0 Tbfs = [bd+1 + bd + … b + 1 - b]*cbfs = O(bd+1) Level d+1 b bd+1- b . . . 1 bd Brian Williams, Spring 03 21 Cost and Performance b Breadth-first d+1 b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G Which is better, depth-first or breadth-first? C S B G A D
Worst Case Space for Breadth-first Worst case space Sas is proportional to maximal length of Q evel 0 Level 1 b Level d Level d+1 b+1-b Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? (D G Method Time Space Path? find path? b"m Yes for finite graph Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian willams, Spring (3
9 Brian Williams, Spring 03 22 Worst Case Space for Breadth-first Level 1 Level d Level 0 Sbfs = [bd+1- b + 1]*cbfs = O(bd+1) Level d+1 b bd+1- b . . . 1 bd Worst case space Sdfs is proportional to maximal length of Q Brian Williams, Spring 03 23 Cost and Performance bd+1 b Breadth-first d+1 b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G Which is better, depth-first or breadth-first? C S B G A D
Breadth-first Finds shortest path Nodes visited earlier cant include g evel 0 Level 1 Level d Level d+1 Assuming each edge is length 1 other paths to g must be at least as long as first found Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? (D G Method Time Space Path? find path? b"m Yes for finite graph Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q 10
10 Brian Williams, Spring 03 24 Breadth-first Finds Shortest Path G Level 1 Level d Level 0 Level d+1 G First reached Nodes visited earlier can’t include G Assuming each edge is length 1, other paths to G must be at least as long as first found Brian Williams, Spring 03 25 Cost and Performance b Yes unit lngth d+1 b Breadth-first d+1 b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G Which is better, depth-first or breadth-first? C S B G A D