Traveler Salesman Problem
-
Greedy algorithm’s complexity is O(n^2) and it doesn’t give a good answer for TSP. But in my program greedy algorithm is the basic step for finding the good answer. Greedy algorithm's good side is that takes very little time for computing the answer even though it’s not optimal result.
-
The time issue cannot be solved by the 2opt algorithm so I came up with another theorem that gives a close result to the 2opt algorithm. Actually, this solution still uses 2opt algorithm but not for all nodes. The algorithm has a scale variable which is the dividing value. The algorithm starts with dividing the length of node list to given scale, and names it as iteration number. With for loop (until iteration number is reached), the algorithm takes a part of the node list. This part’s length is equal to given scale variable. After taking a part of the nodes, the algorithm applies the 2opt algorithm for this part. The result is stored in another list that will be the return value of this algorithm. For all parts that is divided from node list, the algorithm applies 2opt for all of them and combines these results to the result list. If scale value does not divide the length of value without remainder, in the end, the algorithm takes these values and applies 2opt for them too. It is very similar to decrease and conquer algorithm but the important information here is that algorithm doesn’t consider the middle of each two-part. That is why algorithm starts with the greedy method so that nodes line as close as possible.