1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# golden section function minimiser def gs_search(f, a, b, tol=1.0e-14): R = 0.5 * (5.0 ** 0.5 - 1.0) C = 1.0 - R x1, x2 = R * a + C * b, C * a + R * b f1, f2 = f(x1), f(x2) while b - a > tol: if f1 > f2: a, x1, x2 = x1, x2, C * x1 + R * b f1, f2 = f2, f(x2) else: b, x1, x2 = x2, R * a + C * x2, x1 f1, f2 = f(x1), f1 return x1 if f1 < f2 else x2 # Since the position of the river doesn't matter, put the # starting point on its northern edge so that both routes # immediately cross it. Let the distances due south and # due east on the longest route be x. def dif(x): # the distance going due south and then due east d1 = 2 * x # the distance going diagonally after crossing the river d2 = 5 + (x ** 2 + (x - 5) ** 2) ** 0.5 # return the squared difference of (3/4) d1 and d2 return (0.75 * d1 - d2) ** 2 x = gs_search(dif, 0, 30) print('shorter distance = {:.2f} metres'.format(1.5 * x)) |

The version above finds the minimum of the squared difference between the the shortest and three quaters of the longest route. But we can instead simply look for the root (i.e. without the squaring) using a Brent method root solver.

In this example the time difference is minimal but in more complex examples the root finding method will generally be much faster.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
# Brent method root finder (based on # the description on Wikipedia). def bm_solve(fn, a, b, tol=1.0e-14, max_it=100): fa, fb = fn(a), fn(b) if fa * fb >= 0: raise ValueError if abs(fa) < abs(fb): a, b = b, a c, fc, mf = a, fa, True for i in range(max_it): # found a root within tolerance if not fb or abs(a - b) <= tol: return b if fa != fc and fb != fc: # inverse quadratic interpolation s = ( a * fb * fc / (fa - fb) / (fa - fc) + b * fa * fc / (fb - fa) / (fb - fc) + c * fa * fb / (fc - fa) / (fc - fb) ) else: # secant rule s = b - fb * (b - a) / (fb - fa) t = (3 * a + b) / 4 mf = ( not (t < s < b or b < s < t) or mf and 2 * abs(s - b) >= abs(b - c) or not mf and 2 * abs(s - b) >= abs(c - d) or mf and abs(b - c) < tol or not mf and abs(c - d) < tol ) if mf: s = (a + b) / 2 d, c, fc, fs = c, b, fb, fn(s) if fa * fs < 0: b, fb = s, fs else: a, fa = s, fs if abs(fa) < abs(fb): a, b, fa, fb = b, a, fb, fa else: raise ValueError # Since the position of the river doesn't matter, put the # starting point on its northern edge so that both routes # immediately cross it. Let the distances due south and # due east on the longest route be x. def dif(x): # the distance going due south and then due east d1 = 2 * x # the distance going diagonally after crossing the river d2 = 5 + (x ** 2 + (x - 5) ** 2) ** 0.5 # return the squared difference of (3/4) d1 and d2 return (0.75 * d1 - d2) x = bm_solve(dif, 0, 30) print('shorter distance = {:.2f} metres'.format(1.5 * x)) |

Here is a manual solution.

Since the position of the river doesn’t matter, put the starting point its northern edge so that both routes immediately cross it. Let the southerly and easterly distances on the longest route be \(x\) metres.

So the distances on the longer and shorter routes are \(2x\) and \(5+\sqrt{x^2+(x-5)^2}\) respectively. Setting the shorter route equal to three quarters of the longer one now gives:

$$\begin{array} ((3x/2-5)^2=&x^2+(x-5)^2 \\ 9x^2/4-15x+25=&2x^2-10x+25 \\ x^2/4 – 5x=&0 \\ x(x-20)=&0 \end{array}$$

This gives x as 20 metres and the shorter of the two routes as 30 metres.

]]>