Contrary to original Lin-Kernighan, considering only two types of sequential 4-opt moves, the code below deals with all twenty types of sequential 4-opt moves (there are only five types non-sequential 4-opt moves) and disjoining sequences leading to valid 5-opt moves.
proc LK_4Move(c1, c2, c3, c4, c5, c6: City_Number;
G3a: Length_Gain;
tourOrderPrev: int): bool =
const
level = 3
var
improved: bool
c7, c8: City_Number
c6_pred, c6_succ: City_Number
c7_pred, c7_succ: City_Number
fwd: bool
G3: Length_Gain
G4a, gainFromCloseUp: Length_Gain
tried_c7: int = 0
tourOrder: int
moveType: int
improved = false
fwd = (c2 == t_succ(c1))
c6_succ = t_succ(c6)
c6_pred = t_pred(c6)
best_Ga = low(Length_Gain)
block find_promising_moves:
for c7 in neighbors(c6):
# tests:
# when c7 is one of tour neighbors of c6,
# then the link (c6,c7) already exists in tour
# and we cannot add it to the tour
if (c7 == c6_succ) or (c7 == c6_pred):
continue
# link (c6,c7) should not be the same as (c2,c3)
if (c6 == c2) and (c7 == c3) or
(c6 == c3) and (c7 == c2):
continue
G3 = G3a - distance(c6, c7)
if G3 <= 0: # c7 is too far from c6
break # all subsequent candidates for c7 are even worse
# if G3 > 0:
tried_c7 = tried_c7 + 1
if tried_c7 > Max_Breadth_3:
break find_promising_moves
c7_succ = t_succ(c7)
c7_pred = t_pred(c7)
for c8 in [c7_succ, c7_pred]:
# tests:
# link (c7,c8) should not be the same as (c1,c2)
if (c7 == c1) and (c8 == c2) or
(c7 == c2) and (c8 == c1):
continue
# link (c7,c8) should not be the same as (c3,c4)
if (c7 == c3) and (c8 == c4) or
(c7 == c4) and (c8 == c3):
continue
# testing available variants:
case tourOrderPrev
of TO_126534:
if inOrder(c4, c7, c1, fwd):
if inOrder(c4, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12653478 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12653487
elif inOrder(c5, c7, c3, fwd):
if inOrder(c5, c7, c8, fwd):
tourOrder = TO_12657834
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12658734 # disconnecting, starts 5-opt
else:
continue
else: # inOrder(c2, c7, c6, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12786534
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12876534 # disconnecting, starts 5-opt
else:
continue
of TO_125634:
if inOrder(c4, c7, c1, fwd):
if inOrder(c4, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12563478 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12563487
elif inOrder(c6, c7, c3, fwd):
if inOrder(c6, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12567834 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12568734
else: # inOrder(c2, c7, c5, fwd):
if inOrder(c2, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12785634 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12875634
of TO_123456:
when OPT_5_IMPLEMENTED:
if inOrder(c6, c7, c1, fwd):
# TO_12345678 and TO_12345687 are not valid 4-opt moves
# and they do not lead to valid 5-opt moves
continue
elif inOrder(c4, c7, c5, fwd):
if inOrder(c4, c7, c8, fwd):
tourOrder = TO_12347856 # disconnecting, starts 5-opt
else:
tourOrder = TO_12348756 # disconnecting, starts 5-opt
else: # inOrder(c2, c7, c3, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12783456 # disconnecting, starts 5-opt
else:
tourOrder = TO_12873456 # disconnecting, starts 5-opt
else:
continue
of TO_125643:
if inOrder(c3, c7, c1, fwd):
if inOrder(c3, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12564378 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12564387
elif inOrder(c6, c7, c4, fwd):
if inOrder(c6, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12567843 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12568743
else: # inOrder(c2, c7, c5, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12785643
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12875643 # disconnecting, starts 5-opt
else:
continue
of TO_124365:
if inOrder(c5, c7, c1, fwd):
if inOrder(c5, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12436578 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12436587
elif inOrder(c3, c7, c6, fwd):
if inOrder(c3, c7, c8, fwd):
tourOrder = TO_12437865
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12438765 # disconnecting, starts 5-opt
else:
continue
else: # inOrder(c2, c7, c4, fwd):
if inOrder(c2, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12784365 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12874365
of TO_123465:
if inOrder(c5, c7, c1, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c5, c7, c8, fwd):
# TO_12346578 is not valid 4-opt move
# and it does not lead to valid 5-opt move
continue
else:
tourOrder = TO_12346587 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c4, c7, c6, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c4, c7, c8, fwd):
tourOrder = TO_12347865 # disconnecting, starts 5-opt
else:
tourOrder = TO_12348765 # disconnecting, starts 5-opt
else:
continue
else: # inOrder(c2, c7, c3, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12783465
else:
tourOrder = TO_12873465
of TO_126543:
if inOrder(c3, c7, c1, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c3, c7, c8, fwd):
continue
else:
tourOrder = TO_12654387 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c5, c7, c4, fwd):
if inOrder(c5, c7, c8, fwd):
tourOrder = TO_12657843
else:
tourOrder = TO_12658743
else: # inOrder(c2, c7, c6, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12786543 # disconnecting, starts 5-opt
else:
tourOrder = TO_12876543 # disconnecting, starts 5-opt
else:
continue
of TO_124356:
if inOrder(c6, c7, c1, fwd):
if inOrder(c6, c7, c8, fwd):
# TO_12435678 is not valid 4-opt move
# and it does not lead to valid 5-opt move
continue
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12435687 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c3, c7, c5, fwd):
if inOrder(c3, c7, c8, fwd):
tourOrder = TO_12437856
else:
tourOrder = TO_12438756
else: # inOrder(c2, c7, c4, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12784356
else:
tourOrder = TO_12874356
else: # of tourOrderPrev
continue
#end of testing variants
if (c8 == c1):
# c8 should not be c1 when we close the tour
moveType = move_type_0
else:
case tourOrder
of TO_12786534, TO_12657834, TO_12653487, TO_12875634,
TO_12568734, TO_12563487, TO_12785643, TO_12568743,
TO_12564387, TO_12874365, TO_12437865, TO_12436587,
TO_12783465, TO_12873465, TO_12658743, TO_12657843,
TO_12874356, TO_12784356, TO_12437856, TO_12438756:
moveType = move_type_4
else:
moveType = move_type_0
G4a = G3 + distance(c7, c8)
if moveType != move_type_0:
gainFromCloseUp = G4a - distance(c8, c1)
if gainFromCloseUp > 0:
# improving move found
improved = true
Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6, c7, c8])
break find_promising_moves
when not OPT_5_IMPLEMENTED::
# here we should try to use general subsequent move
# after temporary applying 4-opt move
discard
when OPT_5_IMPLEMENTED:
if LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8,
Ga, tourOrder):
improved = true
break find_promising_moves
#end_loop for c8
#end_loop for neighbor_number
#end_block find_promising_moves
result = improved
No comments:
Post a Comment