Skip to main content

16. Heuristics and dynamic programming

27/03/23

General Methods​

Various general methods (paradigms) for finding solutions to problems Common ones includes:

  • Brute force - "generate and test"
  • Divide-and-conquer
  • Heuristics
  • Dynamic Programming

Brute Force​

  • Roughly generate and test
    • Generate all potential solutions
    • Test for which ones are actual solutions
  • Can be useful in some (small) cases

Divide and Conquer​

  • Recursively, break the problem into smaller pieces, solve them, and put them back together
  • Merge-sort and quick sort are classic example

Heuristics​

  • Heuristic = rule of thumb
  • Generally, mean to mean something that gives better decisions, than the naive methods, but still not necessarily optimal
  • Two common type (the term is over-loaded)
    • Decisions within a procedure that gives exact/optimal answers are designed to make it go faster
    • Decisions within a procedure that might not give optimal answers, but are designed to give good answers that are impractical to obtain otherwise

In exact methods​

  • General methods that works in an algorithm that does give exact or optimal answers
    • But need the heuristics to decrease the (average/typical) runtime
    • Examples = Admissible heuristic in A* search

Inexact Methods​

  • These are general methods that (generally) are not be guaranteed to give the best possible answer, but that can give good answers quickly
  • Used on problems when the exact methods are too slow
  • It is a vast research area

Greedy Algorithms​

  • Common heuristic is to be greedy
  • Take the decision that looks best in the short term - without looking ahead

Optimal​

  • Sometimes greedy algorithms can still give optimal answers
  • Prims algorithm for constructing a minimal spanning tree is a greedy algorithm:
    • Just adds the shortest edge without worrying about the overall structure, without looking ahead
    • Makes a locally optimal choice at each step
    • Turns out that this is sufficient for the final answer to be optimal

Non-optimal​

  • Usually greedy algorithms cannot guarantee to give optimal answers
  • Often still give (nearly) optimal answers in practice

Dynamic Programming​

  • DP is a general method that can be suitable when the optimal solutions satisfy a decomposition property
  • General idea is roughly:
    • Splitting an optimal solution into sub-solutions corresponds to splitting the problem into sub-problems and the sub-solutions are optimal for the sub-problems
    • So optimal solutions can be built out of optimal solutions of (smaller) sub-problems
    • Hence: solve small sub-problems first, then build up towards the full solution