Catch multiple pieces of cheese… more efficiently

Project – Session 5

  • Heuristics
  • Greedy algorithms
  • Approximate solutions

Heuristics

Need for a trade-off

What’s a good heuristic?

  • Provide a gain
  • Limited complexity

Greedy algorithms

Principle

  • Global optimization – Find the minimum path that goes through all vertices
  • Greedy approximation – Find a series of minimum subpaths (next one, 2 following ones, etc.)

Approximate solutions

How to characterize them

Approximate solutions

Important aspects

Speed and correctness

  • If finding an approximate solution is as long as finding the exact solution, well…
  • Compare estimation with known solutions or small instances

Recap of the session

Main elements to remember

  • Sometimes, problem are too hard to solve

  • Approximate solutions can be found in shorter time as an alternative

  • Greedy approaches can provide good approximate solutions

  • Heuristics encode an intuition, e.g, what to minimize in a greedy algorithm

  • A good heuristic should provide a gain and be of limited complexity

Recap of the session

What’s next?

Practical activity (~2h30)

Catch multiple pieces of cheese… faster

  • Program a greedy algorithm
  • Test multiple heuristics

After the session

  • Review the articles of the session
  • Check your understanding with the quiz
  • Complete the practical activity
  • Check next session’s “Before the class” section

Evaluation

  • Evaluated quiz to start next session!
  • Deliverable for session 5 (check session page for details)