The problem of Traveling Salesman
New look at an age old problem....that of problem of Traveling Salesman.
No not airports, lost luggage and RyanAir but the mathematical problem. The basis of Traveling Salesman Problem(TSP) is, given a list of cities and their distances, the task is to find a shortest possible tour that visits each city exactly once. The problem was first formulated in 1930 and some work has been done since but never a new approach.
Andrej Kazakov has come up with a new algorithm to solve TSP, which according to him "looks very promising". Could that be an underestimate?
Andrej looked at existing solutions to TSP, the most popular approaches being local search and divide and conquer but a new approach was an algorithm called 'Building Block Hillclimber' and applied a combination of approaches so that he substantially improved its quality, performance and range of applications.
The algorithm is still incomplete, but its current shortcomings have been thoroughly analysed and it has been substantially improved.
you can see Andrej Kazakov paper on the link below
http://www.alphagalileo.org/AssetViewer.aspx?AssetId=11321
No not airports, lost luggage and RyanAir but the mathematical problem. The basis of Traveling Salesman Problem(TSP) is, given a list of cities and their distances, the task is to find a shortest possible tour that visits each city exactly once. The problem was first formulated in 1930 and some work has been done since but never a new approach.
Andrej Kazakov has come up with a new algorithm to solve TSP, which according to him "looks very promising". Could that be an underestimate?
Andrej looked at existing solutions to TSP, the most popular approaches being local search and divide and conquer but a new approach was an algorithm called 'Building Block Hillclimber' and applied a combination of approaches so that he substantially improved its quality, performance and range of applications.
The algorithm is still incomplete, but its current shortcomings have been thoroughly analysed and it has been substantially improved.
you can see Andrej Kazakov paper on the link below
http://www.alphagalileo.org/AssetViewer.aspx?AssetId=11321
posted by Kev King at
14:19
0 Comments
