Fang Talks

Blog-tastic!

Given a list of cities, what is the shortest route to visiting them all just once and returning to the starting point?

Seems like a simple enough issue, right? Yeah, the problem itself is simple. Easy to explain and all that. The solution, however, is a different story. While, of course, you can easily write a program that goes through all possibilities and then picks the one with the shortest route, it’ll be far from efficient. Especially once you get to larger lists of locations, the time it’ll take your program to run through all the options will increase dramatically.

I won’t bore you with the math behind it all, but there’s already been a lot of research done on this. May seem a bit odd at first, but this problem (rather, its solution) has a very broad range of applications, such as logistics, the manufacture of microchips, or even DNA sequencing. It doesn’t have to be salesmen and cities, it could be electricity and solder points, for example.

There’s actually a couple of prizes floating around for whoever can come up with an algorithm more efficient at solving this problem than the current “best” one. It isn’t exactly my domain, but I’d like to give it a shot sometime! Not expecting to make a breakthrough or anything, but it may be cool as an educational project.

And I may already have a “mathematician” in reach to collaborate with.
~ Fang

Comments

  • 12/01/2015 (7:06 PM)

    That’s actually a very cool premise, and something I’ve not thought of. There’s that urban legend that UPS drivers only take right turns because it’s the most efficient way to deliver… that’s partially true (it’s better to avoid them) but they don’t avoid them altogether. In other words, there’s a lot of misinformation with the most ‘effective’ sales/delivery route.

    Also, regarding your comment, Caves is a damn cool premise about an underground world with creatures like the Wyvern, whereas the Hunger Games is about angsty teenagers trying to take down the big mean government in a very typical dystopian world, so don’t dare compare the two! And speaking of, when we gonna see any writing from you again?

    • 12/01/2015 (9:57 PM)

      That question at the end. ):
      I really need to get that caves rewrite going. At the very least move the points from my mind to some text file or whatever. (Know of any good timeline-esque software out there? Plain text files sometimes aren’t all that great for organizing things, though they get pretty close.) Sadly, what with all the near-RSI shit still happening, on top of me being busy with the last few weeks of my internship, and school starting again after that, I’m not sure how much time I’ll be (physically and temporally) able to devote to the art of the pen.

      If you’re wondering about Charlie & Pip Sqeek, I’ve kind of given up on that? No thought about it has passed.

      What thoughts have passed about though is a thing for which the oldest recorded thing is somewhere in late 2012? It’s some MASSIVE story about some virtual reality game that’s more real than can be deemed safe. As far as generic plot bases go this is basically the king, borrowing themes from Charlie and the Chocolate Factory as well as the always kinda “popular” VR genre. I’ve already written a fucking shitton on the game’s mechanics and have a few key plot points standing already, as well as some mediocre-to-nice character development. Last time I’ve seriously written something down for that was in 2013 though, so it’ll probably require a lot of work. It’s still a project I’m muy excited about, though its feasibility level is rather low.

      On a more realistic note, there’s also an idea for a silly web comic though, Ghost Roommate. If I ever feel like it I’ll see if I can get a decent art style down, and then stock up on a huge backlog of silly gags so I can keep a content stream going. (I already have three written out! (no wait four I just thought of another one, this is hilarious))

      Also thanks for the interest. <3

Post a comment

Your email will stay hidden, required field are marked with a *.

Experimental anti-spam. You only have to do this once. (Hint: it's "Fang")