0

I am studying the euclidian version of the Travelling Sales Man problem:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city, where the direct connection from city A to city B is never farther than the route via intermediate city C.

And I wonder:

Is it possible to make the number of cities on the list have no influence on the average/estimated time it will take to find a solution? For example, to modify the rules that with 10 cities that you require 4 cities in the path, and with a million cities, that you require 400 cities in the path. So that each list will take about the same time to solve, no matter its length?

Maestro
  • 165
  • 1
    Do you really think that the number of cities would not affect the question? If you have a million cities, is it going to take the same time to solve as with $4$ cities? It seems like the case with $4$ cities is going to take at most $6$ computations, but the case with 1 million cities will take at least 1 million computations to show the result. – Thomas Andrews Mar 21 '15 at 19:20
  • @ThomasAndrews I explained myself wrongly. If I have a million cities its much easier to form a short path that hits 3 cities, then if I only have 4 cities to choose from. Because with a million cities 3 will likely be very to eachother, while those 4 could be very far apart in the world. So if it will be easier or harder depends on the retrictions. But is it possible to have restrictions where the number of cities dont matter? – Maestro Mar 21 '15 at 19:23
  • That comment is nonsensical. If you have a million cities, you are trying visit a million cities, not three cities. Otherwise, you are not talking about the traveling salesman problem. @Muis – Thomas Andrews Mar 21 '15 at 19:25
  • If you are talking about some other problem, please state that problem clearly in your question. – Thomas Andrews Mar 21 '15 at 19:26
  • @ThomasAndrews I edited my question to do that. – Maestro Mar 21 '15 at 19:28
  • You could always constrain the cities to be on a straight line – Mark Bennet Mar 21 '15 at 19:29
  • It's still not clear what that question is asking. Are you asking for a reformulation of the problem so that this is true? – Thomas Andrews Mar 21 '15 at 19:30
  • @MarkBennet If you show me a formula how I can do that, I will accept it as answer. – Maestro Mar 21 '15 at 19:30
  • @ThomasAndrews I want to present people with the problem, and I want to make sure each peoples problem takes about the same amount of time to solve. But I have no influence on the number of cities each person gets, so I need to find a way to make it easier/harder depending on the cities. That way everybodys problem should be equally hard? – Maestro Mar 21 '15 at 19:32
  • You should make the goal of your question clear. It sounded like a pure complexity question. Is there are minimum number of cities given? If so, and the minimum is $n$, have each person randommly select $n$ cities and try to solve it for that set. (If the minimum number of cities is $4$, this will always be a trivial problem, but that's because there is no way to make the $4$ case hard.) – Thomas Andrews Mar 21 '15 at 19:39
  • The question seems reasonable to me, but it needs to be more carefully stated. Here is one possible formulation: We are given $n$ cities, and we have to visit $m$ of them. If $m$ is fixed, is there an algorithm that will find the shortest possible path in time that is polynomial in $n$? For this formulation, the answer is yes, because the total number of $m$-length paths is polynomial in $n$ if $m$ is fixed. But this is just one way of restating the problem. – TonyK Mar 21 '15 at 19:40
  • As for whether the TSP complexity is exponential, that is unknown - the famous P=NP question is equivalent to the question of whether TSP can be solved in polynomial time or not. – Thomas Andrews Mar 21 '15 at 19:40
  • He asked nothing about polynomial time, @TonyK. He asked for no affect on the average time. He's asking for $O(f(m))$ time, in your example, for some $f$. – Thomas Andrews Mar 21 '15 at 19:42
  • $@ThomasAndrews: Yes, you are of course right. I was trying to salvage something from the question, which I still think has potential. – TonyK Mar 21 '15 at 19:45
  • Yes, but better to try to suss out what he is asking for, rather than projecting a possible meaning. There are lots of variants of TSP that are potentially interesting, but I can't figure out what OP is trying to say. @TonyK – Thomas Andrews Mar 21 '15 at 19:49
  • @ThomasAndrews: That's why I suggested my own interpretation ("here is one possible formulation"). I don't think we have anything to disagree on here. – TonyK Mar 21 '15 at 19:55
  • @ThomasAndrews Im thinking about your solution to let each person pick X cities, where X > minimum. But I think people could cheat by not picking cities really random, and I have no way to find out if they did? Or am I overlooking something? Does that mean I always have to pick the cities for them? Or can you think of anything which would requires less central coordination, so that Im not required to give everybody a list? – Maestro Mar 21 '15 at 20:36
  • @TonyK If you post your comment as answer, I can accept it. But please read my comment to Thomas to see if we are on the same page. – Maestro Mar 21 '15 at 20:41
  • Wait, you want me to keep reading and responding to your long paragraph comments when you already have an answer you are ready to accept? @Muis – Thomas Andrews Mar 21 '15 at 20:50
  • @Muis: I can't post my comment as an answer, because it's not an answer! – TonyK Mar 21 '15 at 21:19
  • @ThomasAndrews Any solution to the problem I pose is fine, even if I cannot understand it fully. So if his comment is the solution, then yes I was ready to accept it. – Maestro Mar 21 '15 at 21:58

0 Answers0