2.5 Traveling He-Man
You must submit this in an archive named "tsp.zip".
Flavor text: In response to the critical acclaim of Final Fantasy X-2, Square Enix is developing a JRPG based on the He-Man Mythos. Attempting to capture the ellusive "Computer Science nerd" demographic, Square Enix has determined that Eternia’s many locales must be explored in a shortest-path fashion. Hoping to get first post on a Slashdot thread about completing the game, you have taken CS 312.
You must solve the Traveling Salesman Problem using Branch and Bound.
Your program should accept a description of an undirected graph in the following format:
| ‹graph› | ::= | ‹integer› ‹edge›* |
| ‹edge› | ::= | ‹node› >- ‹weight› -> ‹node› |
| ‹node› | ::= | ‹integer› |
| ‹weight› | ::= | ‹integer› |
You may want to write a program to generate such inputs.
<start node> -> <node> -> <node> ... -> <end node> |
Cost: <weight> |
You must test your program on graphs of at least 20 nodes.
Your program must output the time it took to solve the problem (not read in the input and solve the problem.)
If you want to, follow these directions instead.