First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in a reasonable amount of time. Because with each additional point, the number of possible routes is greatly increased. This is in terms of a factorial function:
n!
Where 'n' is the number of points.
I am doing a project that is attempting to examine the mathematical properties of different algorithms that provide an answer for the TSP. I am trying to examine the relationship of the time it takes to produce an answer, and how close that answer is to the correct answer. This means that I am checking every possible route using a brute force algorithm, and then will be comparing the other algorithms, and their shortest length to that of the correct answer.
Currently I am comparing the Greedy salesman method, and the brute force method, but I would like some other fairly simple algorithms that can be used for the problem. If there are any common methods that I should do more research into, or any methods that work well, please tell me along with the basic concept behind that process. For example the Greedy salesman method is always going to the closest point, and the brute force method is checking all of the possible routes.
I appreciate any of the algorithms or methods that are suggested.
