Outline
  
  -  General search.
  
-  Uninformed search.
      
      -  Depth-first search.
      
-  Breadth-first search.
      
-  Lowest-cost-first search.
      
 
-  Heuristics and A* searching.
  
A State-Space Interface
interface Problem 
  abstract class State { }
  Set<State> initialStates()
  Boolean isGoalState(State s)
  Set<State> nextStates(State s)
  double moveCost(State from, State to)
  
A State-Space Search Interface
interface StateSpaceSearch
  interface SolutionPath 
  extends Queue<Problem.State>
  SolutionPath search(Problem problem)
  interface Comparison
    boolean isBetterThan(
      SolutionPath a, SolutionPath b)
  SolutionPath search(
    Problem problem, Comparison c)
  
Simple Search
  
Simple Search Problems
  
  -  Only answers the question “is there a solution?”, not “how
  is the problem solved?”.
  
-  Doesn’t handle infinite state sets well.
  
-  Doesn’t handle constrained solutions well.
    
    -  Cheapest, fastest, best after no more than five minutes work. 
    
 
-  Wasteful of information, and hard to improve.
  
Improving Search
  
  -  Improving search—improving
  anything—involves exploiting information.
  
  
Graph Search
SolutionPath search(Problem problem)
  Set<Path> pendingPaths = initialPaths(problem)
  while !pendingPaths.isEmpty()
    Path path = pick(pendingPaths)
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if problem.isGoalState(neighbor)
	return newPath
      pendingPaths.add(newPath)
  return new Path()
  
Observations
  
  -  The search exploits some of the graph structure.
    
    -  Answering the “if solvable” and “solved how” questions. 
    
 
-  The search is nondeterministic.
Path path = pick(pendingPaths)
for Problem.State neighbor : 
    problem.moveResults(path.lastState())
 
   
-  The other problems remain.
  
Graph Optimal Search
SolutionPath search(Problem problem, Comparison c)
  SolutionPath bestSolution = new Path()
  Set<Path> pendingPaths = initialPaths(problem)
  while !pendingPaths.isEmpty()
    Path path = pick(pendingPaths)
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if    problem.isGoalState(neighbor)
         && c.isBetterThan(newPath, bestSolution)
	bestSolution = newPath
      pendingPaths.add(newPath)
  return bestSolution
  
Depth-First Search
SolutionPath search(Problem problem)
  Stack<Path> pendingPaths = initialPaths(problem)
  while !pendingPaths.isEmpty()
    Path path = pendingPaths.pop()
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if problem.isGoalState(neighbor)
	return newPath
      pendingPaths.push(newPath)
  return new Path()
Breadth-First Search
Queue<Problem.State> solve(Problem p)
  paths = 
    Queue(Queue(s | s ∈ p.startStates()))
  while !paths.empty()
    path = paths.get()
    s = path.tail()
    if p.goalState(s)
      return path
    for n in p.nextStates(s)
      paths.put(path.copy().add(n))
  return Queue()
Uninformed Searches
  
  -  Depth- and breadth-first searches are relatively uninformed.
    
    -  They use graph information, but not problem information.
    
 
-  Edge costs are the most commonly exploited problem information.
    
    -  Assuming the edge costs are non-negative. 
    
 
-  Even if not required, finding a minimum-cost solution avoids problems.
  
Least-Cost-First Search
Queue<Problem.State> solve(Problem p)
  paths = 
    MinQueue(Queue(s | s ∈ p.startStates()))
  while !paths.empty()
    path = paths.get()
    s = path.tail()
    if p.goalState(s)
      return path
    for n in p.nextStates(s)
      paths.put(path.copy().add(n))
  return Queue()
Observations
  
  -  LCF search is BFS with a min priority queue over path costs.
  
-  LCF search returns optimal (minimal) solutions.
  
-  LCF search doesn’t get trapped in infinite loops.
    
    -  But they can slow the algorithm down. 
    
 
-  A similar trick can be applied to DFS, but is 
much less effective.
  
Heuristics
  
  -  Searches can also exploit goal information.
    
    -  Either the goals themselves or their characterization.
    
 
-  A heuristic is an estimate (guess) of the “distance”
  between a state and a goal.
  
A* Search
  
  -  A* search is a variation on LCF search.
  
-  Given a heuristic function h, define the total cost estimate
  T as
T(v0, …, vk) = C(v0, …, vk) + h(vk).
 
-  The min priority queue orders paths on T.
  
  
Comparing Searches
  
  -  Searches can be compared on resources (time or space) taken, or results
  produced (quality or accuracy).
    
  
-  Resources used can be estimated via asymptotics or measured in
  execution. 
    
    -  Worst-case (Big-O) asymptotic estimates. 
    
 
Summary
  
  -  Breadth- and depth-first search use minimal problem information to find
  solutions.
  
-  A* search uses a cost-to-goal heuristic to improve searching.
  
-  Improve searching (or anything) by exploiting more and better
  information.
    
    -  Often the information’s available for free.
    
 
-  If information’s not available or too expensive, make good guesses
  using heuristics.
  
References
  
  -  Search and Computational Complexity in IS (Chapter 3) in
  Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2009.
  
Credits
  
  
  | This page last modified on 2011 September 15. | 
      |