Homework 7

Details

Work in groups of zero, one, or two on this project. Submit your code using Webhandin 385-HW7.

1. Implement the backtracking algorithm for Hamiltonian Cycle in Algoraph. When you create the algorithm, use PuzzleInstance as the data type. Your algorithm should either output the Hamiltonian cycle by listing the vertices in the proper order (with spaces between) or "no" if there is no Hamiltonian cycle.

   Run your algorithm on the following puzzles

   1. Lemek (8 vertices)
   2. First Class (9 vertices)
   3. Pete (10 vertices)
   4. Lemeker (12 vertices)
   5. 4 Realz (15 vertices)
   6. Sierpinski Triangle (15 vertices)
   7. c4xc4 (16 vertices)
   8. Hyped Up (16 vertices)
   9. Lemke Kid (16 vertices)
   10. Crossover (17 vertices)
   11. Smal Snake (17 vertices)
   12. Lemke9xC2 (18 vertices)
   13. Dode (20 vertices)
   14. K20 TSP (20 vertices)
   15. Webby Spider (24 vertices)
   16. Choices! (25 vertices)
   17. Spikey (26 vertices)
   18. Tale of Wires (31 vertices)
   19. Snake (35 vertices)
   20. Torus 6x6 (36 vertices)
   21. Gridlick (42 vertices)
   22. Bullseye (48 vertices)
   23. Grid Be Gone (49 vertices)

   You should be able to modify the algorithm ValidTSPSolutionChecker to check the validity of the solutions produced by your algorithm.

   Along with your code, submit a file results7_1.txt that lists all of the above graphs and gives the solution for each. List the solution as "did not finish" for any that your algorithm could not get an answer for.

2. Implement the branch-and-bound algorithm for the traveling salesman problem and solve as many instances from HW 6 as you can. Submit a file results7_2.txt with the names of the graphs for which your algorithm computed an optimal solution and give the solution, including cost, for each.