Rob Renaud (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} ru_linux_geek) wrote,@ 2008-03-21 03:09:00 |
|
| Entry tags: | algorithms, reddit, tsp, xkcd |
Travelling salesman, xkcd, and a month old reddit post.
From a reddit post I made a month ago.
There are n! paths in a graph of size n. I can find the optimal TSP solution in O(n^2 2^n) time. Therefore, it is possible to do better than examine every path to find a TSP solution.
http://www.algorithmist.com/index.php/Traveling_Salesperson_Problem
And today's xkcd comic.
Suspicious?
I just wish I had a modicum of artistic ability, I swear I've got about five ideas for good xkcd style comics.
