### Extending double bridge, from `d4`

We already know how to build sequential moves, that is how to extended sequential 3-opt move to sequential 4-opt move or 4-opt move to 5-opt move. We can use the same approach to extend non-sequential 4-opt move, for example double bridge, to built some 5-opt non-sequential move.

The first option is to *extend the second submove* and can be made as follows:

- Step 0
- Start from tour after considered double bridge move.

- Step 1
- Remove last link added in the second submove of double bridge, that is: from
`d4`

to`d1`

. - Add link between
`d4`

and the some other city`d5`

.

- Remove last link added in the second submove of double bridge, that is: from
- Step 2
- Remove link between
`d5`

and its tour neighbor`d6`

. - Add link between
`d6`

and the first city of submove,`d1`

, to close the tour.

- Remove link between

double bridge (AB)EDC | d6 = t_pred(d5) | AbEDC |

Note that we should make sure we have chosen this `d6`

, tour neighbor of `d5`

, that linked with `d1`

closes the tour. For example in the above case we should not use alternative `d6`

, because it disjoins tour into two cycles:

double bridge | d6 = t_succ(d5) | disjoining move |

The first set of diagrams shows that when `d5`

is between `c2`

and `d1`

, then for `c6`

we can use tour predecessor of `c5`

. The second set of diagrams shows that when `d5`

is between `c2`

and `d1`

, then for `c6`

we should not use tour successor of `c5`

.

But what if `d5`

happens to be not in the upper-right segment, not between `c2`

and `d1`

?

`d2`

and `c3`

, or between `c4`

and `d3`

, or between `d4`

and `c1`

. Relevant diagrams for these cases are given below:
double bridge AED(BC) | d6 = t_pred(d5) | AbdeC |

double bridge AE(CD)B | d6 = t_pred(d5) | AceDB |

double bridge A(DE)CB | d6 = t_pred(d5) | AdECB |

So in this kind of extending double bridge move, for `d6`

we should always take the tour predecessor of `d5`

. It is easy to check that in each case using tour successor results in disjoining move.

Aditionally, we should check check whether `d5`

and `d6`

meet the restrictions: city `d5`

should not be the same as `d1`

, nor `d2`

, nor a tour neighbor of `d4`

(one of these neigbors is `d3`

). Link `(d5, d6)`

to remove should not be the same as link `(c1, c2)`

nor `(c3, c4)`

, already removed in the first submove.

Then discussed algorithm can be implemented as follows:

```
proc LK_Bridge_A3(c1, c2, c3, c4,
d1, d2, d3, d4: City_Number;
G2a: Length_Gain; tourOrderPrev: int): bool =
## c1..c4, d1..d4 define valid double bridge move
## G2a is partial gain from this double bridge,
## without cost of the last, closing link (d4, d1),
## that is:
## d(c1,c2) - d(c2,c3) + d(c3,c4) - d(c4,c1) +
## d(d1,d2) - d(d2,d3) + d(d3,d4)
...
if not (tourOrderPrev == TO_ADBC):
return false
d4_succ = t_succ(d4)
d4_pred = t_pred(d4)
block find_move:
for d5 in neighbors(d4):
if (d5 == d4_succ) or (d5 == d4_pred):
continue
if (d5 == d1) or (d5 == d2):
continue
G2 = G2a - distance(d4, d5)
# choose d6 as predecessor of d5:
d6 = t_pred(d5)
if (d5 == c1) and (d6 == c2) or
(d5 == c2) and (d6 == c1):
continue
if (d5 == c3) and (d6 == c4) or
(d5 == c4) and (d6 == c3):
continue
G3a = G2 + distance(d5, d6)
gainFromCloseUp = G3a - distance(d6, d1)
if gainFromCloseUp > 0: # improving move found
improved = true
Make_5opt_NS_Move(c1, c2, c3, c4,
d1, d2, d3, d4, d5, d6,
TO_AxbEDC) # NOTE this tourOrder is exemplary
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4,
d1, d2, d3, d4, d5, d6])
break find_move
#end_block find_move
result = improved
```

It may not be obvious, but all four considered move types has one more common feature: all of them can be applied using exactly the same procedure: first we apply initial double bridge move, and then we apply simple 2-opt move, the very same in each case. This 2-opt (segment reversing) is equivalent to link exchange: links `(d4, d1)`

and `(d5, d6)`

are exchanged for `(d4, d5)`

and `(d6, d1)`

.

```
proc Make_5opt_NS_Move(c1, c2, c3, c4,
d1, d2, d3, d4, d5, d6: City_Number;
tourOrder: int) =
case tourOrder
of TO_AxbEDC_1, TO_AxbxdxeC_1,
# c12-d65-d12-c34-d34, c12-d12-d65-c34-d34,
TO_AxcxeDB, TO_AxdECB:
# c12-d12-c34-d65-d34, c12-d12-c34-d34-d65
Exchange_Links(d1, d2, d4, d3)
Exchange_Links(c1, c2, c4, c3)
Exchange_Links(d1, d3, d4, d2)
Exchange_Links(d1, d4, d6, d5)
of ...:
...
```

For example type *AbEDC* is obtained from double bridge *(AB)EDC* by reversing segment B, which in this case is the segment from `d5`

to `d1`

. Type *AbdeC* is obtained from double bridge *AED(BC)* by reversing joined segments EDB, which in the same as reversing joined segments CA, in this case also from `d5`

to `d1`

. And so on...