8. Solve the Traveling Salesperson problem using the Exhaustive Search design technique discussed in class. The...

  

Transcribed Image Text:

8. Solve the Traveling Salesperson problem using the Exhaustive Search design technique discussed in class. The salesperson must begin and finish the tour in City B. A B C D A INF 4 7 6 B 4 INF 5 3 CD C 7 5 INF 3 D 6 3 3 INF a. Draw the graph using the data from this adjacency matrix. (3 points) b. State every possible path and its corresponding distance. (6 points) c. Cross out the redundant paths, so no remaining path is an exact reverse of another path. (3 points) d. State an optimal solution. (3 points) 8. Solve the Traveling Salesperson problem using the Exhaustive Search design technique discussed in class. The salesperson must begin and finish the tour in City B. A B C D A INF 4 7 6 B 4 INF 5 3 CD C 7 5 INF 3 D 6 3 3 INF a. Draw the graph using the data from this adjacency matrix. (3 points) b. State every possible path and its corresponding distance. (6 points) c. Cross out the redundant paths, so no remaining path is an exact reverse of another path. (3 points) d. State an optimal solution. (3 points)