The problem is old and still unsolved. It's clear that some of all possible trips has to be the shortest (there might be more than one beeing equally short), but at the present no other method is known but to calculate all possible tours. And the number of trips grows very rapidly with the number of cities - and eventually the computation of the trips overwhelms any computer.
Below are some Java Applets to visualize the problem.
They start with a routine that is in practical use, and explore the efficiency
of it and some variations.
You can point with the mouse and click to locate cities as you wish.
(Limits: at most 150 cities and at least 3 pixels apart)
Click on the "solve" button and the applet shows how its algorithm solves the problem. The length given for the so constructed tour presumes that the size of the area is 100 * 100 length units.
The "random" button gives 100 cities randomly located.
The "series" button gives a series of 100 sets of 100 cities randomly located, and a mean distance of the tours.
A first attemptMore people than travelling salesmen are daily facing the problem. How do you plan delivery of goods to randomly spread customers ?One way: Start with the unsorted delivery notes. Take three and put them in the order these three customers are best visited. Take the fourth note and stick it in among the three previous, where the detour to the fourth customer will be shortest. Continue this way until all delivery notes are sorted. This simple way of sorting destinations actually gives a rather good result. Try it yourself ! Point with the mouse, click and locate points, or click the "random" button and let the computer locate 100 points. Then click the "solve" button, and follow the growth of the tour. In practice one often discovers during the sorting, that a new address fits badly with the previous order, and one has to do partial resortings. | Principle of least effortIn "A first attempt" the addresses to be sorted next are randomly chosen. One takes what one is given and it becomes what it becomes.As this seems to be a somewhat haphazard manner, one might want to do it in a more methodical way. Why not use the principle of always choosing as next address to add, the one which will give the least detour. This principle is used here, and in physics there are many examples where the principle of the least effort is governing choises of ways. The result ? Try it yourself ! Taking a closer look at the figures generated on the random sets of points, one observes that they are remarkable thin and slender. That's the way it will be if one starts with a small figure and always adds as little as possible. We have got what we asked for, but not at all what we wanted. The wanted figure should be as fat and round as possible. The ideal would be a circle, but randomly located points won't be situated that nice. | The shell principleThe previous example showed the result of starting with a little figure and add as little as possible. Let's do it the other way around.Start with making a ring around all points, provide the set of points with a shell. Then gradually link the inner points into that shell. We are here working from the outer towards the inner, whole time making so small changes as possible. It's a simple principle, but it leads to considerable improvements. Yet it's still easy to detect flaws in the figures. Some figures have tours crossing themselves, and there are too many irritating long narrow inlets. We don't want fiords, we want bays. It should be noted maybe, that here the twodimensional properties of the picture are used for the first time. In the two previous examples, the algorithms only use the distances between points, i.e. scalars which could represent many things. | The shell principle with smoothingAs mentioned before, in practice partial resortings are often required when a new address fits badly in the previous sorting order. Let us do the same thing here.Here the tour is generated as in the previous example, but after every new point the tour is checked, and if then one or several adjacent points fit better in an other place in the tour order, the tour is reorganised (and then the resorted tour is checked again until no further improvements can be made). In this way we try to smooth the bumps that occur. Do try to randomize and order a set of points in the previous applet, and compare it with the picture of the same set obtained here, when smoothing is added. There will be many examinations during the growth of the tour, which will affect the execution time (Java isn't too fast). But the result will be affected too: the mean distance will be cut down with more than 5% or allmost 50 length units and will end decidedly under 800. |
Our visual systems are silently making heavy computations, and when the impressions reach our consciousness many relations are already established - what is inside, what is outside and so on. This might be the reason for the illusive and escaping nature of some problems in graph theory - you can feel what is right, but it can be very difficult to prove it. Maybe the wanted relations are in a stage earlier than where they easily can be translated into words (symbols).
Isadora Duncan once was asked to tell what her dance was about. She
answered - "if I could tell it, I wouldn't have to dance it".
| Created 00 03 31 |
Visitors:
|