Via Lubos Motl:
http://motls.blogspot.com/2008/02/dog-solves-travelling-salesman-problem.html

Via Lubos Motl:
http://motls.blogspot.com/2008/02/dog-solves-travelling-salesman-problem.html
This dog solves problem, how to pop up closest balloon in range and its strategy is apparently suboptimal from this point of view. It randomly circles the balloon crowd often and it even doesn't visit the center of crowd at all.

Yeah, I am pretty sure there are efficient heuristic/randomized algorithms for TSP.

From 'Impossibility' by John Barrow :

http://img144.imageshack.us/img144/1494/scan0001cs7.jpg

I dunno...I like the dog's soluotion better.

Well we could met half way. We just need n dogs and 3038n balloons and see if they can find that path in less than a total of 1.5 years of dog running and biting.

What is ''impossibility'' all about?

Yeah, I am pretty sure there are efficient heuristic/randomized algorithms for TSP.
Those algorithms, like the dog's algorithm, are not "solutions" to the TSP. The traveling salesman problem asks for the shortest route to visit a collection of cities and return to the starting point. While these heuristic algorithms usually do find a route that is very close in length to the shortest route, they rarely find the global optimum for a network of any complexity. The problem with finding the global optimum is that it takes to long. This problem exemplifies the maxim "good enough is the enemy of the best" (which itself is an imperfect rendition of the actual Voltaire quote, "The perfect is the enemy of the good.")

From 'Impossibility' by John Barrow :

http://img144.imageshack.us/img144/1494/scan0001cs7.jpg

I know his brother., Wheel

Well we could met half way. We just need n dogs and 3038n balloons and see if they can find that path in less than a total of 1.5 years of dog running and biting.

Sounds like something that you could get government funding for...

Sounds like something that you could get government funding for...

Not if you support the troops and want them to have everything they need for victory against the enemy.

Not if you support the troops and want them to have everything they need for victory against the enemy.

Well...we shouldn't get into this here. The last thing I want is a bunch of whiny democrats and righteous republicans in here arguing about funding science.