HTML5 "Traveling Salesman Problem" (TSP)
The traveling salesman problem is a classic algorithmic problem that dynamic programming can solve. I chose this algorithm to test out HTML5's <canvas> tag with the 2D context.
You can move the nodes around on the canvas, and find the route again. Each found route in the search will display below the graph.
The algorithm I use is based on Robert Sedgewick's "Exhaustive Search"
chapter in "Algorithms in C++" like this:
visit(n) {
val[n] = ++id;
for(c=0; c < V; c++)
if (a[n][c])
if (val[c] == 0)
visit(c);
id--;
val[n] = 0;
}
Where V is the number of vertices or nodes,
a is an adjacency matrix,
val is an array of all the nodes,
and id is the current depth.
Besides modifying the code to keep track of Hamilton cycles, I added heuristics to stop searching if the current weight (distance between nodes) is greater than the minimum weight of any cycles found.
Further Work
- Make interface to add new nodes and edges
- Search slowly and highlight the edges or nodes during the search
- Display error if no cycles exist
- Render the results in canvas
- Change Node.mouse() to work only with it's own member variables and return a boolean value indicating if the canvas is dirty.
- Display a pixel based search path where X is incremented each backtrack and Y is the node id.