Practice Problems for Chapter Six

Part I (Multiple Choice). Circle the correct answer.

  1. The repetitive nearest neighbor algorithm for solving the Traveling Salesman Problem is
    1. a) an optimal and efficient algorithm
    2. b) an optimal and inefficient algorithm
    3. c) an approximate and efficient algorithm
    4. d) an approximate and inefficient algorithm
    5. e) None of these

  2. The brute-force algorithm for solving the Traveling Salesman Problem is
    1. a) an optimal and efficient algorithm
    2. b) an optimal and inefficient algorithm
    3. c) an approximate and efficient algorithm
    4. d) an approximate and inefficient algorithm
    5. e) None of these

  3. Which of the following algorithm(s) is(are) optimal and efficient?
    1. a) Cheapest Link algorithm for solving the TSP
    2. b) The brute force algorithm for solving the TSP
    3. c) Repetitive Nearest Neighbor algorithm for solving the MST problem
    4. d) a and c
    5. e) None of the above

  4. The term optimal may be used to describe the
    1. cheapest route
    2. shortest route
    3. fastest route
    4. All of the above
    5. None of the above

    A UPS driver starting at his headquarters (A), must deliver packages to 4 different locations (B, C, D, and E). The trip must start and end at A. The graph below shows the distances between the locations. We want to minimize the total distance the driver drives. Use this info to answer Problems 5 - 7.


  5. The nearest neighbor algorithm applied to the graph yields the following solution:
    1. A, B, C, D, E, A
    2. A, C, D, B, E, A
    3. A, B, E, C, D, A
    4. A, E, B, C, D, A
    5. None of the above

  6. The cheapest link algorithm applied to the graph yields the following solution:
    1. A, B, C, D, E, A
    2. A, C, D, B, E, A
    3. A, B, E, C, D, A
    4. A, E, B, C, D, A
    5. None of the above

  7. The weight of the circuit yielded by the nearest neighbor is:
    1. 63
    2. 64
    3. 70
    4. 53
    5. None of these

  8. The weight of a circuit is:
    1. the sum of the weights of the vertices
    2. the sum of the weights of the edges
    3. the sum of the weights of vertices and the edges
    4. All of the above
    5. None of the above

  9. Using the repetitive nearest neighbour algorithm the best circuit is the one that uses ----- as its home vertex.
    1. A
    2. B
    3. C
    4. All are the same
    5. None of the above

  10. How many Hamilton circuits does a complete graph of 8 vertices (with no loops or repeated edges) have?
    1. 720
    2. 40320
    3. 5040
    4. 8!
    5. None of the above

  11. Assume you have a complete graph (with no loops or repeated edges) of 25 vertices and a super-super fast computer that finds one trillion (10,000,000,000,000 ) Hamilton circuits per second. About how long will it take your computer to solve a TSP using the brute force algorithm with a short cut (checking only half of the total number)?

    1. about 360, 000 hours
    2. about 360, 000 days
    3. about 360, 000 years
    4. about 245, 000 years
    5. None of the above

    Part II: Show all your work.

    Here is a mileage chart for six cities in Virginia (Alexandria, Harrisonburg, Norfolk, Richmond, Williamsburg, and Winchester). Use this chart to answer questions 12 through 15. 
    		Alex   Hrsnbrg 	Nrflk 	Rchmnd 	  Wlmsbrg	Wnchstr
Alex 		* 	121 	190 	 104 	  148 	 	  70
----------------------------------------------------------------------
Hrsnbrg 	121  	 * 	222 	 131  	  180 	 	  68
----------------------------------------------------------------------
Nrflk		190	222	 *	  93	   43		 222
----------------------------------------------------------------------
Rchmnd 		104     131 	 93 	   *  	   51   	 136
----------------------------------------------------------------------
Wlmsbrg 	148 	180 	 43 	  51 	    * 		 179
----------------------------------------------------------------------
Wnchstr   	70  	 68     222      136  	   179   	  *
----------------------------------------------------------------------
  12. Use the nearest neighbor algorithm, starting in Richmond, to find a Hamilton circuit for a traveling saleswoman that has the eight cities as her jurisdiction.

  13. Use the cheapest link algorithm to find a Hamilton circuit for the same group of cities. Make sure to list the roads in the order they are picked by this algorithm.

  14. Suppose the Secretary of Transportation for the Commonwealth of Virginia decides to inspect all the roads that connect these cities. The trip is going to start in Richmond and will end up back in Richmond. Is there a way the secretary can do it without driving over any road more than once? Why? Why not?

    If not, what is the minimum number of roads that need to be repeated to guarantee a complete inspection of the roads with the shortest possible total distance?

    Part III: Discuss the following Briefly

  15. How the repetitive neighbor algorithm for solving TSP works.

  16. The difference between Brute-Force and Cheapest Link alogorithms.