Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 4
The last part is looking for such pair (d3, d4)
that constructed move improves the tour:
proc LK_Bridge_B2(c1, c2, c3, c4, c5, c6, d1, d2: City_Number;
G1a: Length_Gain,
d1_is_inside_c2_c3: bool): bool =
var
improved: bool
d3, d4: City_Number
d2_pred, d2_succ: City_Number
d3_pred, d3_succ: City_Number
G1, G2a, gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tourOrder: int
tried_c3: int = 0
breadth: int
improved = false
d2_succ = t_succ(d2)
d2_pred = t_pred(d2)
block find_promising_moves:
# find d3 as a candidate for end of link (d2,d3) to add
goodSufficesList = @[] # empty list
for d3 in neighbors(d2):
if tried_c3 >= 2*Max_Breadth_1:
break find_promising_moves
if (d3 == d2_succ) or (d3 == d2_pred):
continue
if inOrder(c2, d3, c3, true) == d1_is_inside_c2_c3:
continue
G1 = G1a - distance(d2, d3)
# choose d4 as one of the two tour neighbors of d3:
d3_succ = t_succ(d3)
d3_pred = t_pred(d3)
for d4 in [d3_succ, d3_pred]:
if d4 == d2:
continue
if (d3 == c1) and (d4 == c2) or
(d3 == c2) and (d4 == c1):
continue
if (d3 == c3) and (d4 == c4) or
(d3 == c4) and (d4 == c3):
continue
if (d3 == c5) and (d4 == c6) or
(d3 == c6) and (d4 == c5):
continue
G2a = G1 + distance(d3, d4)
if inOrder(c4, d1, c6, true) or
inOrder(c4, d3, c6, true):
if inOrder(d1, d3, d4, true):
tourOrder = TO_AExcDB # AEcDB
else:
tourOrder = TO_AdCxeB # AdCeB
else:
# inOrder(c5, d1, c1, true) or
# inOrder(c5, d3, c1, true)
if inOrder(d1, d3, d4, true):
tourOrder = TO_ADxeCB # ADeCB
else:
tourOrder = TO_AxcExdB # AcEdB
goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
Ga: G2a, tourOrder: tourOrder)
goodSufficesList.add(goodSuffix)
tried_c3 = tried_c3 + 1
#end_loop for d4
#end_loop for d3
#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]
d3 = goodSuffix.c2iplus1
d4 = goodSuffix.c2iplus2
G2a = goodSuffix.Ga
tourOrder = goodSuffix.tourOrder
gainFromCloseUp = G2a - distance(d4, d1)
if gainFromCloseUp > 0: # improving move found
improved = true
Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
d1, d2, d3, d4,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6,
d1, d2, d3, d4])
break evaluate_promising_moves
#end_block evaluate_promising_moves
result = improved
Finally we need a proc for actually making the move we have found:
proc Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
d1, d2, d3, d4: City_Number;
tourOrder: int) =
case tourOrder
of TO_AExcDB, TO_AxcExdB:
Exchange_Links(c1, c2, c5, c6)
Exchange_Links(d1, d2, d4, d3)
Exchange_Links(c3, c4, c5, c2)
Exchange_Links(d1, d3, d2, d4)
of TO_ADxeCB, TO_AdCxeB:
Exchange_Links(c1, c2, c5, c6)
Exchange_Links(d1, d2, d3, d4)
Exchange_Links(c3, c4, c5, c2)
else:
echo "Unknown 5-opt non-sequential move: ", tourOrder
quit 1