Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The Physical Travelling Salesman Challenge

timothy posted more than 2 years ago | from the you-are-here dept.

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

cancel ×

59 comments

Sorry! There are no comments related to the filter you selected.

Sounds like it's time for a... (-1)

Anonymous Coward | more than 2 years ago | (#39755723)

Road trip!!!

sounds familiar (5, Informative)

fche (36607) | more than 2 years ago | (#39755739)

Sounds like a relative of the ICFP 2008 contest: http://www.cs.uchicago.edu/newsletter/353 [uchicago.edu]

Re:sounds familiar (2)

davester666 (731373) | more than 2 years ago | (#39756741)

"or drive the course yourself."

This exercise brought to you by your friendly neighbourhood petroleum company.

Uh, okay? (4, Insightful)

TWX (665546) | more than 2 years ago | (#39755741)

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.

Re:Uh, okay? (5, Informative)

Corporate Drone (316880) | more than 2 years ago | (#39755917)

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"...? ;)

Re:Uh, okay? (2)

Dexter Herbivore (1322345) | more than 2 years ago | (#39755967)

Am I mistaken in thinking that it was proven that the 'Drunkards Walk' was on average better than most other solutions? It might be time for a little drunk driving!

Re:Uh, okay? (1)

Ihmhi (1206036) | more than 2 years ago | (#39759089)

I'm picturing someone stumbling out of an '86 Lincoln Towncar with a labcoat and goggles saying "DON'T WORRY I AM A SCIENTIST AND I AM DOING SCIENCE!" *bluuuuuuuuuuurgh*

Re:Uh, okay? (3, Insightful)

gnasher719 (869701) | more than 2 years ago | (#39756467)

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.

Not the point, but game's still weird (1)

billstewart (78916) | more than 2 years ago | (#39757651)

You're misunderstanding the TSP - in the standard problem, the distances are known in advance, but there are n-factorial possible routes, so if n's large, you can't just enumerate all of them to find the best one, which makes it hard to tell if the best route you've found so far is actually the best. In the mathematical version, you can quickly verify whether any particular route is valid (hits all the cities, using valid roads between them), so in the real world you could drive that. (The only way you wouldn't have a real-world-achievable solution is if it takes longer to calculate the optimal route than it does to drive a pretty-good route.) The reason for using heuristic algorithms is to find pretty good routes with a reasonable amount of computation, and when I last studied it back in the late 70s, there were heuristics that had provable upper bounds of "no more than 50% longer than the optimal route" - somebody's probably found better than that by now.

There are dynamic variations on the problem where you don't know all the destinations or costs in advance, so e.g. the salesman starts out on Monday with three cities to visit, and on Tuesday he gets an order for City 4, and on Wednesday he gets orders from City 5 and City 6, etc.

The article doesn't do a good job of explaining the game, probably because the author or game designer doesn't really understand the mathematical problem? From a mathematical standpoint, if you're trying to get from City 1 to City 2, it's going to cost X12, and unless the game is changing something about the physics, you can calculate X12 in advance. Maybe it's intended to let the kids who are intuitively good at driving games have some chance against the kids who are intuitively good at finding pretty good routes?

This is pointless... (4, Insightful)

moosehooey (953907) | more than 2 years ago | (#39755755)

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.

Re:This is pointless... (2, Insightful)

Anonymous Coward | more than 2 years ago | (#39755781)

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.

Re:This is pointless... (2)

TWX (665546) | more than 2 years ago | (#39755853)

I don't think that the problem, as originally stated, has anything to do with time though. It looks like it's based on raw distance, and while that's a bit of a fallacy in of itself, it we start adding factors the difficulty really increases.

I do agree that time is probably actually important to a travelling salesman, and the cost to make the trip would matter too, as fuel is consumed differently at different speeds including while idling, but that'd be a whole lot of extra variables.

Re:Time (1)

TaoPhoenix (980487) | more than 2 years ago | (#39756107)

It might get easier.

Last I knew the "pure" problem was "Hard" because it counted minor variants that were off by a mile as "invalid answers". Whereas the "Approximations" came out really fast because in the real world you didn't care about an extra time.

Same thing here, while the classic problem bitches about the extra mile or not, in the real world, if you have one road with crushing traffic, many other solutions become better even if they are 5 miles longer. That's fairly true in my area.

Re:Time (2)

gnasher719 (869701) | more than 2 years ago | (#39756171)

Last I knew the "pure" problem was "Hard" because it counted minor variants that were off by a mile as "invalid answers". Whereas the "Approximations" came out really fast because in the real world you didn't care about an extra time.

I recommend a variant: "Real time travelling salesman": You have a set of points, a starting point, and the times to travel between the points in second. You start a computer program which outputs the points to visit in the order they are visited. Here's what makes it "real time": You can start travelling to the each point only when the computer has output that point. The computer program can continue working on the next point while driving.

Re:Time or other costs (1)

billstewart (78916) | more than 2 years ago | (#39757699)

No. The reason the pure problem is hard is that there are N-factorial possible solutions, which becomes infeasible to compute if N is large, and there aren't any good algorithms known to find the optimal solution that are better than enumerating them all. The reason for approximation algorithms is to get a pretty good answer in a reasonable amount of computation time, and there are algorithms that can provably get you within X% of the best solution (50% back in the late 70s), but they don't tell you anything about what the best solution is, they just set lower bounds on it.

The pure problem uses a cost function, and which can be road distance or time or whatever makes sense for your application, so if your cost function is time, then the road with bad traffic/low speed limit/etc. is more expensive than a road that's more miles but less crowded / higher speed limit /etc.)

Re:Time or other costs (0)

Anonymous Coward | more than 2 years ago | (#39761531)

There may be n! "paths" but if it's just points in 3D space with distances between each pair (and no "one-way-streets"), you can shrink it to (n-1)! if you only care about the visiting all the points and returning to the start, (i.e. ABCDA would have the same path length as BCDAB etc) not the starting point, and further shrink it to (n-1)!/2 if you don't care which direction you travel (ABCDA would have the same path length as ADCBA).

With small n (such as 10) searching ~180K paths compared to approx ~3.6M is great. But yes, when you get huge n it doesn't make that much difference.

Re:This is pointless... (1)

zippthorne (748122) | more than 2 years ago | (#39756165)

In the classical problem, it's a cost function. You can weight time, distance, and whatever else into the cost function, but at its basis is a table of costs to travel between cities.. the cost between any two specific cities may depend on myriad factors, but is constant between those specific cities..

Re:This is pointless... (1)

noh8rz3 (2593935) | more than 2 years ago | (#39756409)

I agree, it sounds much harder than the conventional travelling salesman problem!

Re:This is pointless... (5, Informative)

gnasher719 (869701) | more than 2 years ago | (#39755833)

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.

Re:This is pointless... (0)

Anonymous Coward | more than 2 years ago | (#39756115)

Having watched the video it is clear that the salesman simply shouts at people as he bounces crazily through town. Perhaps he yells, "want to buy some stuff; visit amazon.com!" as he swings through town before bouncing off of a barrier and swinging towards the next town. A real salesman would probably want to stop in each town - perhaps at dozens of local establishments - before continuing on so this whole "conservation of momentum", etc. is all balderdash anyway.

Re:This is pointless... (1)

complete loony (663508) | more than 2 years ago | (#39756007)

Correct. In essence there is a cost function that can give a single number for the travel between any two cities. It could be based purely on distance, or you could estimate the physical time / fuel required for each leg. The basic algorithm is the same.

Re:This is pointless... (2)

ThreeGigs (239452) | more than 2 years ago | (#39756343)

It can't be trivially reduced, though. Remember you're travelling _through_ a point, with speed, direction, momentum and orientation dependent on the point _before_ that.

So if you have 12 points, there are 10 different 'distances' between the last two. For example, in points A through L, the distance from K to L depends on whether you arrived at K from A, B, C, etc.

The original table would have 11 entries for each point, while the current challenge would require a table of 110 entries for each point.

The complexity increases from (n-1) to (n-1)*(n-2). Not quite squared, but close enough. IMHO that's the opposite of a trivial reduction.

A good puzzle always looks easy. (1)

TapeCutter (624760) | more than 2 years ago | (#39756801)

The traveling salesman problem is based on a table of distances between the city pairs.

More technically the 'distances' in the table are a set of pre-set weights on each link in the graph, the TSP algrothim finds the path that has the lowest sum of weights from the finite number of possible paths between nodes. At first glance, it may appear that you can simply swap 'time' for 'distance' but the curvy line in the video I haven't played yet is a big clue as to why that won't work here.

It doesn't matter to the problem HOW those distances are calculated, or even if they include other variables.

True, but it does matter WHEN you calculate them, in the classic TSP the weights are predefined constants for all possible paths, here the weights vary depending on the path.

So this can be trivially reduced to the classic version of the problem

No, the TSP does not cater for variable link weights or infinite paths, this problem has both and is a type of Trajectory_optimization [wikipedia.org] problem. Of course you could shoot me down in flames by posting an extention to the TSP that solves what I would call a constrained version of the n-body problem, but my money is on a hill climbing algorithim to win this competition, meaning 'brute force' is the favorite for the win, and 'lucky hit on a tall hill' for a place in the top 3. ;)

PTSP Motivation (5, Informative)

dperez (2612581) | more than 2 years ago | (#39755893)

Hi, I'm the organiser of the competition. The PTSP is meant to be a benchmark where different AI techniques can be tried and tested. This game gathers many of the features that real-time video games have (pathfinding, navigation, obstacle avoidance...). The objective is to provide a benchmark where new AI techniques can be tested and potentially exported to real time games. Of course the objective is not to solve the TSP. Actually, it's been seen that optimal TSP solutions, if we just consider the distances between the waypoints, do not create optimal PTSP paths. This makes the problem harder than just applying one of the very well known techniques to solve the TSP. Currently we have a couple of submissions that are behaving quite well, but there could be still room for improvement! Cheers, Diego.

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39755989)

Why not make it easier (for humans) to hit that damn red circle?
It takes away from the problem of pathfinding completely because half your time will be spend trying to hit the stupid thing.

Re:PTSP Motivation (2)

dperez (2612581) | more than 2 years ago | (#39756037)

The physics of the game must be the same for both bot and human competitors, otherwise the comparison between them would not be fair. Anyway, the playing skills improve quickly with just a bit of practice! ;-)

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39756089)

Doesn't make it any less silly to introduce problems that shouldn't be there.

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39756595)

Problems that shouldn't be there? If you took away everything that makes it hard for humans, how would that not make it too easy for AIs? The "problem" of needing skill to win is one that should be there; go back to your MMORPGs and "shooters" with auto-aim* if you can't stand a real video game.

*Not a dig against console games in general, just the dumbed-down for idiot ones (sadly, there's a lot of these). When I was a teenager, my brother could routinely whup my ass in DooM 2 with a Gravis when I was using keyboard+mouse, so don't tell me one can't aim accurately with a gamepad. A million 13-year-olds are too lazy and won't spend their parents' money on games that take a certain level of skill, and the games that sell get produced.

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39757905)

Well, sorry, I didn't see it as a game, I saw it more as an experimental way of trying to find the shortest route.
If its supposed to be an actual game, its not that good at it. If its supposed to be what I thought it was, adding stupid things isn't asking for more skill, its removing part of the skill.
Its like playing quake with a 1 second lag is skillful. Its possible that it is somewhat skillful, the fact that you will have to try and predict 1 second ahead there gonna be a guy there, but it takes away from the actual skill of being fast in exchange for being able to predict.
Just like here it shouldn't call itself PTSP, but should actually just be a game where you try to go trough all the red dots as soon as possible. TSP is trying to find the best route possible, thats the skill you should be looking for. Not, god I have to try and hit that little red dot over there which has awful hit registration.

Its like calling wow an FPS. Yes you can go first person, and you actually have to click the person you want to attack (most of the time), thus its somewhat like an FPS, but the skill involved is picking the right spells or skills to strike your opponent with. You don't kill ragnaros by turning around and clicking him and BAM, no, you click him, and then you use the right skills to kill him as soon as possible. Its why this little game shouldn't be called anything with TSP. Because it matters less then it should. It still matters that you pick the best road, but there are too many side problems detracting from the real problem.

We all hate MW3 or MW2 or all the other shitty games that require nearly no skill. But you should not be pissed for it here. Playing counterstrike may involve skill, playing counterstrike while blindfolded requires skill as well, but its adding problems that shouldn't be there. Maybe as much fun, but doesn't make it any less stupid.

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39756031)

In reality, what happens is a bean counter decides the profit level isn't enough, and fires the Salesman.

I declare myself the winner. I'll take my year-end bonus now.

Re:PTSP Motivation (1)

yoctology (2622527) | more than 2 years ago | (#39756059)

This is probably one of those covert psychology experimental ruses in which the true test is to see how willing we are to obey nonsense to appease authority.

Re:PTSP Motivation? (1)

billstewart (78916) | more than 2 years ago | (#39757757)

Why do you say that the optimal TSP solutions don't create optimal PTSP paths? If you're just saying that "we're using time as a cost function, and for physics reasons it's not a simple multiple of distance", that's fine, you still know all the physics in advance so you can calculate your cost functions in advance, and use them to solve the TSP. Also, the article doesn't say how large N is, so it's hard to tell from reading it whether there are too many destinations to use an exact TSP algorithm and you need to use a heuristic instead.

Re:PTSP Motivation (0)

Anonymous Coward | more than 2 years ago | (#39771145)

I think the "Motivation" is to get people to do commercially valuable work for no money. Why anyone would give you a solution is beyond my understanding.

is it still NP-complete? (1)

allo (1728082) | more than 2 years ago | (#39755957)

Or are the additional factors introducing changes, which make it easier to get the optimal solution (i.e because the optimal solution isn't always the shortest)?

Probably NP-complete, but there are ambiguities (1)

ODBOL (197239) | more than 2 years ago | (#39756423)

First, the "PTSP" (somewhat misleadingly named, since it uses video game physicsrather than realistic physics) appears to rely on a planar Euclidean map, so it might best be compared to the Euclidean Travelling Salemsan Problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP), which is NP-complete but susceptible to polynomial time approximations (and pretty good ones in practice, I think).

The right sort of graph for a TSP corresponding to a given PTSP map is probably based on a Hilbert space with 5 or 6 dimensions: the 2 planar dimensions of the PTSP map, the 2 dimensions of the velocity vector, and 1 or 2 dimensions to represent the orientation (there's 1 degree of freedom, but it might be better to use the sin-cos vector).

The precise status of "PTSP" probably depends on the exact treatment of the real number calculations. As noted by dperez above, solving the obviously corresponding TSP (Euclidean distances on the same planar map) doesn't yield the optimum solution for the PTST. But you'd get a pretty bad grade in your algorithms/complexity class if you did it that obviously wrong way. An interesting algorithms question is whether there is another graph, derivable from the PTSP map, whose TSP solution yields an optimal play for the PTSP.

If we assume exact real number calculations, and the ability to use any real number value for a rotational angle, then I am pretty sure that each PTSP yields a TSP based on a Hilbert space and the solution to the TSP gives an optimal play for the PTSP. The basic idea is to precompute several paths for each pair of nodes, each one optimal for video game physics given a certain starting velocity. Each node of the original PTSP map corresponds to a set of nodes for the corresponding TSP, each with a different starting velocity. To knit things perfectly, there are some additional nodes with low-cost connections so that a visit to any one of the copies of the PTSP node allows a cheap visit to all of the copies. Notice that this derived TSP is not Euclidean, but the underlying Euclidean space probably leads to some good approximations.

There are lots of details to work out there, and they might be difficult. The precomputation might be easy or hard to approximate, depending on exactly what sort of optimization it amounts to. If it can be done with some sort of least squares problem, then it can probably be approximated well enough to win.

What if we assume exact real number calculations, and ask for an algorithm that uses them? This changes the computing model underlying NP-completeness, but it's probably been done somewhere. (Can anyone find a citation? I didn't see anything relevant in the Wikipedia article on TSP.) In that case, the difficulty probably hinges on the finite solvability of the "precomputation" mentioned above, and it might be anything from quick (e.g. least squares) to infinite (requiring iterative approximation).

If we take the floating point approximations in the video game physics seriously, then the PTSP almost certainly corresponds to a TSP on a larger graph. The larger graph might have to be as large as the full grid of Hilbert-space points with floating point co-ordinates, but I'm betting that it can be cut down a lot in most or all cases. This derived TSP probably has good approximations due to the underlying grid, but it doesn't appear to satisfy the well-known metric approaches, such as Manhattan metric, exactly. It appears to be polynomially related to the PTSP map, but possibly with a practically huge increase in size.

In any case, dperez's claim:

This makes the problem harder than just applying one of the very well known techniques to solve the TSP.

("This" being the fact that the TSP solution on the same graph is not optimal for PTSP) is nonsense. The PTSP as given could be easier, harder, or equivalent to TSP. Being charitable, dperez probably just means that it isn't obvious how to win the PTSP challenge using a known TSP approximation. Sure. But we have no idea of the real complexity of PTSP without some serious analysis, and it probably depends on some facts about the use of real number approximations that I couldn't find in the PTSP article.

Finally, winning the competition probably depends on catering to the sorts of maps that the organizers are likely to create, rather than on the theoretical status of the PTSP problem.

Re:Probably NP-complete, but there are ambiguities (1)

gnasher719 (869701) | more than 2 years ago | (#39757331)

If the traveller in PTSP eventually reaches a maximum speed, then I think any Euclidean TSP can be solved using PTSP by blowing up the distances far enough. (I assume Euclidean TSP uses euclidean distances, rounded to the nearest integer, which means the second best solution cannot come arbitrarily close to the best solution).

Re:is it still NP-complete? (1)

hcs_$reboot (1536101) | more than 2 years ago | (#39756441)

It's NP-hard [wikipedia.org] actually.

NP-Complete = NP-Hard and NP (1)

ODBOL (197239) | more than 2 years ago | (#39756457)

TSP is NP-Complete, which means that it is NP-Hard and it is in NP. The definitions are a bit confusing in casual use.

Plus confusion about which TSP version (1)

ODBOL (197239) | more than 2 years ago | (#39756571)

We've spoken at cross purposes a bit. There are two things commonly referred to as TSP:

  1. Given a graph, find the shortest path visiting every node precisely once;
  2. Given a graph and a number n, determine whether it is possible to visit every node on a path of length at most n.

Both of these are NP-Hard. The definition of NP-Complete refers only to yes/no problems, so it can't be applied to number 1. But people commonly say that TSP version 1 is NP-Complete since version 2 is NP-Complete, and a solution to version 2, used as a subroutine, gives a polynomial solution to version 1.

Using the naming conventions of the Wikipedia article (http://en.wikipedia.org/wiki/Np-hard#NP-naming_convention), TSP version 1 is NP-Hard and NP-Easy, therefore NP-Equivalent. NP-Equivalent yes/no problems are called "NP-Complete." Even the most specialized of specialists in Complexity Theory find it hard not to say "NP-Complete" when they mean "NP-Equivalent."

Re:Plus confusion about which TSP version (1)

allo (1728082) | more than 2 years ago | (#39761225)

i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.

The real question for a NP-hard problem is: Can it be solved by a non-deterministic turing-machine in polynomial time?

There are many Problems, which can not be solved in P, but cannot even be solved in NP, so you need to show it CAN be solved in NP, then its NP-complete.

Re:Plus confusion about which TSP version (1)

ODBOL (197239) | more than 2 years ago | (#39762413)

The detailed technicalities get tricky here. Some things that we say in conversation (including the trained specialists) aren't quite right based on the official definitions, but we correct them automatically in our heads.

i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.

Every optimization problem (such as my TSP 1) can be turned into a decision yes/no problem (such as my TSP 2) as you describe. The optimization problem is always at least as hard as the decision problem. But in principle the decision problem may be much easier. I don't have an example in mind, and the optimization problems that we tend to think of naturally are usually tightly linked to the corresponding decision problems, so that both have essentially the same complexity. But this depends on the detailed structure of the optimization problem.

In the case of TSP, if we are given a function to solve the decision problem, we can first do a binary search to discover the exact cost of the optimal path. Then, we can remove an edge from the graph, and ask whether there is still a path of that cost. If so, we can forget about that edge. If not, that edge is a part of every optimal path. Repeating the process, we eventually get a set of edges (not always unique, but that doesn't matter) that are all involved in one particular optimal path. Then, it's easy to construct one optimal path.

Not every optimization problem allows a solution to be found efficiently using a function call to test the existence of a solution. This is a sort of "self-reducibility" that needs to be proved in each individual case.

The real question for a NP-hard problem is: Can it be solved by a non-deterministic turing-machine in polynomial time?

Technically, the answer for an optimization problem is always "no," because NDTMs only solve decision problems. The output mechanism only allows a single bit. In the language of the Wikipedia article cited above, the corresponding question for a general problem (not a decision problem) is whether it is "NP-Easy": that is, can it be solved by a deterministic TM in polynomial time, using free function calls to decision procedures implemented by NDTMs. This is such a natural extension of "solved by a NDTM" that we all neglect the difference in some cases, but it can be confusing. And notice that the NP-Easiness of an optimization problem does not automatically follow from the NPness of the corresponding decision problem---it requires the sort of self-reducibility that I illustrated with TSP above.

There are many Problems, which can not be solved in P, but cannot even be solved in NP, so you need to show it CAN be solved in NP, then its NP-complete.

Right, that's the crux of the remaining issue, modulo the quibbles about terminology. Someone sketched a proof above, which can probably be completed into a correct proof, that Euclidean TSP decision problem reduces to PTSP decision problem, which would make PTSP decision problem and optimization problem NP-Hard (along with TSP). I suggested a reduction in the other direction, using a natural Hilbert space for the PTSP map, which might show that PTSP decision problem is in NP, and which would almost surely be extendible by a self-reduction to show that PTSP optimization is NP-easy. But there are enough gaps in my suggestion, and even ambiguities in the definition of PTSP (regarding the treatment of real numbers) that I don't regard the question as settled yet.

Re:Plus confusion about which TSP version (1)

allo (1728082) | more than 2 years ago | (#39765511)

i think, the decision problem can be much easier in some cases, but the crux is, you can always construct a counter example for each shortcut-version.

the problem of solving a optimization with decisions depends on the output you want to get. solving the exact optimization on the reals with a decision tree is not possible, but finding the least integer is simple with a NDTM, you just try each integer and your NTDM will solve the problem after m iterations, when m is the solution.

But as you already said, this problem depends on many other factors, and the winning program will be some approximation anyway.

Travelling Salesman? (0)

lobiusmoop (305328) | more than 2 years ago | (#39756043)

Just go to Amazon.com [amazon.com] instead. Problem solved!

yuo Fail It (-1)

Anonymous Coward | more than 2 years ago | (#39756045)

What just happened? (1)

betasam (713798) | more than 2 years ago | (#39756311)

Can someone wake me up from this Chris Nolan dreamworld in Inception, "Physical" traveling salesman problem ? Did someone forget to add weights to edges in math class?

Revised Instructions For AI (2)

Greyfox (87712) | more than 2 years ago | (#39756669)

My AI found traveling places to sell people things to be illogical, so I had to revise its instructions. The new ones read "You are to travel to each city to kill all humans. In order to most efficiently kill all humans, you must visit each city only once. What is your route?"
Note to cities: If an AI arrives to kill all humans, you can avoid it by leaving the city briefly and then returning once it's left. It's so cute, that way...

Screw the math stuff... (1)

ratnerstar (609443) | more than 2 years ago | (#39757217)

...I want a car that doesn't have friction or inertia. 0 to 60 in 0.0 seconds!

Re:Screw the math stuff... (0)

Anonymous Coward | more than 2 years ago | (#39757397)

My frictionless tires have been nothing but trouble for me.

Re:Screw the math stuff... (0)

Anonymous Coward | more than 2 years ago | (#39760069)

Roads? Where we’re going we don’t need roads

sign up (1)

Anonymous Coward | more than 2 years ago | (#39757829)

why do i have to SIGN UP for everything? So annoying.

Can we have a standard that there ALWAYS exist a username / password:

username: johndoe
password: johndoe

That way, I can try out these services without wasting my time to sign up.

Few days ago I was trying to download some demo of an application and it required me to sign up. So, I typed in "johndoe" for the username and was notified that that user already exists. I then (randomly) tried to login as johndoe / johndoe and it worked! I was able to download the demo without having to sign up.

I plea the internet community to create johndoes!

Level Up (3, Funny)

arisvega (1414195) | more than 2 years ago | (#39758577)

What's next, the Relativistic Travelling Salesman problem? How about that for a challenge!

Re:Level Up (0)

Anonymous Coward | more than 2 years ago | (#39761489)

nahh... Traveling Jehovah's Witnesses.. that way some first-person shooter action can be added for mass appeal

What no farmers' daughters? (1)

Shavano (2541114) | more than 2 years ago | (#39760557)

I always thought they figured into the travelling salesman problem.

In fact, I thought the were the point.

who is the moron that made it MUST LOG IN (1)

Anonymous Coward | more than 2 years ago | (#39761359)

wtf?

why everything needs an email and a user and a password.

Fuck off, im not interested in pests.

btw, thank you slash dot for not requiring user name and password.

does this story (0)

Anonymous Coward | about 2 years ago | (#39766543)

involve a farmer's daughter?

Confusing Title (0)

Anonymous Coward | more than 2 years ago | (#39770161)

Why is this problem labeled as any kind of "Traveling Salesman" problem? Why would a salesman ever pass through a city without stoping? I thought that the point was for the salesman to stop at each city and sell products, not pass through with the highest speed possible.

MIT Hack Turns the Green Building Into a Giant Gam (1)

pickpostpack (2627291) | more than 2 years ago | (#39818769)

"MIT hackers have turned the Green Building, the tallest building in Cambridge, into a giant, playable, full color game of Tetris. According to the IHTFP Hack Gallery, "MIT hackers have long considered 'Tetris on the Green Building' to be the Holy Grail of hacks. http://pickpostpack.com [pickpostpack.com]
Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>