Hacker News new | ask | show | jobs
by akoboldfrying 453 days ago
If there is only one fridge, the solution that minimises total distance travelled is trivial: Move Kasia into the fridge.

For n > 1 fridges at known locations, Kasia can be positioned anywhere (including partway along an edge) on an optimal TSP tour through them all.

OTOH, if fridges pop into and out of existence dynamically over time, then having a single Kasia traverse all of them is not feasible. In this case, other employees will need to walk to her desk when they discover the last carton of milk at some fridge. If we can assume that the density of fridge creation/destruction is uniform, then the strategy resulting in minimum total distance travelled in expectation is a spherical office building with Kasia at the centre.