The Physical Travelling Salesman Challenge 59
mikejuk writes "You probably know that the traveling salesman problem is one of the classics of computer science theory. Now we have a new challenge — the Physical Travelling Salesman Problem and anyone can join in. All you have to do is visit each city once using an optimal route. The new element is that you now have to drive between the cities using a 'car' that has inertia and friction — see the video. You can submit an AI bot to solve the problem or drive the course yourself."
sounds familiar (Score:5, Informative)
Sounds like a relative of the ICFP 2008 contest: http://www.cs.uchicago.edu/newsletter/353 [uchicago.edu]
Re:This is pointless... (Score:5, Informative)
The traveling salesman problem is based on a table of distances between the city pairs. It doesn't matter to the problem HOW those distances are calculated, or even if they include other variables. So this can be trivially reduced to the classic version of the problem.
It's not quite as simple. The distance between two destinations is not fixed. The time to get from A to B depends on the speed and direction when you arrived at A or passed through A, and the speed and direction that you want to have when arriving at B.
PTSP Motivation (Score:5, Informative)
Re:Uh, okay? (Score:5, Informative)
It's simply meant to be an implementation of a heuristic, based on the traveling salesman problem, that takes into account physical considerations (speed, acceleration, direction) and processing limitations (RAM, processor cycles) for both initial setup and decision-making at each step.
The speed/direction stuff reminds me of the kind of skating that hockey players do (is it more effective to go in one direction, stop, and turn around, or is it better to modify your line and preserve momentum? in this game, too, is it better to accelerate greatly and bounce off a wall behind your target, or approach more slowly in order to modify your line without an abrupt change in direction?).
The processing limitations are interesting too, and provide for an interesting optimization exercise.
Or, by "I don't understand", should I simply answer "it's fun"...? ;)