Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 2
For obtaining a code for this kind of 5-opt non-sequential moves we can modify a proc for non-sequential 4-opt moves this way:
proc LK_2NS_Move(c1, c2: City_Number;
G1a: Length_Gain): bool =
var
improved: bool
c3, c4: City_Number
c2_pred, c2_succ: City_Number
c3_pred, c3_succ: City_Number
c4_A, c4_B: City_Number
fwd: bool
G1, G2a, Ga: Length_Gain
gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tourOrder: int
tried_c3: int = 0
breadth: int
improved = false
fwd = (c2 == t_succ(c1))
c2_succ = t_succ(c2)
c2_pred = t_pred(c2)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
for c3 in neighbors(c2):
if tried_c3 >= 2*Max_Breadth_1:
break find_promising_moves
if (c3 == c2_succ) or (c3 == c2_pred):
continue
G1 = G1a - distance(c2, c3)
if G1 <= 0:
break
# if G1 > 0:
c3_succ = t_succ(c3)
c3_pred = t_pred(c3)
if fwd:
c4_A = c3_succ
c4_B = c3_pred
else:
c4_A = c3_pred
c4_B = c3_succ
for c4 in [c4_A, c4_B]:
if c4 == c1: # NOTE
continue
G2a = G1 + distance(c3, c4)
if G2a > 0:
goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
Ga: G2a)
goodSufficesList.add(goodSuffix)
tried_c3 = tried_c3 + 1
#end_loop for c4
#end_loop for c3
#end_block find_promising_moves
block evaluate_promising_moves:
if len(goodSufficesList) == 0:
break evaluate_promising_moves
SortSufficesByGain(goodSufficesList)
breadth = min(len(goodSufficesList), Max_Breadth_1)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
c3 = goodSuffix.c2iplus1
c4 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
gainFromCloseUp = Ga - distance(c4, c1)
if gainFromCloseUp > 0:
if fwd and (c4 == t_succ(c3)) or
not fwd and (c4 == t_pred(c3)):
# disconnecting 2-move (||)
if LK_Bridge_A1(c1, c2, c3, c4, gainFromCloseUp):
improved = true
break evaluate_promising_moves
else:
# connecting 2-move (X)
improved = true
Make_2opt_Move(c1, c2, c3, c4)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4])
break evaluate_promising_moves
#end_if gainFromCloseUp > 0
# improving move has not been found;
# extend current 2-move ('X' or '||') to 3-move
# (disconnecting or connecting) and keep trying
if fwd and (c4 == t_succ(c3)) or
not fwd and (c4 == t_pred(c3)):
tourOrder = TO_1234
else:
tourOrder = TO_1243
#end_if
if LK_3NS_Move(c1, c2, c3, c4, Ga, tourOrder):
improved = true
break evaluate_promising_moves
#end_block evaluate_promising_moves
result = improved
proc LK_3NS_Move(c1, c2, c3, c4: City_Number;
G2a: Length_Gain;
tourOrderPrev: int): bool =
var
improved: bool
c5, c6: City_Number
c4_pred, c4_succ: City_Number
c5_pred, c5_succ: City_Number
fwd: bool
G2, Ga: Length_Gain
G3a, gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tried_c5: int = 0
breadth: int
tourOrder: int
improved = false
fwd = (c2 == t_succ(c1))
c4_succ = t_succ(c4)
c4_pred = t_pred(c4)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
for c5 in neighbors(c4):
if tried_c5 >= 2*Max_Breadth_2:
break find_promising_moves
if (c5 == c4_succ) or (c5 == c4_pred):
continue
G2 = G2a - distance(c4, c5)
if G2 <= 0:
break
# if G2 > 0:
c5_succ = t_succ(c5)
c5_pred = t_pred(c5)
for c6 in [c5_succ, c5_pred]:
# testing available variants
case tourOrderPrev
of TO_1234:
if inOrder(c2, c5, c3, fwd):
if (c6 == c1):
continue
if inOrder(c2, c6, c5, fwd):
tourOrder = TO_126534
else:
tourOrder = TO_125634
else:
if (c6 == c2):
continue
if inOrder(c4, c5, c6, fwd):
tourOrder = TO_123456 # disconnecting
else:
tourOrder = TO_123465 # disconnecting
of TO_1243:
if inOrder(c2, c5, c4, fwd):
if inOrder(c2, c6, c5, fwd):
tourOrder = TO_126543 # disconnecting
else:
if (c5 == c1) and (c6 == c2) or
(c5 == c2) and (c6 == c1):
continue
tourOrder = TO_125643
else:
if inOrder(c3, c6, c5, fwd):
tourOrder = TO_124365
else:
if (c5 == c1) and (c6 == c2) or
(c5 == c2) and (c6 == c1):
continue
tourOrder = TO_124356 # disconnecting
else:
continue # no more possibilities
#end_case tourOrderPrev
tried_c5 = tried_c5 + 1
G3a = G2 + distance(c5, c6)
goodSuffix = Suffix(c2iplus1: c5, c2iplus2: c6,
Ga: G3a, tourOrder: tourOrder)
goodSufficesList.add(goodSuffix)
#end_loop for c6
#end_loop for c5
#end_block find_promising_moves
block evaluate_promising_moves:
if len(goodSufficesList) == 0:
# no promising moves
break evaluate_promising_moves
SortSufficesByGain(goodSufficesList)
# pass promising moves, one by one, to next level
# to check them there
breadth = min(len(goodSufficesList), Max_Breadth_2)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
c5 = goodSuffix.c2iplus1
c6 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
tourOrder = goodSuffix.tourOrder
gainFromCloseUp = Ga - distance(c6, c1)
if gainFromCloseUp > 0:
case tourOrder
of TO_125634, TO_126534, TO_125643, TO_124365:
# pure 3-opt move
improved = true
Make_3opt_Move(c1, c2, c3, c4, c5, c6, tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6])
break evaluate_promising_moves
of TO_123465, TO_124356, TO_126543:
# disconnecting into 2 parts, use 2-exchange to connect
...
if LK_Bridge_B1(...):
improved = true
break evaluate_promising_moves
else: # TO_123456
continue
#end_case
#end_block evaluate_promising_moves
result = improved
No comments:
Post a Comment