### 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