| To Run: Link: Update to most recent java version. To enter points of interest/vertices/cities, do one of the following: -click on the mesh -enter x, y coordinates and click Enter -specify a number of cities to add and click Random To reset all points click Reset. This applet can compute: -the Minimum Spanning Tree(MST) -the MST joined with a minimum weight Perfect Matching among the vertices of odd degree in the MST -a heuristic solution to the Traveling Salesman Problem(TSP) using Christofides' algorithm, limit of 24 cities -the Optimal solution of the TSP, limit of 9 cities. -sample Contour lines over the mesh to one specified point, limit of 1 city All options should return a bright green lines displaying the appropriate result, after clicking Compute. |
|
| The Research: The Paper The mesh is as you see it a greyscale image. The darker the more costly to travel over that point, or slower, likewise, the lighter the less costly, or faster. With the positions of the cities as shown, the object is to find the quickest path over the mesh from a single city, and jointly find the fastest path around all the cities. Different meshes can be selected in top right menu. |
|
| If you discover problems with the applet - please take a screen shot and send it to me at astuteAjax gmail com cheers! June Andrews | |