### Double Bridge as an improving 4-opt move, part 2

In previous part we have found such `cF1`

...`cF4`

that replacing links `cF1-cF2`

and `cF3-cF4`

with links `cF2-cF3`

and `cF4-cF1`

disjoins tour, but gives gain:

We can expect that segment from `cF2`

to `cF3`

contains relatively small number of cities. Therefore we will look for `d1`

by examining one by one all cities between `cF2`

and `cF3`

, and then look for `d3`

among these *neighbors* of given `d1`

that are in the other segment, that is between `cF4`

and `cF1`

. If total gain from set of all eight cities obtained this way is positive, then we have found improving non-sequential move.

But what if segment from `cF2`

to `cF3`

contains more cities than the other one?

Then we can simply "rename" cities before using the procedure described above:

So we use:

```
if (2 * Segment_Size(cF2,cF3)) > N:
(cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)
```

where:

```
proc Segment_Size(cityStart, cityEnd: City_Number): int =
## Returns number of cities in segment given by the two cities.
## Note that order of parameters is important to distinguish
## between two possible segments
result = (N + position[cityEnd] + 1 - position[cityStart]) mod N
```

Rest of the code implements the idea described above:

```
proc LK_Bridge_A1(c1, c2, c3, c4: City_Number;
G0: Length_Gain): bool =
var
improved: bool
cF1, cF2, cF3, cF4: City_Number
d1, d2: City_Number
Ga, G1a: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
breadth: int
improved = false
# order cities 'forward':
if (c2 == t_succ(c1)):
(cF1, cF2, cF3, cF4) = (c1, c2, c3, c4)
else:
(cF1, cF2, cF3, cF4) = (c2, c1, c4, c3)
#end_if
# we want segment [cF2,cF3] to be the shorter one
if (2 * Segment_Size(cF2,cF3)) > N:
(cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
d1 = cF2
d2 = t_succ(d1)
while d2 != cF3:
G1a = G0 + distance(d1, d2)
goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
goodSufficesList.add(goodSuffix)
d1 = d2
d2 = t_succ(d1)
#end_loop while d2 != cF3
#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]
d1 = goodSuffix.c2iplus1
d2 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
if improved:
break evaluate_promising_moves
#end_block evaluate_promising_moves
result = improved
```

and:

```
proc LK_Bridge_A2(c1, c2, c3, c4, d1, d2: City_Number;
G1a: Length_Gain): 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
# find d3 as a candidate for end of link (d2,d3) to add
d2_succ = t_succ(d2)
d2_pred = t_pred(d2)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
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):
# d3 should not be between c2 and 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
G2a = G1 + distance(d3, d4)
if (d4 == t_succ(d3)):
tourOrder = TO_ADBC # 'ADBC' (||=)
else:
tourOrder = TO_AxcxdB # 'AcdB' (||X)
#end_if
goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
tourOrder: tourOrder, Ga: G2a)
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
gainFromCloseUp = G2a - distance(d4, d1)
if gainFromCloseUp > 0: # improving move found
improved = true
Make_4opt_NS_Move(c1, c2, c3, c4,
d1, d2, d3, d4, tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4,
d1, d2, d3, d4])
break evaluate_promising_moves
#end_block evaluate_promising_moves
result = improved
```