[pvg]

Google up 'soap film steiner tree' for a fun, well-known variant of this.

[jerf]

Then follow it up with https://www.scottaaronson.com/papers/npcomplete.pdf . While reality can "solve" these problems to some extent it turns out that people overestimate reality's ability to solve it optimally.