"Islands!" is a Java program which examines the "classic" Travelling Salesman Problem. Students are challenged to find the "best" route for an airplane, such that each island is visited once and the plane returns to its starting island.
If you have a screen resolution of 640 X 480 or less I would recommend running the small screen version (same size as shown above)
Islands! for small screen (500 X 334).
If you have greater resolution try
Islands! for large screen (600 X 400)
When the program starts 10 islands will appear on the map and the Edit "Route" button will be selected.
Edit Panel - Route: In this mode, the background of the "Edit" panel will be cyan. The button "clear" will clear all routes (lines) connecting the islands. The "add" button will allow you to add route segments between islands by clicking on each of the two islands. An island icon will get bigger when it is selected. As a route is constructed, a circle graph will appear in the bottom left part of the frame, and will be completely red when the route is complete. The "delete" button will allow a segment between a previously selected and newly selected city to be deleted. The "random" button will create random route connecting all the islands. Either the delete or add buttons may be turned off by clicking in the blue background area. A city can be moved by clicking and dragging it in the map.
Edit Panel - Isles: In this mode, the background of the Edit panel will be pink. The button "clear" will clear all islands in the map. The "add" button will allow you to add an island (up to 99) anywhere you click in the map. As cities are added the total number of possible route is computed and listed in the lower right section of the frame. if there are "n" islands, the number of routes is (n-1)! = (n-1) X (n-2) X (n-3) X ... X 3 X 2 X 1. The "delete" button will remove any island that is "clicked". The "random" button will randomly move all islands in the map. Cities can also be moved in this mode, provided that the add or delete buttons are not "on".
The Search for Routes panel contains 4 buttons. The "Best" button will perform a full search, computing the total distance for each route. Since the number of routes can be very large, completing a full search may take a long time, depending on your computer and browser's java implementation. While the search is performed, a clock will time how long the search takes, and the number of routes visited will be updated every second. The Stop button will end the search. The Better and Good buttons perform partial searches based on heuristics. These should execute very quickly (the time will be measured in milliseconds) and will usually return the best solution, but not always. When there are more than 21 cities you must use one of these search buttons. See the technical details page for a description of these search strategies and some benchmark times on doing full searches.
Stars and Points can be earned by first constructing a complete route in the Edit Panel - Route - add mode and then selecting a search strategy. If the route you created is among the 3 best you will earn a star (gold, silver, or red) and points depending on the place and number of islands. After a search, the top five routes are saved and can be viewed by selecting a button in the "Top Five" panel. The button labeled "0" will recall the route you constructed. The computed distance (Euclidean) is listed to the right of the Top Five panel. The map region corresponds to a unit square.
(Clicking this image will load the small screen version. Click here ) for the large screen version.
Sample Islands! screen in "Edit-Route" mode.
I hope that you and your children enjoy and benefit from this program.
If you have any comments or constructive criticisms you can send email to
Bill Szymczak.