ストレートトンネルを見つける2


直線トンネルを探す
と同じプラグインタスクがありますが、問題が発生するようになりましたもう少し想像力:

Bob has a field, which is a regular polygon with $N$ sides and
perimeter $P$. There is a tunnel, which is just under the surface,
but invisible – unless you dig. It is known that the tunnel goes
under the field (at least touches it at one point), it is straight
and infinitely long (in both directions).
Bob wants to find the tunnel. To do this he has a plow and can dig
along some lines with it. If Bob plows and crosses the tunnel he
will find it. Bob doesn’t want to plow too much so he first figured
a strategy out, which guarantees to find the tunnel by plowing at
most $L$ meters.
What can be the smallest $k = L/P$ ratio, given $N$ can be any
number from 3 to $infty$?
Bob is allowed to plow only inside of his
field. He can take the plow out of the ground and move it over the
ground without plowing.

ここで重要なのは、内側だけを耕すことができ、フィールドを選ぶことができることです。これはあなたにとって最適です(つまり、$ N
$を選択したことになります)。

極端なケースを試しました:
  $ N = infty $ – これは円で、最適なパスは周囲に沿っているので、$ k_ {min} = 1
$です。
  $ N = 3 $ – それは三角形であり、最良の場合はメジアンに沿った経路であると信じている。$ k_
{min} = 1/ sqrt {3} approx 0.5774 $。
 最善のケースはどこかにあるべきです。

ベストアンサー

これは証明するのが少し難しいようです…

I hope the attached image explains my optimisation for the first
n-sided polygon. I’ll try to explain step by step.

First, n=3 is the exception and the best route is the path along
the medians. Consider the case where n>3:

Begin with one vertex labelled (1). Trace the perimeter to the next
vertex(V). Keep tracing to the next vertex until you find a vertex
whereby (1),(V), and (V+1) forms an acute triangle. This allows you
to drop an altitude from vertex(V+1) onto the line (1)-(V). From
then on, repeat the same process for every vertex henceforth.

For the case of a square, we trace out the perimeter until the 3rd
vertex, whereby it is more “economical” to drop the altitude to the
line (1)-(3) than to trace out the next side. This shape will fully
cover any possible tunnel going through the shape.

Let’s take n=9 as another example. We can trace out four sides (or
5 vertices) until we see that the next vertex (6) would allow us to
drop the altitude to line (1)-(5). Then, we repeat for every
subsequent vertex that follows.

This is more economical than the naive solution of tracing out the
entire parameter for each shape. I don’t have a mathematically
rigorous proof that these are the minimum cases for how much we
need to plough, and hope the images can intuitively present that it
may be the optimum solution.

Ultimately, this appears to give the minimum case that
N=3 is the lowest L/P ratio. N=4 gives a L/p ratio
of roughly 0.677, and the ratio slowly increases as n increases
until we reach the limit of a circle, whereby L/P=1.enter image description here

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です