Friday, March 16, 2018

Non-sequential 5-opt moves – part 6 of 7

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 3

Now we look for two links to remove: (d1, d2) and (d3, d4). (We can also say that we look for two pairs of cities adjacent to each other on tour, determining these links.)

In case of 12-34-65 move type one of these pairs should be inside [c2, c3] segment. For the second we should consider two options: it can be inside [c5, c1] segment:

12-34-65AEcDBAdCeB
c1 c2 c3 c4 c6 c5 c1 c2 c3 c4 c6 c5 d1 d2 d3 d4 c1 c2 c3 c4 c6 c5 d1 d2 d4 d3

or inside [c4, c6] segment:

12-34-65ADeCBAcEdB
c1 c2 c3 c4 c6 c5 c1 c2 c3 c4 c6 c5 d1 d2 d4 d3 c1 c2 c3 c4 c6 c5 d1 d2 d3 d4

But we san simplify our task and treat [c4, c6] and [c5, c1] as one segment of consecutive cities: from c4 to c1, with additional condition that link to remove cannot be the same as (c5, c6).

c1 c2 c3 c4 c6 c5

We can use the same reasoning for 12-43-56 and 12-65-43 move types. Then we would have:

  var
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    canBreakLink: bool
...
  case tourOrder
  of TO_123465:
    if (2 * Segment_Size(cF2,cF3)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF4, cF1)
  of TO_124356:
    if (2 * Segment_Size(cF6,cF1)) <= N:    
      (cFrom, cTo) = (cF6, cF1)
    else:
      (cFrom, cTo) = (cF2, cF5)
  of TO_126543:
    if (2 * Segment_Size(cF5,cF4)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF3, cF6)
  else:
    discard
  #end_case
  
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d2 != cTo:
      canBreakLink = true
      if (d1==cF1) and (d2==cF2)  or
         (d1==cF2) and (d2==cF1):
        canBreakLink = false
      if (d1==cF3) and (d2==cF4)  or
         (d1==cF4) and (d2==cF3):
        canBreakLink = false
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        canBreakLink = false

      if canBreakLink:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2,
                            Ga: G1a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves
  ...

On the other hand we can simplify the code by taking advantage of the fact that 12-43-56 and 12-65-43 are just rotated versions of 12-34-65. Then we obtain:

proc LK_Bridge_B1(c1, c2, c3, c4, c5, c6: City_Number;
                  G0: Length_Gain;
                  tourOrder: int): bool =
  var
    improved: bool
    fwd: bool
    cF1, cF2, cF3, cF4, cF5, cF6: City_Number
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    d1_is_inside_c2_c3: bool
    d1, d2: City_Number
    Ga, G1a: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int

  improved = false  # rotate all other types of move to use only TO_123465
  fwd = (c2 == t_succ(c1))
  case tourOrder
  of TO_123465:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c1, c2, c3, c4, c5, c6)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c4, c3, c2, c1, c6, c5)
  of TO_124356:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c5, c6, c1, c2, c3, c4)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c2, c1, c6, c5, c4, c3)
  of TO_126543:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c6, c5, c4, c3, c2, c1)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c3, c4, c5, c6, c1, c2)
  else:
    discard
  #end_case

  # we want to scan shorter segment
  if (2 * Segment_Size(cF2,cF3)) <= N:
    (cFrom, cTo) = (cF2, cF3)
    d1_is_inside_c2_c3 = true
  else:
    (cFrom, cTo) = (cF4, cF1)
    d1_is_inside_c2_c3 = false
  #end_if
    
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d1 != cTo and d2 != cTo:
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        discard
      else:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
        goodSufficesList.add(goodSuffix)
      #end_if
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    #breadth = len(goodSufficesList) # NOTE!!!
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d1 = goodSuffix.c2iplus1
      d2 = goodSuffix.c2iplus2
      Ga = goodSuffix.Ga
      improved = LK_Bridge_B2(cF1, cF2, cF3, cF4, cF5, cF6,
                              d1, d2, Ga, d1_is_inside_c2_c3)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

No comments:

Post a Comment