Travelling Salesman Variation

47 Views Asked by At

Is there a name for this variation and a recommended algorithm for solving this problem:

  • You have a large boat with many leaks on it.
  • As soon as you patch a leak, it resets, and slowly begins leaking again gradually over time at a higher and higher flow rate.
  • Each leak has a varying rate at which it increases flow, but you know what this rate is for each leak.
  • You can instantly patch a leak by visiting it, but it takes you time to move between leaks.

Over the course of a day, how can you minimize the amount of water let into your boat?