Intelligent Systems Lecture Notes

16 September 2011 • Search Refinements

---

Outline

• A bunch of tricks.
  • Avoiding cycles.
  • Don't waste your time: pruning.
  • Small steps: iterative deepening.
  • Cutting your losses: branch and bound.
  • Go with (or against) the flow: search direction.
  • The power of intermediate results: dynamic programming.

The Cycle Problem

Cycles trap some searches; other searches waste resources in them. Searching works best (is most efficient and effective) on acyclic problems. Unfortunately, many problems are naturally cyclic.

• Now the task becomes dealing with cycles.

Breaking Cycles

• Eliminating paths with cycles is easy:

  for n in p.nextStates(s)
    if not path.member(n)
      paths.push(path.copy().add(n))
  

• Sometimes each vertex can have a visited bit instead of searching the path.

  for n in p.nextStates(s)
    if not n.visited
      n.visited = true
      paths.push(path.copy().add(n))
  

Redundant Paths

A problem may have several ways to reach a state. And the particular path to a state is unimportant. In such cases, it doesn't make sense to visit a vertex more than once.

• Visiting a vertex for the first time removes it (prunes it) from the graph for further visits.

Path Pruning

• A redundant path looks like an undirected cycle, and should be treated like one, more or less.
  • Old vertices may not be in the current path.

  path = paths.pop()
  s = path.tail()
  if visited.member(s)
    continue
  visited.add(s)
  if p.goalState(s)
  

Too Far Too Fast

DFS takes linear space, but may not find a solution. BFS takes exponential space, but finds a solution.

• How can DFS and BFS be cross-bread to produce a linear, successful search?
  • What is the secret of BFS's success, and can DFS use the secret?

Adventures Close to Home

BFS examines all paths of length i before any path of length i + 1.

• Constrain DFS to search every path of length i before it searches any path of length i + 1.
• This is known as iterative deepening.
  • It is a general technique, applicable to more than DFS.

Constrained DFS

• Constrained DFS (CDFS) can fail in two ways:
  1. Run out of vertices to search (vertices exhausted).
  2. Run out of path length to search (length exhausted).
• When vertices are exhausted, the search fails.
• When length's exhausted, rerun the search with length i + 1.

Cutting Your Losses

Some problems want a constrained-cost solution. Which usually means finding all solutions. Suppose that all costs are non-negative.

• What do you know about any solution found from v?

Branch and Bound

• If a solution costs C, than any other useful solution should cost no more than C (for example).
  • Any partial solution costing at least C can be pruned.
• This is the basis for branch and bound algorithms.

Search Direction

• Searching forward goes from initial to goal states.
• Searching backward goes from goal to initial states.
• Sometimes searching backwards is easier than searching forwards.
  • Vertices with high out degree but low in degree have fewer choices to make searching backwards.
• Program structure may favor one search direction over another.

Dynamic Programming

• Intermediate results during a search represent information to be exploited by the search.
• Intermediate results can often be precomputed and used during the search.
• Dynamic programming is a common technique for precomputing partial results.
  • Dynamic programming itself exploits partial information.
  • And frequently works backward from the solution.

Summary

• These tricks are general purpose, widely applicable.
• Iterative deepening and depth-first branch-and-bound searches generate exploitable information while they work.
• Dynamic programming solves small problems and calculates good heuristics for large problems.

References

• Search and Computational Complexity in IS (Chapter 3) in Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2009.

---

This page last modified on 2011 September 15.