Lecture Notes for Algorithm Design

Heuristic Algorithms, 21 October 1999

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 4 November 1999.