Homework #3, cs480, 30p, due: 11/20/17 at 11:59pm
The Traveling Salesman Problem (TSP) is a challenge to the salesman who wants to visit every
location exactly once and return home, as quickly as possible. Each location can be reached from
every other location, and for each pair of locations, there is metric that defines the travel time
between them. Given the following two graphs
� �
�
�
�
���
��
���
�
��
��
��
��
��
�
��������
�
�����
��
�
�����
��
�
����� �
�
�������
�
�����
��
�
�����
��
�
����� �
�
�����
��
�
�������
911
15
10
9
15
10 9
10 11
8
16
14
13
Medford
Everett
Arlington
CambridgeBelmont
Somerville
6
Figure 1: Example input to the TSP
2 Metric TSP
In general, we can say nothing about the weights of edges in a given TSP
graph except that they are positive. Metric TSP is an special case of the
TSP that satisfies the triangle inequality. The triangle inequality ensures
that a direct path between two vertices is at least as short as any indirect
path. This is called the triangle inequality because no 1 side of a triangle
can be longer than the sum of the other 2.
Definition 2.0.1 A complete graph satisfies the Triangle Inequality if
∀i, j, k : wi,k ≤ wi,j + wj,k.
The example given in figure 1 satisfies the triangle inequality and therefore
this is a case of Metric TSP. On the other hand, there are commonly occurring
examples on non-metric TSP. If the weights represent something like the cost
of airline tickets, for example, there is no reason to expect the input would
satisfy the triangle inequality; it is often the case that taking an indirect
route is less expensive than a direct route.
2
your task is to write Lisp functions to support hill-climbing to solve TSP for it.
1. (2p) How would you represent the edge costs to support your code? Write the chosen data
Lisp data structures for both graphs.
2. (3p) Write a Lisp function InitLoop which takes an initial loop with all cities listed in alpha-
betical order and produces its random permutation. Your code must produce a real random
shuffle of the initial loop.
3. (5p) Write a Lisp function LoopCost which computes the cost for a given loop.
4. (10p) Write a function ImproveLoop which takes a given loop and improves it if possible. The
improvement should use 2-opt heuristics which removes a pair of edges out of the loop and
reconnects the loop to lower its cost if possible. There is only one way to reconnect a pair of
edges to make a legal loop and it is shown in this figure
u u u u
u u u u
©©
© HHH
¥
¥
¥
¥
¥
¥
¥
¥¥HHH ©©
©
Q
Q
Q
Q
Q
Q
Q
QQ
Figure 1. A 2-opt move
uu u
uu u
uuu
A
A
A
A
A
A
A
A¢
¢
¢
¢
¢
¢
¢
¢
AA
@@
¢¢
°°
PP≥≥
Figure 2. A 3-opt move
4.1. 2-opt and 3-opt
The 2-opt algorithm basically removes two edges
from the tour, and reconnects the two paths created.
This is often refered to as a 2-opt move. There is only
one way to reconnect the two paths so that we still
have a valid tour (figure 1). We do this only if the
new tour will be shorter. Continue removing and re-
connecting the tour until no 2-opt improvements can
be found. The tour is now 2-optimal.
The 3-opt algorithm works in a similar fashion, but
instead of removing two edges we remove three. This
means that we have two ways of reconnecting the three
paths into a valid tour1(figure 2 and figure 3). A 3-opt
move can actually be seen as two or three 2-opt moves.
We finish our search when no more 3-opt moves can
improve the tour. If a tour is 3-optimal it is also 2-
optimal [5].
If we look at the tour as a permutation of all the
cities, a 2-opt move will result in reversing a segment
of the permutation. A 3-opt move can be seen as two
or three segment reversals.
Running the 2-opt heuristic will often result in a tour
with a length less than 5% above the Held-Karp bound.
The improvements of a 3-opt heuristic will usually give
us a tour about 3% above the Held-Karp bound [1].
1not including the connections being identical to a single 2-
opt move
uu u
uu u
uuuAA@@
¢¢
°°
PP≥≥
Figure 3. A 3-opt move
4.2. Speeding up 2-opt and 3-opt
When talking about the complexity of these k-opt
algorithms, one tends to omit the fact that a move can
take up to O(n) to perform (see section 4.8).
A naive implementation of 2-opt runs in O(n2),
this involves selecting an edge (c1, c2) and searching
for another edge (c3, c4), completing a move only if
dist(c1, c2) + dist(c3, c4) > dist(c2, c3) + dist(c1, c4).
An observation made by Steiglitz and Weiner tells
us that we can prune our search if dist(c1, c2) >
dist(c2, c3) does not hold. This means that we can
cut a large piece of our search by keeping a list of each
city’s closest neighbors. This extra information will of
course take extra time to calculate (O(n2log2)), and
also needs a substantial amount of space. Reducing
the number of neighbors in out lists will alow this idea
to be put in practice.
By keeping the m nearest neighbors of each city we
can improve the complexity to O(mn). But we still
have to find the nearest neighbors for each city. Luckily
this information is static for each problem instance, so
we need only do this calulation once and can reuse it
for any subsequent runs on that particular problem.
This speedup will remove the 2-optimality guaran-
tee, but the loss in tour quality is small if we choose
m wisely. Choosing m = 20 will probably reduce the
quality by little or nothing. Choosing m = 5 will give
us a very nice increase of speed at the cost of some
quality[1].
4.3. k-opt
We don’t necessarilly have to stop at 3-opt, we can
continue with 4-opt and so on, but each of these will
take more and more time and will only yield a small
improvement on the 2- and 3-opt heuristics.
Mainly one 4-opt move is used, called “the crossing
bridges” (Figure 4). This particular move can not be
sequentially constructed using 2-opt moves. For this to
be possible two of these moves would have to be illegal
[5].
5. (10p) Write a function SolveTSP which solves TSP given an input graph defined in part 1.
Your code should use the functions written in parts 2-4.
Instructions for submission:
1. Using script or dribble, you are to capture the output of a Lisp session in which you success-
fully load and execute your code, showing sufficient testing of your function(s). of execution
of each of your functions. You will attach these results in your email (see next step) as
“output.txt”.
2. Send a SINGLE email to ple13gmu.edu formatted in the following way:
– the subject field of the email should read: CS480:HW3
– Please attach your lisp file in the email. The file should be called “yourNetIDHW3.lisp”
where your netID is the first part of your GMU email (mine would be “zduricHW3.lisp”.
The body should include:
Your GMU net id
Your name
Homework #3
As a safety precaution, always CC yourself when you submit homework this way and keep it
around until it has been graded and returned.
FINAL NOTE: we will test all code using MOSS.