Netscape 2.0 in 32 bits (and patience) or other Java-browser required!
You are a Traveling Salesman - and you should visit a number of cities, before you return home. You want to save gasoline and find the shortest route....
| Q: How do you save gasoline? |
| A: Try the Java-applet below.. |
(BTW, this problem is similar to finding the shortest cable for a token-ring
network.)
Further, you're crossing a border line several times. Depending on the presence and
the mood of the toll controller this may cost you money - or save you money if toll controller wants to - off the record- buy some of your goods...
TOTAL COSTS = length of route + Toll Costs
Press "** TRY 1000 **" a couple of times to see how the applet shortens the
route. Not every attempt yields a shorter route.
If you introduce a negative "Toll Fee" the applet tries to avoid crossing the
red border line. However, if the "Toll Fee" is positive, i.e. you manage to make
money dealing with the toll officer, the applet seeks to cross the border suspiciously
often..
A small work-animation is shown for larger jobs (>1000 iterations)
The so-called "Traveling Salesman Problem" this applet solves, is a well known mathematical problem from Operations Research - and numerous methods has been suggested through the last 40 years. The implemented algorithm is by far the best, however, as it provides quick and good solutions (not necessarily the best). The scheme can be inspected by setting the "Iteration" to "1" and press the "Try 1" several times.
To find the optimal solution you have to go through all possible routes, and
the numbers of routes increases exponential with the numbers of cities.
("NP-complete") This means that a few years ago computers were NOT able
to calculate the optimal solution if you had more than 50 cities! Which allows me to
mention the "Corn flakes-method" as introduced by my former math-teacher,
Jacobsen, to solve the TSP-problem of say the capitol cities of the USA.
Don't forget that the number of routes with 50 cities is (50-2)!,approximately:
12.412.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000
This applet was written using JDK 1.0, WIN95 and has 350 programming lines. The applet is my first C-like program ever. Anyway, here is the source (TRAVEL.JAVA 12.5 kb) - true C-programmers might find the source amusing - I have a Delphi background, which however taught me OOP. Please harass me with comments and suggestions :=)!
Possible updates of the source will be FTP-available at here.
Please send comments or suggestions to [email protected] - please use subject
"TRAVEL".