Project Eulerに挑戦してみよう

Project Euler 607 / Marsh Crossing

Frodo and Sam need to travel 100 leagues due East from point A to point B. On normal terrain, they can cover 10 leagues per day, and so the journey would take 10 days. However, their path is crossed by a long marsh which runs exactly South-West to North-East, and walking through the marsh will slow them down. The marsh is 50 leagues wide at all points, and the mid-point of AB is located in the middle of the marsh. A map of the region is shown in the diagram below:


The marsh consists of 5 distinct regions, each 10 leagues across, as shown by the shading in the map. The strip closest to point A is relatively light marsh, and can be crossed at a speed of 9 leagues per day. However, each strip becomes progressively harder to navigate, the speeds going down to 8, 7, 6 and finally 5 leagues per day for the final region of marsh, before it ends and the terrain becomes easier again, with the speed going back to 10 leagues per day.

If Frodo and Sam were to head directly East for point B, they would travel exactly 100 leagues, and the journey would take approximately 13.4738 days. However, this time can be shortened if they deviate from the direct path.

Find the shortest possible time required to travel from point A to B, and give your answer in days, rounded to 10 decimal places.

Problem 607 - Project Euler

Marsh = 沼地,湿地だそうです。

「n*sin θ = (一定)」にしたがって曲がる経路が最短だろうと見当をつけましたが,スタートとゴールが決まっているので,この方法では解けません。

P1(-50/√2, -50/√2), P2(x1, -25), P3(x2, -15), P4(x3, -5),
P5(x4, 5), P6(x5, 15), P7(x6, 25), P8(50/√2, 50/√2)
v={10, 9, 8, 7, 6, 5, 10}
 f=\displaystyle \sum_{i=1}^7 \dfrac{P_i P_{i+1}}{v_i}

NMinimize で f の最小値を数値的に求めます*1

NMinimize ははじめて使ったのですが,変数の範囲を何も制約しないと0.05秒で,
-50/√2 < x1 < x2 < x3 < x4 < x5 < x6 < 50/√2
の制約をつけるとかえって遅くなって 0.2秒になるのが意外でした。