travelling salesman problem

Nov 2014
12
0
Moorhead M
I have a question, how useful would it be to identify an edge that must always be used in an optimal? i found a way to identify optimal (though it is not efficient) and one unique property of my new method is that it has created a way to identify a specific edge that will always be in the optimal path (provided there is only one optimal. it goes on from there and finds optimal using that as its starting point. But my question is, is that a big deal or what? my method can only find a single edge that is always included in an optimal. which means that the number of possible routes that could be optimal is no longer (n-1)!/2, but becomes (n-2)!... meaning that it eliminates ((n-1)!/2)-((n-2)!) options. graphed out, it starts at 1/3 of the solutions, then 1/2, then 3/5 and that portion of eliminated possible routes approaches 1 (100%) as the graph increases in size.

this all happens before doing any work with the graph itself for finding/approximating optimal. has this been found out before? would this be of use to others who are working on programs to identify/approximate? i would imagine that being able to eliminate a high percentage of routes before starting would be useful, and i can't imagine that someone hasn't identified this yet?
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
I have a question, how useful would it be to identify an edge that must always be used in an optimal?
It reduces an n-city problem to an (n-1)-city solution. In particular if you can find an edge that must be taken in an optimal solution for an arbitrary graph in polynomial time then you can solve TSP in polynomial time (with exponent 1 higher).*

* And hence, your proof would probably br incorrect -- about optimality, being able to find it in all graphs, or about it taking polynomial time. But this is just a heuristic (and of course you didn't claim polytime!).
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
this all happens before doing any work with the graph itself for finding/approximating optimal. has this been found out before? would this be of use to others who are working on programs to identify/approximate? i would imagine that being able to eliminate a high percentage of routes before starting would be useful, and i can't imagine that someone hasn't identified this yet?
An enormous amount of work has been done on this topic. The best methods can easily eliminate a percentage of work asymptotically approaching 100% as well -- it's merely an issue of how fast the approach is.
 
Nov 2014
12
0
Moorhead M
ok but neither of those answer my question. maybe i can rephrase it... i can (with very little work) identify an edge that must be included in any graph. by knowing just one edge, it eliminates a lot of possibilities. it then limits what was (n-1)!/2, to (n-2)!. that number is a lot smaller, and as the chart increases, it eliminates more and more. at k4, it only eliminates one option (1/3 eliminated), but at a k11, it eliminates 98% (1778112/1814400 options) of the optional routes in the graph. all of this before running any algorithm to find optimal. So my question comes down to, does anyone know if anyone has found something like this before? and would something like that be of any use to someone running an algorithm? it may eliminate a lot, but it still leaves a lot to test. i guess i don't have the understanding of how useful this is/isn't.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
ok but neither of those answer my question.
Maybe I wasn't clear enough in my first post. If, given any TSP graph, you can find (at least) one edge which must be included in an optimal circuit, then you've solved TSP. If the time it takes you to find an edge is O(f(n)), where f(n) is a nondecreasing function of n, then you can solve the whole graph in O(n*f(n)). In particular, if f(n) has a polynomial upper bound then you've solved TSP in polynomial time and showed that P = NP.

So my question comes down to, does anyone know if anyone has found something like this before?
I don't think that you've found what you think you have, so the meaning of "like this" is in question.
 
Nov 2014
12
0
Moorhead M
I'm not going to pretend that I understand that (sorry)... I am not as familiar with this topic as I would like to be. Time complexity still is a bit confusing to me. So I will try to explain what I have found.

In very few steps, I can organize the data in a way that allows me to find an edge that must be contained in any optimal. This happens before any process for finding optimal exists. This only finds one edge, and does not work again. As far as I can understand, one of the problems with the TSP is that finding a constant property of the optimal (other than it having the lowest value of all possible routes) is really hard. The other problem with the TSP is, how do you distinguish between 2 identical edge weights, which one to be chosen. now, i found a way to solve for optimal every time, but it is not time efficient (so sayeth my partner who better understands time complexity, and whom I will have explain that post to me later on).

What I think I have found is a constant property of the optimal route(s) in a TSP. The value i think it has, is that it removes a lot of options before applying any method.

This is a fun math project for me, but I don't fully understand the theories behind it. I noticed a pattern and my math professor encouraged me to explore it. So I am currently working on this with no understanding of graph theory (working on that slowly but surely), no understanding of time complexity (just know that it means make it an easy fast equation), and I am working with a computer science person who is helping by creating a brute force program so that all the graphs that I do (by hand) can be compared to the optimals. I have found a way to solve for optimal but it is not very efficient. I spend about an 3 hours on a k-17. But through all of this I did find a way to quickly, easily, and accurately identify a single edge in an optimal route of any given graph.

So that's what I got. Thanks for your help.