A,
D, B, C, AGreat Ideas in Mathematics
Math 110 - Fall 2007
Ch. 6: Travelling Salesman problem
Practice questions
Some Answers may be below.
1. The number of Hamiltonian circuits in K15 is
A 15
B 14!
C 15!
D 15x14 / 2
E none of these
The next four questions refer to the following situation: A delivery truck must deliver furniture to 4 different locations (A, B, C, and D). The trip must start and end at A. The graph below shows the distances between locations (in miles). We want to minimize the total distance traveled.
2. The nearest neighbor algorithm applied to the graph yields the following solution:
A
A,
D, B, C, A
B A, C, B, D, A
C A, D, C, B, A
D A, B, D, C, A
E none of these
3. The cheapest link algorithm applied to the graph yields the following solution:
A A, B, D, C, A
B A, D, B, C, A
C A, C, B, D, A
D A, D, C, B, A
E none of these
4. The repetitive nearest neighbor algorithm applied to the graph yields the following solution:
A A, B, D, C, A
B A, D, B, C, A
C A, C, B, D, A
D A, D, C, B, A
E none of these
5. An optimal solution to this problem is given by
A A, B, D, C, A
B A, B, C, D, A
C A, C, B, D, A
D A, D, C, B, A
E none of these
The next four questions refer to the following situation: A traveling salesman’s territory consists of the 5 cities shown on the following mileage chart. The salesman must organize a round trip that starts and ends at Louisville (his hometown) and will pass through each of the other four cities exactly once.
6. The nearest neighbor algorithm applied to this problem yields the following solution:
A Louisville, Chicago, Buffalo, Boston, Columbus, Louisville.
B Louisville, Columbus, Buffalo, Boston, Chicago, Louisville.
C Louisville, Boston, Buffalo, Chicago, Columbus, Louisville.
D Louisville, Columbus, Chicago, Buffalo, Boston, Louisville.
E none of these
7. The cheapest link algorithm applied to this problem yields the following solution:
A Louisville, Chicago, Buffalo, Boston, Columbus, Louisville.
B Louisville, Columbus, Buffalo, Boston, Chicago, Louisville.
C Louisville, Boston, Buffalo, Chicago, Columbus, Louisville.
D Louisville, Columbus, Chicago, Buffalo, Boston, Louisville.
E none of these
8. The repetitive nearest neighbor algorithm applied to this problem yields the following solution:
A Louisville, Chicago, Buffalo, Boston, Columbus, Louisville.
B Louisville, Columbus, Buffalo, Boston, Chicago, Louisville.
C Louisville, Boston, Buffalo, Chicago, Columbus, Louisville.
D Louisville, Columbus, Chicago, Buffalo, Boston, Louisville.
E none of these
9. At an average cost of 25 cents per mile, the cheapest possible trip that starts at Louisville and passes through each of the other cities exactly once would cost
A $541.75
B $578.25
C $606.50
D $551.00
E none of these
The next three questions refer to the following situation: A hypothetical management science problem requires us to find the cheapest "supercircuit" in a graph. Three algorithms are available: Algorithm 1; Algorithm 2; and Algorithm 3.
10. Algorithm 1 always produces the cheapest supercircuit. The amount of time it takes to carry out Algorithm 1 doubles every time we increase the number of vertices by one. Algorithm 1 is
A an approximate and inefficient algorithm
B an optimal and efficient algorithm
C an approximate and efficient algorithm
D an optimal and inefficient algorithm
E none of these
11. Algorithm 2 sometimes produces the cheapest supercircuit but most of the time it produces a supercircuit that is only close to being the cheapest. The amount of time it takes to carry out Algorithm 2 is: 1 second for a graph with 1 vertex, 2 seconds for a graph with 2 vertices, ... 5 seconds for a graph with 5 vertices, etc. Algorithm 2 is
A an approximate and inefficient algorithm
B an optimal and efficient algorithm
C an approximate and efficient algorithm
D an optimal and inefficient algorithm
E none of these
12. Algorithm 3 never produces a supercircuit that is off by more than 10% from the cheapest supercircuit. The amount of time that it takes to carry out Algorithm 3 is: 1 second for a graph with 5 or less vertices; 30 seconds for a graph with 6 vertices; 40 seconds for a graph with 7 vertices, and so on, increasing by 10 seconds every time we add a vertex (from 7 vertices on). Algorithm 3 is
A an approximate and inefficient algorithm
B an optimal and efficient algorithm
C an approximate and efficient algorithm
D an optimal and inefficient algorithm
E none of these
13. The repetitive nearest neighbor algorithm for solving the Traveling Salesman Problem is
A an approximate and inefficient algorithm
B an optimal and efficient algorithm
C an approximate and efficient algorithm
D an optimal and inefficient algorithm
E none of these
14. n! =
A n! + (n-1)!
B n! x (n-1)!
C n x (n-1)!
D n + (n-1)!
E none of these
15. In trying to solve a certain traveling salesman problem you find a solution with a total length of X miles. If the length of the optimal solution is L miles, then the relative error of your solution is
A X / L
B X - L
C (X – L) / L
D (X – L) / X
E none of these
16. The number of edges in K10 is
A 90
B 10!
C 45
D 10
E none of these
17. In a complete graph with 14 vertices, A to N, total number of Hamiltonian circuits (including mirror-image circuits) that start at vertex A is
A 15!
B 14!
C (15 x 14)/2
D 13!
E none of these
The
next six questions refer to the following situation. A delivery truck must
deliver 
furniture to 4 different locations (A,B,C, and
D). The trip must start and end at A. The graph in Figure 6.1 shows the
distances between locations (in miles). We want to minimize the total distance
traveled.
18. The nearest neighbor algorithm applied to the graph yields the following solution:
A ACBDA
B ADCBA
C ADBCA
D ABDCA
E none of these
19. The cheapest link algorithm applied to the graph yields the following solution:
A ACBDA
B ADCBA
C ADBCA
D ABDCA
E none of these
20. The repetitive nearest neighbor algorithm applied to the graph yields the following solution:
A ACBDA
B ADCBA
C ADBCA
D ABDCA
E none of these
21. The optimal solution to this problem is given by
A ACBDA
B ADCBA
C ADBCA
D ABDCA
E none of these
22. How many different Hamilton circuits would we have to check if we use the brute force algorithm? (Do not count the same circuit traveled backward.)
A 24
B 4
C 3
D 6
E none of these
23. The length of the shortest possible delivery route is
A 26 miles
B 28 miles
C 22 miles
D 24 miles
E none of these
The next four questions refer to the following situation: Atraveling salesman’s territory consists of the 5 cities shown on the following mileage chart. The salesman must organize a round trip that starts and ends at Minneapolis (his hometown) and will pass through each of the other four cities exactly once.
|
|
Chicago |
Des Moines |
Fargo |
Minneapolis |
Milwaukee |
|
Chicago |
* |
333 |
643 |
409 |
94 |
|
Des Moines |
333 |
* |
477 |
244 |
375 |
|
Fargo |
643 |
477 |
* |
235 |
571 |
|
Minneapolis |
409 |
244 |
235 |
* |
337 |
|
Milwaukee |
94 |
375 |
571 |
337 |
* |
24. The nearest neighbor algorithm applied to this problem yields the following solution:
A Minneapolis, Chicago, Milwaukee, Des Moines, Fargo, Minneapolis
B Minneapolis, Milwaukee, Chicago, Des Moines, Fargo, Minneapolis
C Minneapolis, Des Moines, Chicago, Milwaukee, Fargo, Minneapolis
D Minneapolis, Milwaukee, Chicago, Fargo, Des Moines, Minneapolis
E none of these
25. The cheapest link algorithm applied to this problem yields the following solution:
A Minneapolis, Chicago, Milwaukee, Des Moines, Fargo, Minneapolis
B Minneapolis, Milwaukee, Chicago, Des Moines, Fargo, Minneapolis
C Minneapolis, Des Moines, Chicago, Milwaukee, Fargo, Minneapolis
D Minneapolis, Milwaukee, Chicago, Fargo, Des Moines, Minneapolis
E none of these
26. The repetitive nearest neighbor algorithm applied to this problem yields the following solution:
A Minneapolis, Chicago, Milwaukee, Des Moines, Fargo, Minneapolis
B Minneapolis, Milwaukee, Chicago, Des Moines, Fargo, Minneapolis
C Minneapolis, Des Moines, Chicago, Milwaukee, Fargo, Minneapolis
D Minneapolis, Milwaukee, Chicago, Fargo, Des Moines, Minneapolis
E none of these
27. At an average cost of 50 cents per mile, the cheapest possible trip that starts at Minneapolis and passes through each of the other cities exactly once would cost
A $738.00
B $739.00
C $737.50
D $738.50
E none of these
28. The nearest neighbor algorithm for solving the Traveling Salesman Problem is
A an approximate and inefficient algorithm
B an optimal and efficient algorithm
C an approximate and efficient algorithm
D an optimal and inefficient algorithm
E none of these
29. 500! + 499! =
A 499 x 500!
B 501 x 499!
C 1 + 500 x 499!
D 501 !
E none of these
30 In trying to solve a certain traveling salesman problem you find a solution with a total length of 2800 miles. If the length of the optimal solution is 2100 miles, then the relative error of your solution is
A 30%
B 125%
C 25%
D 130%
E none of these
31. Match the total number of different Hamilton Tours to the order of the complete Graph K having n vertices.
|
K5 Complete graph of order 5 |
|
A |
3 |
|
|
K3 Complete graph of order 3 |
|
B |
2520 |
|
|
K4 Complete graph of order 4 |
|
C |
1 |
|
|
K6 Complete graph of order 6 |
|
D |
12 |
|
|
K7 Complete graph of order 7 |
|
E |
360 |
|
|
K8 Complete graph of order 8 |
|
F |
60 |
32. Match the total number of edges to the complete graph K of order n.
|
K5 Complete graph of order 5 |
|
A |
10 |
|
|
K3 Complete graph of order 3 |
|
B |
6 |
|
|
K4 Complete graph of order 4 |
|
C |
15 |
|
|
K6 Complete graph of order 6 |
|
D |
21 |
|
|
K7 Complete graph of order 7 |
|
E |
3 |
|
|
K8 Complete graph of order 8 |
|
F |
28 |
Created November 4, 2007
Answers
|
1 B 2 C 3 A 4 A 5 C
6 D 7 D 8 D 9 D 10 D
11 C 12 C 13 C 14 C 15 C
|
16 C 17 D 18 C 19 D 20 D
21 C 22 C 23 C 24 B 25
26 27 28 A 29 B 30 E |
31 DCA FEB
32 AEB CDF
|
End of the answers