Monday, May 15, 2017

3-opt asymmetric move speedup

p1 p2 p3 p4 p5 p6 A B C
p1 p2 p3 p4 p5 p6

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:

A B C p6 p1 p2 p3 p4 p5
A' B' C (rev.) (rev.)
    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:

C A B p4 p5 p6 p1 p2 p3
A C' B (rev.)
    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:

B C A p2 p3 p4 p5 p6 p1
C' B A (rev.)
    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:

C A B p4 p5 p6 p1 p2 p3
C A' B (rev.)
A C' B (rev.)
    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:

B C A p2 p3 p4 p5 p6 p1
B' C A (rev.)
C' B A (rev.)
    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