Lecture Notes for CS 512, Algorithm Design

22 March 1999, Exhaustive Search and Heuristics

1. intractable problems still need to be solved

   1. exponential algorithms run on small or average cases

   2. polynomial algorithms to give non-optimal results - heuristic algorithms

   3. heuristic algorithms giving boundedly non-optimal results

2. using intractable algorithms

   1. for small inputs, the algorithm may be fast enough

   2. backtracking algorithms

      1. make a guess and see what happens

      2. on failure backtrack to the most recent guess and try again

      3. set partition

      4. branch and bound

      5. exhaustive search

3. using heuristics - rules of thumb

   1. out of all possible next choices, take the best one - greed

      1. sometimes greed is optimal - dikjstra's shortest path; prim's or kruskal's mst algorithm

      2. sometimes greed is good or bad - knapsack packing

This page last modified on 24 March 2000.