Hacker News new | ask | show | jobs
by Merovius 3248 days ago
I tried describing here https://www.reddit.com/r/programming/comments/6oxra8/using_h... why I think that this is theoretically a TSP problem, I don't consider that necessarily the best way to treat it. tl;dr is, that at least to me, at the time, for this problem, the speedup of an optimal solution wouldn't have outweighed the additional thinking time to get to that optimal solution (and, most importantly, to actually make it useful; after all, I wasn't actually drawing a path, I was outputting a list of names).

You can even see that in the argument I added to the post; while a zig-zag line might've been, in theory, a stupider, easier way to solve the problem, in practice it would've meant spending some time thinking about the right discretization. With a Hilbert-curve, I could just choose some n that is definitely large enough and be done with it and the additional cost of the more complicated curve doesn't really factor in, as I could just copy-paste it anyway.

But yes. The theoretical problem is a TSP and with the right set of tools, I could've added some efficiency to the search by viewing it as such.