On Sun, Jan 25, 2009 at 09:13:28PM -0800, Bill Coderre wrote:There are still ways that this can get confused or beaten, of course. Until someone comes out with a low-cost traveling-salesman solver, however, whatever algorithm you find will have some snags.
On Jan 26, 2009, at 12:53 AM, Marius Gedminas wrote: I don't see how traveling salesman applies here. Could you elaborate?
OK, so this was a semi-joke/handwave that if the walls are moving, one would probably need something that can solve routes in near-zero time because the routing would be changing a lot.
If I were thinking harder, I would have remembered that the Traveling Salesman Problem is concerned with visiting ALL nodes on a network, and not just finding a single (hopefully quick) route from A to B, and therefore it's not applicable to this problem at all.