22 - Fastest route through the forest

A problem was posted by the Danish newspaper, Ingeniøren, and it goes like this:

You are in the middle of a dense forest located at \(A\). You need to get to \(C\) in the fastest way possible, and you can only change direction once. You can walk directly via \(AB\) to the dedicated walking path \(BC\) where you can walk fast, you can take the direct path through the forest (\(AC\)) where you have to walk slower, or cross through the forest to the dedicated walking path (\(AD\) and then \(DC\)).

Information given

Distances
- \(|AB| =\) 300 m
- \(|AC| =\) 1,000 m
Velocities
- \(v_{AB} = 2\) m/s
- \(v_{AD} = 2\) m/s
- \(v_{AC} = 2\) m/s
- \(v_{BC} = 5\) m/s

Length of line segments

We parameterise with \(k = |BD|\), the distance between \(B\) and \(D\). That is, how much to walk on fast walking path before crossing into the forest.

Formulating using caracas:

AB <- as_sym('300')
AB
#> c: 300
AC <- as_sym('1000')
AC
#> c: 1000
BC <- sqrt(AC^2 - AB^2)
BC
#> c: 100⋅√91
k <- symbol('k') # |BD|
DC <- BC - k
AD <- sqrt(AB^2 + k^2)
AD
#> c:    ____________
#>      ╱  2         
#>    ╲╱  k  + 90000

So for a distance of \(|AD|\), you travel by 5 m/s, and then for a distance of \(- k + 100 \sqrt{91}\) you travel by 2 m/s. Thus it takes \(\frac{\sqrt{k^{2} + 90000}}{2}\) to travel \(AD\) and \(- \frac{k}{5} + 20 \sqrt{91}\) to travel \(DC\).

The question is: What is the fastest way to get from \(A\) to \(C\)?

First, the total duration of the route is:

l <- AD/2 + DC/5
l
#> c:          ____________         
#>            ╱  2                  
#>      k   ╲╱  k  + 90000          
#>    - ─ + ─────────────── + 20⋅√91
#>      5          2

lfun <- as_expr(l)
lfun
#> expression(-k/5 + sqrt(k^2 + 90000)/2 + 20 * sqrt(91))
ks <- seq(0, as_expr(AC), length.out = 100)
ls <- eval(lfun, list(k = ks))
plot(ks, ls, type = "l", xlab = "k", ylab = "Time A to C")

It looks like a minimum around \(k = 150\).

We find the analytical solution by first finding critical points:

dl <- der(l, k)
dl
#> c:         k           1
#>    ───────────────── - ─
#>         ____________   5
#>        ╱  2             
#>    2⋅╲╱  k  + 90000
crit_points <- solve_sys(dl, k)
crit_points
#> k = 200⋅√21
#> ───────
#>    7
best_k <- crit_points[[1]]$k
best_k
#> c: 200⋅√21
#>    ───────
#>       7

The type of the critical point is found by considering the Hessian:

eval(as_expr(der(dl, k)), list(k = as_expr(best_k)))
#> [1] 0.001283121

Thus the critical point is indeed a minimum as suggested by the plot.

The fastest route is thus obtained for \[ k = \frac{200 \sqrt{21}}{7} \approx 130.93 . \] It has a length of (in meters)

DC_best <- BC - best_k
AD_best <- sqrt(AB^2 + best_k^2)
AD_best
#> c: 500⋅√21
#>    ───────
#>       7
best_route <- AD_best + DC_best
best_route
#> c: 300⋅√21          
#>    ─────── + 100⋅√91
#>       7
as_expr(best_route)
#> [1] 1150.335

\[ \frac{300 \sqrt{21}}{7} + 100 \sqrt{91} \approx 1150.34 \] and takes (in seconds)

best_l <- subs(l, "k", best_k)
best_l
#> c: 30⋅√21 + 20⋅√91
as_expr(best_l)
#> [1] 328.2651

\[ 30 \sqrt{21} + 20 \sqrt{91} \approx 328.27 \]

The best route can be illustrated, too: