Allow me a little brief introduction. The travelling salesman problem is one of the Millenium problems that has been engaged by mathematicians and computer scientists alike. A million dollar bounty from the Clay Mathematics foundation awaits the lucky chap who manages to solve the problem.
The problem is as follows. Imagine there are seven (or think of any numbers you like) towns spread out over a geographical location. A salesman has to go through all the towns and return back to the town that he originally started out from. Think of the shortest route by arranging the sequence of the towns the salesman should visit.
Intuitively, the number of links should be N, where N is the number of towns that the salesman must visit. It appears that the problem is a graphical one. Nonetheless, there are many ways to attack the problem. The ACO (Ant Colony Optimization) algorithm provides a heuristic solution, which is at best approximate. Basically, ACO harnesses the parallel processing capability of the ant colony, and sends out ants in different directions, which creates pheromone trails, resulting in routes to the food source, or the salesman's final destination, before he returns back from where he started out.
Personally, rather than going through every town using every ostensible heuristic algorithm, the geometrical layout patterns formed by the settlement of towns should be studied. If all the towns are separated from left to right in a linear fashion, intuitively the journey will be a circular roundabout trip from the leftmost town to the rightmost town and back again or vice versa (See Figure A).
However, what happens if we have a nucleated layout of towns? I have always been inspired by phase space plots of oscillating pendulum with damping effect (See Figure B Part 1), hence the inspired solution. Imagine the pattern created by the routes as ever shrinking concentric circles.
Thus, my suggested simplified algorithm will be as follows:
1) Search for possible nucleated settlement of towns and the possibility of multiple nucleated settlements of towns (in case of Figure C). Important rule: Distance between inner and outer concentric rings must be greater that the adjacent distance between towns. If there are multiple nucleated settlements of towns, shrinking concentric circles will be drawn for each settlement, followed by the joining of settlements (See Figure C).
2) If no nucleated settlement of towns exists and the towns are scattered from left to right as shown in Figure A, trip will be a circular roundabout trip from left to right or right to left.
Probably experts out there will find my work falling short of quality content, but nonetheless, it is great fun trying to work out possible solutions to the Millenium problem. It remains to be seen if my suggested algorithm can solve the problem in polynomial time. *Chuckles*
The problem is as follows. Imagine there are seven (or think of any numbers you like) towns spread out over a geographical location. A salesman has to go through all the towns and return back to the town that he originally started out from. Think of the shortest route by arranging the sequence of the towns the salesman should visit.
Intuitively, the number of links should be N, where N is the number of towns that the salesman must visit. It appears that the problem is a graphical one. Nonetheless, there are many ways to attack the problem. The ACO (Ant Colony Optimization) algorithm provides a heuristic solution, which is at best approximate. Basically, ACO harnesses the parallel processing capability of the ant colony, and sends out ants in different directions, which creates pheromone trails, resulting in routes to the food source, or the salesman's final destination, before he returns back from where he started out.
Personally, rather than going through every town using every ostensible heuristic algorithm, the geometrical layout patterns formed by the settlement of towns should be studied. If all the towns are separated from left to right in a linear fashion, intuitively the journey will be a circular roundabout trip from the leftmost town to the rightmost town and back again or vice versa (See Figure A).
However, what happens if we have a nucleated layout of towns? I have always been inspired by phase space plots of oscillating pendulum with damping effect (See Figure B Part 1), hence the inspired solution. Imagine the pattern created by the routes as ever shrinking concentric circles.
Thus, my suggested simplified algorithm will be as follows:
1) Search for possible nucleated settlement of towns and the possibility of multiple nucleated settlements of towns (in case of Figure C). Important rule: Distance between inner and outer concentric rings must be greater that the adjacent distance between towns. If there are multiple nucleated settlements of towns, shrinking concentric circles will be drawn for each settlement, followed by the joining of settlements (See Figure C).
2) If no nucleated settlement of towns exists and the towns are scattered from left to right as shown in Figure A, trip will be a circular roundabout trip from left to right or right to left.
Probably experts out there will find my work falling short of quality content, but nonetheless, it is great fun trying to work out possible solutions to the Millenium problem. It remains to be seen if my suggested algorithm can solve the problem in polynomial time. *Chuckles*
2 comments:
Uh suggesting an polynomial approximation to the travelling salesman problem does not have anything to do with the millenium problem. What you needto do is to get an algorithm which is NP complete (and there are hard and fast rules for certifying it NP complete) and either show it can or cannot be solved in polynomial time.
Yes, my title might be a little misleading, and the original problem is the P vs NP problem, thanks for your reminder. The Travelling Salesman problem is NP-hard though,
Post a Comment