Search Strategies - Manhattan College

Search Strategies CMPT 420 / CMPG 720 Uninformed Search Strategies Uninformed search strategies use only the information available in the problem definition Breadth-first search Uniform-cost search

Depth-first search Depth-limited search Iterative deepening search Breadth-first search Expand shallowest unexpanded node 4 Breadth-first search Expand shallowest unexpanded node

5 Breadth-first search Expand shallowest unexpanded node 6 Breadth-first search Expand shallowest unexpanded node Examine siblings before children

7 Breadth-first search Expand shallowest unexpanded node Implementation: o Frontier is a FIFO queue, i.e., new successors go at end 8 Example: Romania

11 Graph Representation Adjacency list representation of G = (V, E) o An array of V lists, one for each vertex in V o Each list Adj[u] contains all the vertices v such that there is an edge between u and v Adj[u] contains the vertices adjacent to u (in arbitrary order) o Can be used for both directed and undirected graphs

1 2 3 5 4 Undirected graph

1 2 5 2 1 5

3 2 4 4 2

5 3 5 4 1 2

/ 4 3 / / 12

Graph Representation Adjacency matrix representation of G = (V, E) o Assume vertices are numbered 1, 2, V o The representation consists of a matrix A V x V : o aij = 1 if (i, j) E 0 1

otherwise 2 3 5 4 Undirected graph

1 2 3 4 5

1 0 1 0 0 1

2 1 0 1 1

1 3 0 1 0 1

0 4 0 1 1

0 1 5 1 1 0

1 0 For undirected graphs matrix A is symmetric: aij = aji

A = AT 13 Breadth-first search Is BFS guaranteed to find a solution if one exists? Breadth-first search Is BFS guaranteed to find a solution if one

exists? Problem? Breadth-first search Guaranteed to find a solution if one exists Problem: it might take a very long time to find a solution! o note how much of tree is expanded that doesn't contribute towards goal

Properties of breadth-first search Complete? o Yes Optimal? Time? Space? 17

Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step) Time? Space? 18

Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step) Time? o 1+b+b2+b3+ +bd = O(bd) o exponential in d

Space? 19 Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step)

Time? o 1+b+b2+b3+ +bd = O(bd) o exponential in d Space? o O(bd) (O(bd-1) nodes in the explored set and O(bd) nodes in the frontier) 20

Uniform-cost search Expand the node with the lowest path cost g(n) (Cheapest search) Implementation: 21 Uniform-cost search Expand the node with the lowest path cost g(n) (Cheapest search) Implementation:

o Frontier = priority queue ordered by path cost g(n) 22 Example: Romania 23 Properties of uniformcost search Equivalent to breadth-first if step costs all equal

Complete? o Yes Optimal? o Yes nodes expanded in increasing order of path cost Time? o O(bd) Space?

o O(bd) Depth-first search Expand deepest unexpanded node 25 Depth-first search Expand deepest unexpanded node

26 Depth-first search Expand deepest unexpanded node Examine children before siblings 27 Depth-first search Expand deepest unexpanded node Examine children before siblings

28 Depth-first search Expand deepest unexpanded node Examine children before siblings 29 Depth-first search Expand deepest unexpanded node

Examine children before siblings 30 Depth-first search Expand deepest unexpanded node Examine children before siblings 31 Depth-first search

Expand deepest unexpanded node Examine children before siblings 32 Depth-first search Expand deepest unexpanded node Examine children before siblings 33

Depth-first search Expand deepest unexpanded node Examine children before siblings 34 Depth-first search Expand deepest unexpanded node Examine children before siblings 35

Depth-first search Expand deepest unexpanded node Implementation: o Frontier = LIFO queue 36 Depth-first search

Example More efficient (in some cases) than breadth-first search o Problem: what if some branch is very long: can spend a lot of time searching useless cases Properties of depth-first search Complete? o Yes (if every branch has finite number of

states) Optimal? o No 39 search Complete? o Yes (if every branch has finite number of states) Optimal?

o No Time? o O(bm): terrible if m is much larger than d o but if solutions are dense, may be much faster than breadth-first 40 Comparing Uninformed Search Strategies

Time and space complexity are measured in o b maximum branching factor of the search tree o m maximum depth of the state space o d depth of the least cost solution search Complete? o Yes (if every branch has finite number of states) Optimal? o No

Time? o O(bm): terrible if m is much larger than d o but if solutions are dense, may be much faster than breadth-first Space? o O(bm), i.e., linear space! 42

