Slashdot Mirror

← Back to Stories (view on slashdot.org)

The Physical Travelling Salesman Challenge

Posted by timothy on from the you-are-here dept.

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."

4 of 59 comments (clear)

  1. Uh, okay? by TWX · · Score: 4, Insightful

    I thought the point of the actual mathematical problem was to mathematically conclude the best possible path, with the understanding that it wouldn't be real-world achievable but that one would use that as a guideline to strive for.

    This little game they came up with removes the math portion of the experiment entirely, and while it adds the acceleration changes due to mass, one could have just introduced those acceleration changes into the original problem mathematically.

    I don't understand what the little game is actually for. It's not entertaining enough despite their attempts to compare it to Crazy Taxi and others, and without there being math involved in plotting the route I don't see how one practices the theory beyond a child's level.

    --
    Do not look into laser with remaining eye.
    1. Re:Uh, okay? by gnasher719 · · Score: 3, Insightful

      I thought the point of the actual mathematical problem was to mathematically conclude the best possible path, with the understanding that it wouldn't be real-world achievable but that one would use that as a guideline to strive for.

      The point of the mathematical problem was being a mathematical problem. In real life, you would first not look at the distance, but at the cost (taking into account fuel, wear and tear, cost of the time spent, tolls etc. ). You would consider that the cost of going from A to B is often not the same as the cost going from B to A. You would consider that the cost will depend on the time of day. You will consider that there are other restrictions (be at X anytime before launch, be back at the base before 6pm). If a truck makes delivery, there might be advantages of getting rid of a heavy load early, so the cost would go down after visiting some point X.

      So the result of the mathematical problem will likely not be nearly as good as some rather simple heuristic with real life data.

  2. This is pointless... by moosehooey · · Score: 4, Insightful

    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.

    1. Re:This is pointless... by Anonymous Coward · · Score: 2, Insightful

      Well the difference could be the time taken for each leg could be different depending on what time/day it is. So it doesn't reduce to the classic version.

      I'm no mathematician but I think this makes the problem harder to solve not easier, and the classic problem is already considered "hard",,,

      In the real world you might be able to solve it for simple cases or "solve" it well enough. But that applies to the classic scenario and this scenario.