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-65 | AEcDB | AdCeB |
or inside [c4, c6]
segment:
12-34-65 | ADeCB | AcEdB |
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)
.
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