# Thread: Travelling Salesman Problem - Part 6

1. I am giving a very simple explanation of the algorithm so that it becomes easier to understand.

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.

End of posting  2.

3. Um, good for you - what are you going to do with the prize money?  4. The "starter edge method" given in the post can be written in short form as "SEM". In order to create a software for "SEM" may take a long time. So in order to quickly get results for testing, I am giving a modified version of the starter edge method which I will call as "modified starter edge method" or in short as "MSEM".

The "Nearest Neighbour Method" is written in short form as "NNM".

The minimum hamilton circuit can be found from "MSEM" and it will give the same minimum hamilton circuit as the "SEM".

Why I am giving the "MSEM" is because the "SEM" may take time to understand because of the many notations, although the algorithm is very simple.

Since the time complexity of the travelling salesman problem is more important and since the time complexity of "MSEM" is O(n^2), "MSEM" can be used for testing and getting the results quickly.

In the "NNM", a random vertex is taken to get the approximate minimum weight hamilton circuit.

The "NNM" is mainly used in the "MSEM".

In "MSEM", eventhough the "NNM" is used, the edges of the graph are considered very important.

So the "MSEM" is as follows.

Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex.
Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained. Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4".

And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph.

So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed.

Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM".

Now using computers and a brute force algorithm, find all the possible hamilton circuits in the graph and find the 100% optimal weight hamilton circuit. Now compare the weight of this hamilton circuit with the minimum weight hamilton circuit obtained by using the "MSEM".

As far as possible, the complete graph example should be limited to less than 10 or 20 vertices, in order for the computers to quickly find the 100% optimal hamilton circuit and then use the hamilton circuit to compare with the weight of the hamilton circuit obtained by using the "MSEM".  5. Please don't start any new threads. This could have all been posted in a single thread.  6. The "starter edge method" algorithm can be used for any number of vertices "n" and the algorithm still works in polynomial time. An accurate number is that for a graph with n number of edges, there will be 2n hamilton circuits for weight calculation and comparison. So only 2n hamilton circuits needs to be processed no matter how large n may be.

The brute force algorithm I mentioned in the previous post is the different kind of algorithms and software that other scientists might use to get the 100% convincing optimal weight hamilton circuit or the exact solution, which they can use to compare with the weight of the hamilton circuit that is obtained using my method.

In order to avoid confusion about the "MSEM" in the previous post, I will write this algorithm with beginning and an ending tag. Notations used here are the same as that used in the previous post.

[ Beginning of "MSEM" ]

Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex.

Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained. Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4".

And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph.

So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed.

Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM".

[ End of "MSEM" ]  7. I mentioned about the time complexity of the "MSEM" in the previous post. What I meant to say was that the both "SEM" and "MSEM" are polynomial time methods. So which algorithm (ie:- "SEM" or "MSEM") is more efficient is not important, because the aim of all scientists at the present moment is to find a polynomial time solution for the Travelling Salesman Problem. So for the time being it does not matter whether "SEM" or "MSEM" is used to find the minimum weight hamilton circuit. ( As mentioned in the previous post "SEM" denotes "starter edge method" and "MSEM" denotes "modified starter edge method" )  Tags for this Thread
 problem, salesman, solution, travelling Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement