There are 148 pure 5-opt move types.
Note that the code below is for sequential pure 5-opt moves and it is supposed to be used with the code for pure 4-opt, 3-opt and 2-opt moves.
proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
G4a: Length_Gain;
tourOrderPrev: int): bool =
const
level = 4
var
improved: bool
searching: bool
c9, c10: City_Number
c8_pred, c8_succ: City_Number
c9_pred, c9_succ: City_Number
fwd: bool
G4, G5a, gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tried_c9: int = 0
breadth: int
tourOrder: int
moveType: int
c2subseq, cLast: City_Number
Ga: Length_Gain
SubseqLvl: int
improved = false
fwd = (c2 == t_succ(c1))
c8_succ = t_succ(c8)
c8_pred = t_pred(c8)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
for c9 in neighbors(c8):
if tried_c9 >= 2*Max_Breadth_4:
break find_promising_moves
# tests:
# when c9 is one of tour neighbors of c8,
# then the link (c6,c7) already exists in tour
# and we cannot add it to the tour
if (c9 == c8_succ) or (c9 == c8_pred):
continue
# link (c8,c9) should not be the same as (c2,c3)
if (c8 == c2) and (c9 == c3) or
(c8 == c3) and (c9 == c2):
continue
# link (c8,c9) should not be the same as (c4,c5)
if (c8 == c4) and (c9 == c5) or
(c8 == c5) and (c9 == c4):
continue
# if c9 is c1, then link (c10,c1) needed to close the tour
# would be the same as (c10,c9) already in in tour
if (c9 == c1):
continue
G4 = G4a - distance(c8, c9)
if G4 < 0: # c9 is too far from c8
break # all subsequent candidates for c9 are even worse
# if G4 > 0:
c9_succ = t_succ(c9)
c9_pred = t_pred(c9)
for c10 in [c9_succ, c9_pred]:
# tests:
# c10 should not be c1, when we close a tour.
# We check condition here, because we are not going to
# go deeper and pass possibly disconnecting move
# to *general* 6-opt proc
# (compare place of similar test in 4opt proc)
if (c10 == c1):
continue
# link (c9,c10) should not be the same as (c3,c4)
if (c9 == c3) and (c10 == c4) or
(c9 == c4) and (c10 == c3):
continue
# link (c9,c10) should not be the same as (c5,c6)
if (c9 == c5) and (c10 == c6) or
(c9 == c6) and (c10 == c5):
continue
tourOrder = TO_00 # do not remove this line!
case tourOrderPrev
of TO_12347856:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A347856
else:
tourOrder = TO_12A9347856
of TO_12348756:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A348756
else:
tourOrder = TO_12A9348756
of TO_12783456:
if inOrder(c4, c9, c5, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1278349A56
else:
tourOrder = TO_127834A956
of TO_12873456:
if inOrder(c4, c9, c5, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1287349A56
else:
tourOrder = TO_128734A956
of TO_12346587:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A346587
else:
tourOrder = TO_12A9346587
of TO_12347865:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A347865
else:
tourOrder = TO_12A9347865
of TO_12783465:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12783465A9
elif inOrder(c4, c9, c6, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1278349A65
elif inOrder(c8, c9, c3, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A93465
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9783465
of TO_12873465:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12873465A9
elif inOrder(c4, c9, c6, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1287349A65
elif inOrder(c7, c9, c3, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A3465
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A873465
of TO_12563478:
if inOrder(c4, c9, c7, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1256349A78
else:
tourOrder = TO_125634A978
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A3478
else:
tourOrder = TO_1256A93478
elif inOrder(c2, c9, c5, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A563478
else:
tourOrder = TO_12A9563478
of TO_12563487:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12563487A9
elif inOrder(c4, c9, c8, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1256349A87
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A3487
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A563487
of TO_12785634:
if inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1278569A34
else:
tourOrder = TO_127856A934
elif inOrder(c2, c9, c7, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A785634
else:
tourOrder = TO_12A9785634
of TO_12875634:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12875634A9
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1287569A34
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_1287A95634
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A875634
of TO_12567834:
if inOrder(c6, c9, c7, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A7834
else:
tourOrder = TO_1256A97834
of TO_12568734:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12568734A9
elif inOrder(c7, c9, c3, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_125687A934
elif inOrder(c6, c9, c8, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A8734
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9568734
of TO_12653478:
if inOrder(c4, c9, c7, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1265349A78
else:
tourOrder = TO_126534A978
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A3478
else:
tourOrder = TO_1265A93478
elif inOrder(c2, c9, c6, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A653478
else:
tourOrder = TO_12A9653478
of TO_12653487:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12653487A9
elif inOrder(c4, c9, c8, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1265349A87
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_1265A93487
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9653487
of TO_12657834:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12657834A9
elif inOrder(c8, c9, c3, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_126578A934
elif inOrder(c5, c9, c7, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A7834
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9657834
of TO_12658734:
if inOrder(c7, c9, c3, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1265879A34
else:
tourOrder = TO_126587A934
elif inOrder(c2, c9, c6, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A658734
else:
tourOrder = TO_12A9658734
of TO_12786534:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12786534A9
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1278659A34
elif inOrder(c8, c9, c6, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A96534
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A786534
of TO_12876534:
if inOrder(c7, c9, c6, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A6534
else:
tourOrder = TO_1287A96534
of TO_12435687:
if inOrder(c3, c9, c5, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A5687
else:
tourOrder = TO_1243A95687
elif inOrder(c2, c9, c4, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A435687
else:
tourOrder = TO_12A9435687
of TO_12437856:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12437856A9
elif inOrder(c8, c9, c5, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_124378A956
elif inOrder(c3, c9, c7, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_1243A97856
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A437856
of TO_12438756:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12438756A9
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1243879A56
elif inOrder(c3, c9, c8, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A8756
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9438756
of TO_12784356:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12784356A9
elif inOrder(c3, c9, c5, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1278439A56
elif inOrder(c8, c9, c4, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A94356
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9784356
of TO_12874356:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12874356A9
elif inOrder(c3, c9, c5, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_128743A956
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A4356
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A874356
of TO_12436578:
if inOrder(c5, c9, c7, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1243659A78
else:
tourOrder = TO_124365A978
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A6578
else:
tourOrder = TO_1243A96578
elif inOrder(c2, c9, c4, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A436578
else:
tourOrder = TO_12A9436578
of TO_12436587:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12436587A9
elif inOrder(c5, c9, c8, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1243659A87
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_1243A96587
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A436587
of TO_12437865:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12437865A9
elif inOrder(c8, c9, c6, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_124378A965
elif inOrder(c3, c9, c7, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A7865
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9437865
of TO_12438765:
if inOrder(c7, c9, c6, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1243879A65
else:
tourOrder = TO_124387A965
of TO_12784365:
if inOrder(c3, c9, c6, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1278439A65
else:
tourOrder = TO_127843A965
elif inOrder(c2, c9, c7, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A784365
else:
tourOrder = TO_12A9784365
of TO_12874365:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12874365A9
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_128743A965
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_1287A94365
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A874365
of TO_12564378:
if inOrder(c3, c9, c7, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1256439A78
else:
tourOrder = TO_125643A978
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A4378
else:
tourOrder = TO_1256A94378
elif inOrder(c2, c9, c5, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A564378
else:
tourOrder = TO_12A9564378
of TO_12564387:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12564387A9
elif inOrder(c3, c9, c8, fwd):
s if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1256439A87
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A4387
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9564387
of TO_12567843:
if inOrder(c6, c9, c7, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A7843
else:
tourOrder = TO_1256A97843
of TO_12568743:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12568743A9
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_125687A943
elif inOrder(c6, c9, c8, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A8743
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A568743
of TO_12785643:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12785643A9
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1278569A43
elif inOrder(c8, c9, c5, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A95643
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A785643
of TO_12875643:
if inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1287569A43
else:
tourOrder = TO_128756A943
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A5643
else:
tourOrder = TO_1287A95643
of TO_12654387:
if inOrder(c5, c9, c4, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A4387
else:
tourOrder = TO_1265A94387
of TO_12657843:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12657843A9
elif inOrder(c8, c9, c4, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_126578A943
elif inOrder(c5, c9, c7, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_1265A97843
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A657843
of TO_12658743:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12658743A9
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1265879A43
elif inOrder(c5, c9, c8, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A8743
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A658743
of TO_12786543:
if inOrder(c5, c9, c4, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1278659A43
else:
tourOrder = TO_127865A943
else: # of tourOrderPrev
continue
#end of testing variants
if tourOrder == TO_00:
moveType = move_type_0
else:
moveType = move_type_5
if moveType != move_type_0: # 6-opt not implemented
tried_c9 = tried_c9 + 1
G5a = G4 + distance(c9, c10)
goodSuffix = Suffix(c2iplus1: c9, c2iplus2: c10,
Ga: G5a,
tourOrder: tourOrder, moveType: moveType)
goodSufficesList.add(goodSuffix)
#end_loop for c10
#end_loop for neighbor_number
#end_block find_promising_moves
block evaluate_promising_moves:
if len(goodSufficesList) == 0:
# no promising moves
break evaluate_promising_moves
Save_Tour()
Save_DLB()
SortSufficesByGain(goodSufficesList)
# pass promising moves, one by one, to next level
# to check them there
breadth = min(len(goodSufficesList), Max_breadth_4)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
c9 = goodSuffix.c2iplus1
c10 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
tourOrder = goodSuffix.tourOrder
moveType = goodSuffix.moveType
if moveType != move_type_0: # connecting move
gainFromCloseUp = Ga - distance(c10, c1)
if gainFromCloseUp > 0:
improved = true
Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook,
[c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
break evaluate_promising_moves
when true: # not OPT_6_IMPLEMENTED:
# below we try to use general subsequent move
# after temporary applying 5-opt move
c2subseq = c10
cLast = c10
LinksAddedClear()
AddtoLinksAdded(c2, c3)
AddtoLinksAdded(c4, c5)
AddtoLinksAdded(c6, c7)
AddtoLinksAdded(c8, c9)
Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
tourOrder)
Set_DLB_off(DontLook,
[c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
searching = true
SubseqLvl = 0
while searching:
SubseqLvl = SubseqLvl + 1
improved = LK_SubsequentMove(c1, c2subseq, Ga, cLast)
if improved:
break evaluate_promising_moves
else: # not improved
if c2subseq == cLast: # end of promising moves
Restore_Tour()
Restore_DLB()
searching = false
else:
c2subseq = cLast
if SubseqLvl > Max_Depth:
Restore_Tour()
Restore_DLB()
searching = false
#end_loop for mve
#end_block evaluate_promising_moves
result = improved
No comments:
Post a Comment