Travelling Salesman Problem solution as a conjecture

[varghese]

Hello to All,

 

This is a continuation of the post "Travelling Salesman Problem" given by me in Appplied Mathematics section. I am giving a very simple explanation of the algorithm so that it becomes easier to understand. I did not see that postings could be made in the Mathematics section. That is why I am posting here.

 

The main advantage of this approach is that the exact solution can be obtained for "complete" graphs in polynomial time. ( Please

note that the word "complete" which is mentioned here is the same mathematical term used in graph theory ). I tried out the

"complete" graph examples in the textbook using pen and paper and they are giving the exact solutions. Now the only thing is that

solution needs to be tested on further complete graph examples using computers and software by scientists. Also the solution is

polynomial time, because the solution is a new type of modified and improved version of the nearest neighbour method. And

everyone knows that the nearest neighbour method is an approximate method which is polynomial time method. But this new

modified method, gives exact solution to "complete" graphs and it is polynomial time also.

 

In graph theory, a complete graph of n vertices has [ n(n-1)/2 ] edges. So when implementing the algorithm, in the worst case, all

the edges may have to be taken for processing. Also for each edge, the left vertex and the right vertex has to be taken for

processing. So the number of times the edges have to be taken for processing = number of edges * 2 = [ n(n-1)/2] * 2 = n(n-1) =

n^2 - n . So the processing time for the algorithm in the worst case = O(n^2) ie:- it takes polynomial time. ( Here "^" means

raised to ). In the example that I have given for describing how the algorithm works, I have taken a random edge in order to show how the

algorithm works. Where the algorithm is taken with the minimum weight edge , the process is shown between the headings

"Beginning of second example" and"End of second example" and this description is short and easy for viewing.

 

I am claiming that I have tried the algorithm on all the examples given in the theory sections of the 2 textbooks and they give

exact solutions. But I dont have mathematical proof. For graphs that are not complete, I cannot claim that it will give the exact

solution, but I can only say that they might give the best solution. That is how far have I have tested. For other scientists, to get

further convinced, it is better, if they try out this algorithm on more complete graphs at least using pen and paper for the time

being instead of using computers. I am not forcing anyone to try it out. A lot of Mathematicians are saying that there might never

be a solution to this problem, so I thought it was a little exciting if this algorithm would provide any clue which could further

advance the research of the scientists. For proof of such problems, advanced degrees in maths is required like B.Sc, M.Sc, PhD etc.

I don't even have a B.Sc degree, but only a B.Tech Degree. But the mathematics that I have learnt in B.Tech is not formal enough

for finding a proof of such theorems. I can say that what I have given in the post is a " conjecture ". This word is more suitable.

 

I will try to put the explanation of the algorithm in very simple terms as far as possible. All Discrete Mathematicians know about

the nearest neighbour method. In the nearest neighbour method, a random edge is taken and the nearest neighbour method is

applied starting from that edge. This is the method that is known that is known to everyone. So when the nearest neighbour

method is done, the process is O(1). Now in my method ( if for example the worst case is taken ie:- every edge of the complete

graph is taken ( Also suppose the complete graph consists of "n" edges. ) ) , then the nearest neighbour method is applied to each

edge ( taking the most minimum weight edge first and proceeding in ascending order of the weights of the edges ) , then the

number of hamilton circuits obtained will be "n" hamilton circuits. So now the order will be O(n) because of "n" edges. Now the

most important part of the algorithm is that for each edge, the nearest neighbour method should be applied by starting from the

left vertex of the edge and then the next hamilton circuit should be obtained by starting from the right vertex of the edge by using

the nearest neighbour method. So each edge should contain two hamilton circuits (which is obtained by using the nearest

neighbour method ). So now the total number of hamilton circuits obtained for "n" edges will be " 2*n " hamilton circuits. So now

the the order is O(2n) ie:- O(n). ( Please note that here the number of edges is taken as "n" and not the number of vertices , for

easy understanding.) The most important point is that for each edge, 2 hamilton circuits are required which are produced by

starting from the left vertex and the other by starting from the right vertex of the edge.

 

So the software for this algorithm is already there ie:- nearest neighbour method programs. The only modification that is needed for the software is that the nearest neighbour method should be applied to each edge, and for each edge, the nearest neighbour method should be

applied to the left vertex and the right vertex of each edge. So for a complete graph of "n" vertices, in the worst case, there are "2n"

hamilton circuits. Then the minimum weight hamilton circuit among all these hamilton circuits is taken as the shortest weight hamilton circuit.