An Idea for a Probabilistic Approximation of the Solution to the Travelling Salesman Problem
In one of my classes here at Brigham Young, our group has been asked to come up with a unique idea for getting a good approximation to an optimal tour in the traveling salesman problem. Here's the idea I came up with.
I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?
The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).
Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.
We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.
All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.
We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!
I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!
I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?
The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).
Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.
We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.
All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.
We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!
I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!
Comments
Post a Comment