← All solutions

This problem can be solved with dynamic programming. First, instead of thinking of one tour that goes west and then back east, let us think of it as two separate paths going from west to east at the same time (with every island being visited by exactly one of the two paths). This is of course equivalent but the change of viewpoint makes things a lot easier.

We now let L(i, j) denote the minimum length of two paths starting at islands i and j respectively, together covering all the islands from max(i, j) + 1 to n − 1 and both ending at n − 1. Letting k = max(i, j) + 1 and ignoring the two special islands b1 and b2, a recursion for L is the following:

L(i, j) = min (d(i, k) + L(k, j),  d(j, k) + L(i, k))   if k < n
          d(i, n − 1) + d(j, n − 1)                      if k = n

where d(i, k) denotes the distance between islands i and k. The second line is the base case of the recursion, and the two different options in the first line correspond to the choice of which of the two tours should pass island k. With the addition of the two special islands, the only difference is that when k = b1 the value d(j, k) + L(i, k) is not an option since only the first tour can pass island k, and similarly when k = b2 the value d(i, k) + L(k, j) is not an option.

To reconstruct the optimal solution, the standard method of backtracking can be used.