増分ステップでのポイントからポイントへの最小移動

Aug 19 2020

ここで質問するのは初めてです。アルゴリズムについて不思議な問題があります。デカルト平面（0,0）の中心で、別の点（x、y）に移動する必要があります-xとyはZ番号に属します-しかし、水平方向と垂直方向のステップしか使用できませんこのステップは1単位ずつ増加します。単位は、（0,0）から（0,1）、（1,0）、（-1,0）、または（0、-1）までの距離です。

たとえば、（1,1）ポイントに移動する必要があり、手順は次のとおりです。

（1,0）、1単位のステップに移動します。
（1、-2）に2単位ずつ進みます。
最後に、（1,1）に3単位のステップに進みます。

そしてこの例の答えは、6単位の距離で3つのステップが必要だということです。

明らかに、中心からポイントに移動する方法はいくつかありますが、問題は最小限で済みます。

この方法の最小ステップ数と距離を見つけるための式またはアルゴリズムはありますか？

さて、それらの1つ（歩数または距離）を見つけた場合、距離はN（歩数）の最初の自然数の合計であるため、もう1つは簡単に見つけることができます。

これを読んでくれてありがとう、そしてあなたの答えと提案をありがとう。

回答

1 JohnL. Aug 21 2020 at 11:54

興味深い質問です。答えがにのみ依存しているのは驚くべきことです$|x|+|y|$。たとえば、到達するには同じ数のステップが必要です$(1,1)$ または $(0,2)$。

最小ステップは最小の非負の整数です $n$ そのような $n(n+1)/2-(|x|+|y|)$ 偶数で非負です。

これが $O(1)$-上記の値を返す時間アルゴリズム。ここでleast_n、つまり、$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$、は最小の非負の整数です $n$ そのような $n(n+1)/2-(|x|+|y|)\ge0$。

def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

ステップ数を考えると $s$、移動距離は $1+2+\cdots+s=s(s+1)/2$。

上記の式とアルゴリズムの正しさは、次の特性から得られます。

命題。からの最小ステップ数$(0,0)$ に $(x,y)$ 最小の非負の整数です $n$ そのような $n(n+1)/2-(|x|+|y|)$ 非負で均一です。

証明。私たちが行くことができれば$(x,y)$ に $n$ ステップ、1との間のいくつかの数の合計 $n$ またはそれらの否定は $x$ 残りの数またはその否定の合計は、 $y$、すなわち、 $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ すべてのいくつかの選択のために $\pm$の。つまり、$$1+2+\cdots+ n - (|x| + |y|)$$ 非負で均一です。

今それを証明するのに十分です $(x,y)$ で到達可能です $n$ 次の場合の手順 $n(n+1)/2-(|x|+|y|)$非負で均一です。誘導によってそれを証明しましょう$n$。

ベースケース、 $n=0$ または $1$ 手段 $(x,y)=(0,0), (0,1), (1,0)$。これらのケースはすぐに確認できます。

誘導仮説として、それがより小さなものに対して正しいと仮定します $n$の。ここで、$n\ge2$ と $n(n+1)/2-(|x|+|y|)$非負でさえ。私たちは仮定することができます$x$ そして $y$非負です。それ以外の場合、たとえば、$x$ 負の値です、変更できます $x$ その絶対値に平行であるすべてのステップの方向を逆にします $X$-軸。