4 ms·

>that are about 25% longer than optimum Is this a property or mere probability? What are the random point sets for TSP testing? Given n points in a plane , th

by kang 16y ago

>that are about 25% longer than optimum Is this a property or mere probability? What are the random point sets for TSP testing? Given n points in a plane , the number of Hamiltonian paths can be drawn is (n-1)!. One of these is minimum, and our optimum solution to TSP. If we distribute the frequencies of the lengths of these graphs, (is there a particular name for this graph?) we will find the probability of a particular length-range occurring. This graph, should be different for different complete graphs. So an improvement might simply be that the 'high ridges' on such graph of input of random sets given , lay towards the left sides of 'peak'. >A useful property of a spacefilling curve is that it tends to visit all the points in a region once it has entered that region. Thus points that are close together in the plane will tend to be close together in appearance along the curve. Or very far! Like points around averaged areas (like middle lines, etc) and spacefilling curves do generate averaged areas. Eg yellow points around blue middle lines here http://i.imgur.com/Dl7Vo.gif http://i.imgur.com/Dl7Vo.gif NB: I do not mean to criticize. asking questions.

Groxx 16y ago
Almost certainly a probability. You could probably prove that it's not worse than a certain amount, because it won't jump the farthest distance every time in anything but a truly trivial graph, but a value like that is unlikely to be an actual limit. A reason for my reasoning: they visit things in a certain order. It's therefore possible to design a path that falls directly on non-optimal points along a certain order of that curve; I'd guess you could get multiple times the shortest length, instead of just 25% greater. But you can get a new path by simply increasing / decreasing the order of the curve, so running through a few iterations could probably get you an exceptionally-good result for the sort of speed it provides.
- kang 16y ago
  Sorry , I think, I haven't been clear. My question is 'What are the input of random sets given as input?' because I feel if we write ANY algorithm, however bad it may be, until it gives us a path, saying that that it is only x% longer is a property of the input given by us. I am saying that x could turn out to be 25 in most of the cases who knows.

by kang 16y ago

Groxx 16y ago

Almost certainly a probability. You could probably prove that it's not worse than a certain amount, because it won't jump the farthest distance every time in anything but a truly trivial graph, but a value like that is unlikely to be an actual limit. A reason for my reasoning: they visit things in a certain order. It's therefore possible to design a path that falls directly on non-optimal points along a certain order of that curve; I'd guess you could get multiple times the shortest length, instead of just 25% greater. But you can get a new path by simply increasing / decreasing the order of the curve, so running through a few iterations could probably get you an exceptionally-good result for the sort of speed it provides.

kang 16y ago
Sorry , I think, I haven't been clear. My question is 'What are the input of random sets given as input?' because I feel if we write ANY algorithm, however bad it may be, until it gives us a path, saying that that it is only x% longer is a property of the input given by us. I am saying that x could turn out to be 25 in most of the cases who knows.