Depth-limited search Depth-first search with depth limit l, i.e., nodes at depth l have no successors 20 cities in map of Romania o l =19 Any city can be reached from any other city in at most 9 steps. o Diameter gives a better depth limit. Properties of

Depth-limited search Complete? o Yes (if the goal is within the limit) Optimal? o No Time? o O(bl) Space? o O(bl)

44 Properties of Depth-limited search Depth-first search can be viewed as a special case with l = infinity Main advantage that the search process can't descend forever (in a branch without solution). However, it will not find a solution if all

solutions require a depth greater than the limit. o (This is likely when l is unknown.) How to overcome this and maintain the advantages of depth limited search? Iterative deepening search Gradually increases the limit 0, 1, 2, If don't find solution, increase depth and

try again Combines the benefits of depth-first and breadth-first search. Iterative deepening search l =0 48 =1

49 =2 50 =3 51 Properties of iterative

deepening search Complete? o Yes Optimal? o Yes, if step cost = 1 Space? o O(bd), linear space Time?

o d b1 + (d-1)b2 + + (1)bd = O(bd) 52 Time consuming?? Can show this doesn't really increase the number of examined nodes by much over depth-first search: o For large graphs, "most" of the nodes are at the outermost edge

o If branching factor is b, then there are b2 nodes in the 2nd layer, b3 in the 3rd, bn in the nth o Thus number of nodes at depth d is 1 + b + b2 + b3 + ... + bd o If d =4, b =10, get 1 + 10 + 102 + 103 + 104 = 11,111 nodes o For iterative deepening, need to consider some nodes more than once: b(d) + b2(d - 1) + b3(d - 2) + ... + bd o d = 4, b = 10 gives 1*(4 + 1) + 10 * 4 + 102 * 3 + 103 * 2 + 104 =

12,345 visitations: a 10% increase o in general, if branching factor is 10, visit nodes 11% more often by iterative deepening Properties of iterative deepening search Combines the benefits of depth-first search o Memory space O(bd) o linear!

breadth-first search o Always complete and optimal Search Start the process simultaneously from the initial start and backwards from the goal state whether the frontiers of the two intersect To reduce the complexity

bd/2 + bd/2 < bd

Recently Viewed Presentations

  • IS 651: Distributed Systems

    IS 651: Distributed Systems

    Document Type Definition (DTD) The declaration of the DTD in the XML document has the syntax where SYSTEM refers to that fact that the DTD is a private implementation for this document rather than a standard. It would change to...
  • Introduction to Practice Education

    Introduction to Practice Education

    All assessment material pertaining to each placement along with module descriptors is accessible to the student on each practice education module MOODLE page. Prepare and send an introductory email to the appropriate practice education coordinator . not less than five...
  • Menopausal Hormone Replacement Professor Gordana Prelevic, MD, DSc,

    Menopausal Hormone Replacement Professor Gordana Prelevic, MD, DSc,

    Menopausal Hormone Replacement Professor Gordana Prelevic, MD, DSc, FRCP Consultant Endocrinologist Royal Free Hampstead NHS Trust Whittington Health
  • February PM Power Talk

    February PM Power Talk

    February PM Power Talk. At the end of this training, you will understand… what's new: Project Dashboard. what's updated: One Line Diagram & WIP Tracker Clarification
  • The Structure of Language The study of phonetics

    The Structure of Language The study of phonetics

    (plural vs. singular). Languages vary a lot in what kinds of things there needs to be agreement on. Not all languages enforce agreement on number, but . all except a very few languages incorporate lots of agreement rules.
  • An introduction to systems thinking and tools for

    An introduction to systems thinking and tools for

    go beyond range of any one organization to manage them . are often characterised by disagreement about causes, and how to tackle them. recognise the need to change behaviour or practice at multiple levels and scales (individuals to organizations) require...
  • Strategic Management- Chapter Two

    Strategic Management- Chapter Two

    Identify the five competitive forces and explain how they determine an industry's profit potential. Define strategic groups and describe their influence on the firm. Describe what firms need to know about their competitors and different methods (including ethical standards) used...
  • Contaminación Atmosférica: Causas Y Riesgos Para Medellín

    Contaminación Atmosférica: Causas Y Riesgos Para Medellín

    Al mismo tiempo, sin embargo, han ocasionado también problemas y riesgos que requieren un análisis serio y exhaustivo. El aumento de la contaminación, el uso de sustancias tóxicas, el deterioro progresivo del medio ambiente, la desertización, el empobrecimiento de la...