The cyclic tour before 3-opt asymmetric move can be described as consisting of three consecutive segments:
A B C = B C A = C A B
The 3-opt asymmetric move showed on the diagram transforms the tour into the form:
A' B' C
where symbol prime (') after a letter means that the segment is reversed.
Reversing whole tour doesn't change it, only its natural orientation is reversed, so:
A' B' C = (A' B' C)' = (C)' (B')' (A')' = C' B A
Tour is cyclic, therefore:
C' B A = A C' B = B A C'
This shows us three methods of obtaining result from 3-opt move:
A B C ==> A' B' C C A B ==> A C' B B C A ==> C' B A
In each method different segment remains unchanged in its original place, so we can use this fact to speed up the procedure of making the move.
proc Make_3_Opt_Asym_Move_Fast(tour: var Tour_Array;
p1, p2, p3, p4, p5, p6: Tour_Index;
position: var City_Position_In_Tour) =
var
city: City_Number
left, right: Tour_Index
segment: seq[City_Number] # max. N/2 elements
move_method: int
# the tour consists of three consecutive segments:
# [p6,p1] [p2,p3] [p4,p5] == A B C
# A B C == B C A == C A B
# there are three ways of *performing* the very same
# 3-opt asymmetric move, in each different segment remains
# intact in its original place:
# 1) A B C ==> A' B' C -- doesn't touch C
# 2) C A B ==> A C' B -- doesn't touch B
# 3) B C A ==> C' B A -- doesn't touch A
# Method 1, used so far, is default, but when segment B or A
# has many cities compared to segment C then we choose
# method 2 or 3, to not change the longest segment
let size_A = (N + p1 - p6 + 1) mod N
let size_B = (N + p3 - p2 + 1) mod N
let size_C = (N + p5 - p4 + 1) mod N
let sizeMax = max(size_A, max(size_B, size_C))
move_method = 1
if sizeMax == size_B:
move_method = 2
elif sizeMax == size_A:
move_method = 3
case move_method
of 1: # default method, not changing segment C
...
of 2: # not changing segment B
...
of 3: # not changing segment B
...
else: # we use only 3 methods of performing asym. 3-opt move
discard
The first, traditional method is as follows:
case move_method
of 1: # default method, not changing segment C
# A B C ==> A' B' C
# reverse segment A in place:
left = p6
right = p1
for counter in 1 .. size_A div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
position[tour[left]] = left
position[tour[right]] = right
left = t_succ(left)
right = t_pred(right)
# reverse segment B in place:
left = p2
right = p3
for counter in 1 .. size_B div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
position[tour[left]] = left
position[tour[right]] = right
left = t_succ(left)
right = t_pred(right)
The second method is:
case move_method
...
of 2: # not changing segment B
# C A B ==> A C' B
# make a copy of segment C=[p4,p5]:
segment = newSeq[City_Number](size_C)
left = p4
for pos in 0 .. size_C-1:
segment[pos] = tour[left]
left = t_succ(left)
# move segment A backward, it should end at p4:
left = p6
right = p4
for counter in 1 .. size_A:
tour[right] = tour[left]
position[tour[right]] = right
left = t_succ(left)
right = t_succ(right)
# put copy of reversed C before B in tour:
right = p1
for pos in 0 .. size_C-1:
tour[right] = segment[pos]
position[tour[right]] = right
right = t_pred(right)
The third method is:
case move_method
...
of 3: # not changing segment A
# B C A ==> C' B A
# make a copy of reversed segment C=[p4,p5]:
segment = newSeq[City_Number](size_C)
right = p5
for pos in 0 .. size_C-1:
segment[pos] = tour[right]
right = t_pred(right)
# shift segment B forward, it should end at p5:
left = p3
right = p5
for counter in 1 .. size_B:
tour[right] = tour[left]
position[tour[right]] = right
left = t_pred(left)
right = t_pred(right)
# put the copy of reversed C in its new place in tour:
left = p2
for pos in 0 .. size_C-1:
tour[left] = segment[pos]
position[tour[left]] = left
left = t_succ(left)
Alternative version
Above solution has two disadvantages. Firstly, it is quite complex. Secondly, methods 2 and 3 have to use temporary variable to store whole segment C during shifting segment A or B.
Thanks to properties of inversion operation the second disadvantage can be eliminated:
(C A')' = (A')' C' = A C'
Therefore we can replace method 2 by:
case move_method
...
of 2: # not changing segment B
# C A B ==> ==> C A' B ==> A C' B
# reverse segment A in place:
left = p6
right = p1
for counter in 1 .. size_A div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# reverse segment (A'C) in place:
left = p4
right = p1
for counter in 1 .. (size_A+size_C) div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# update position[] array:
left = p4
for pos in 0 .. size_A+size_C:
position[tour[left]] = left
left = t_succ(left)
and method 3 by:
case move_method
...
of 3: # not changing segment A
# B C A ==> B' C A ==> C' B A
# reverse segment B in place:
left = p2
right = p3
for counter in 1 .. size_B div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# reverse segment (B'C) in place:
left = p2
right = p5
for counter in 1 .. (size_B+size_C) div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# update position[] array:
left = p2
for pos in 0 .. size_B+size_C:
position[tour[left]] = left
left = t_succ(left))
This alternative versions of speedup methods, although does not need additional memory for segment variable, could be somewhat slower than more complex versions shown first, and in fact is not very elegant.
Final version
We can use Swap_Segments()
procedure to make the implementation of this speedup both concise and clear, although probably slightly slower than the complex version shown first and still using additional variable to store a segment during swap:
case move_method
of 1: # default method, not changing segment C
Reverse_Segment(tour, p6, p1, position)
Reverse_Segment(tour, p2, p3, position)
of 2: # not changing segment B
Reverse_Segment(tour, p4, p5, position)
Swap_Segments(tour, p4, p5, p6, p1, position)
of 3: # not changing segment A
Reverse_Segment(tour, p4, p5, position)
Swap_Segments(tour, p2, p3, p4, p5, position)
else: # we use only 3 methods of performing asym. 3-opt move
discard
No comments:
Post a Comment