[L03] Uninformed Searches - ATPAustinPeng/cs3600 Wiki

Uninformed Searches

Problem Formulation For Search

  • initial state
  • transition model
  • goal test
  • path cost

Generalized Tree Search

  • initial state: root node
  • transition model: node expansion
  • goal test: node test
  • path cost: path cost in tree (sum of path from root to final node)

Node Representation In Tree Search

  • state this node represents
  • parent node that generated this node
  • action that generated this node
  • cost of path from root to this node
  • depth of path from root to this node
  • ex. graph with nodes A, B, C, D
    • state: E
    • parent: A (generated B), B (generated D)
    • action A to B, B to D
    • cost: 2
    • depth: 2

General Tree Search Algorithm

TreeSearch(problem) returns solution
	frontier = {problem.initial_state}
		if empty(frontier) return failure
			select leaf node, remove from frontier
		if node.contains(problem.goal)
			return node.solution
		node.expand(), add children to frontier
  • frontier is implemented as a queue

Evaluating Search Algorithms

  • completeness: guaranteed to find a solution if one exists
  • optimality: guaranteed to find the solution with lowest path cost
  • time complexity: number of nodes generated
  • space complexity: size of tree stored in memory

Uninformed Search

  • breadth-first search
  • uniform-cost search
  • depth-first search
  • depth-limited search
  • iterative-deepening search
  • uninformed search: search method uses only information from the problem

Breath-First Search

  • FIFO queue (showing items in queue over each iteration, use alphabetical order for tie-breaker)

    • A
    • B C
    • C D E
    • D E F G
  • implementation: FIFO (first-in-first-out) queue

  • complete: yes, will find shallowest goal node

  • optimal: yes, if all actions have the same cost then shallowest node will have lowest path cost

  • time complexity - in the above example, 2 - in general, b + b^2 + b^3 + ... = O(b^{d + 1})

  • space complexity

    • O(b^d) since entire frontier is kept in memory
  • Note: b = branching factor

  • Note: time and space scale exponentially with the problem size d (the depth of the shallowest solution)

    • if b = 10 (every parent has 10 children) and we can evaluate 100M nodes/second, then it would take 2.7 hours to find a solution 11 levels deep
    • ex. only 11 moves ahead in a game-playing application

Uniform-Cost Search

  • priority queue (sorts elements by cost, low to high)

    • A(0)
    • C(5) B(10)
    • F(2+5) B(10) G(5 + 6)
    • ...
  • implementation: priority queue ordered by path cost

  • complete: yes, if there are no zero cost solutions

  • optimal: yes

  • time complexity

    • in the above example, 2
    • O(b^{1+(C* / e)})
      • where C* is the path cost of the optimal solution
  • space complexity

    • C* / e is the worst case depth (expected depth because solution is optimal)
  • Note: b = branching factor

  • Note: e = minimum cost for any action

Depth-First Search

  • LIFO queue (showing items in queue over each iteration, push parent's children into queue in front of other nodes)

    • A
    • C B
    • G F B
    • I H F B
  • implementation: LIFO (last-in-first-out) queue

  • complete: no, infinite loops are possible using tree-search (cycles within the graph, tree of infinite depth)

  • optimal: no, can select a deep solution over a more shallow one

  • time complexity: O(b^m), can be larger than the size of state space

  • space complexity: O(bm), linear in space, huge improvement over breadth-first

  • Note: m = maximum depth of tree

⚠️ **GitHub.com Fallback** ⚠️