Computer Algorithms II Lecture Notes

2 October 2008 • Heuristics

---

Outline

• Exhaustive search and greed.

• Costs and correctness.

• Heuristics

  • Heuristic algorithms

  • Approximation algorithms

  • Average-case algorithms

  • Heuristic tricks

A Problem

• A county has n towns, each town has a school.

• Consolidate schools such that each town is within 30 miles of a school.

• Minimize the number of schools.

  

Exhaustive Search

consolidation(towns)

  schools = { }
  
  for i = 2towns.size() - 1 to 0 do
    s = subset(i, towns)
    if covers(s, towns) 
       s.size() < schools.size()
      schools = s

  return schools

• 40 towns, 1 nsec/check, 10₃ sec total. Problem solved!

Oops

• Monmouth County has 237 populated places.

Greed

• Find all neighbors within 30 miles of each town t.

• Arrange the towns in descending order by neighborhood size.

  consolidation(towns)
  
    schools = covered = { }
  
    for i = 1 to towns.size()
      schools U= { towns[i] }
      covered U= { towns[i].neighbors }
      if covered = towns 
        break
  
    return schools
  

Greed Costs

• Finding neighbors: O(n²).

• Ordering towns: O(n log n).

• Set manipulations: O(n).

• Loop: O(n²).

Does Greed Work?

• Are locally optimally choices globally optimal?

  • Nope.

• Are subproblems optimal?

  • Nope.

How Bad Is It?

• Greed doesn't work, but how badly doesn't it work?

  • In this case it's O(log n) off optimal.

• Bounding the difference between optimal and sub-optimal solutions isn't always possible.

Heuristics

• Many important problems are intractable.

• Exhaustive search is too expensive for many of those problems.

• Greed may not work.

• What to do? These problems need to be solved.

The Problem

• What exactly is the problem?

• Exhaustive search for an optimal solution is too expensive.

• Trade-off cost for quality: quickly produce a sub-optimal answer.

Heuristics

• Heuristic methods produce non-optimal solutions quickly.

• There are lots of different heuristic methods.

  • Heuristic algorithms.

    • Approximation algorithms.

  • Heuristic tricks applied to heuristic algorithms.

  • Average-case algorithms.

Heuristic Algorithms

• Heuristic algorithms solve the problem, but not optimally.

Approximation Algorithms

• An approximation algorithm is a heuristic algorithm that has a bounded amount of badness.

Example

• The greedy solution to consolidation comes to within an O(log n) factor of optimal.

Average-Case Algorithms

• Average case algorithms work well , but may be bad (intractable) in the extremes.

  • Quicksort, ignoring the O(n²) worst case.

Heuristic Tricks

• Little tricks that can be added to algorithms to improve performance, in most cases.

  • Particularly helpful for average-case algorithms.

Examples

• Racing: run two or more heuristic algorithms and take the best one.

• Sorting: order the input in some way to force good behavior.

• Capping: stop when an answer's close enough.

• Pruning: dynamic capping; don't pursue partial answers that are worse than the current best answer.

  • Branch and bound: keep several options open; pursue the best on at any moment.

• Postprocessing: take a sub-optimal answer and diddle with it to try and make it better.