минимальное перемещение от точки к точке с инкрементными шагами

Aug 19 2020

Я впервые задаю здесь вопрос. У меня любопытная проблема с алгоритмом, в центре декартовой плоскости (0,0) мне нужно перейти в другую точку (x, y) -x, а y принадлежат числам Z, но я могу использовать только шаги по горизонтали и вертикали и этот шаг увеличивается на одну единицу, единица - это расстояние от (0,0) до (0,1), (1,0), (-1,0) или (0, -1).

Например, мне нужно перейти к точке (1,1), и шаги следующие:

  • Перейти к (1,0), шаг 1 ед.
  • Перейти к (1, -2) с шагом 2 единицы.
  • Наконец, перейдите к (1,1) с шагом 3 единицы.

И для этого примера ответ: мне нужно 3 шага с 6 единицами расстояния.

Очевидно, есть несколько способов перейти к точке из центра, но проблема требует минимума.

Есть ли формула или алгоритм, чтобы найти минимальное количество шагов и расстояние этого пути?

Что ж, если вы найдете одно из них (шаги или расстояние), другое будет легко найти, потому что расстояние - это сумма N (количество шагов) первых натуральных чисел.

Спасибо, что прочитали это, а также за ваши ответы и предложения.

Ответы

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$-ось.

Есть три случая.

  • $x \ge n$. Позволять$x'= x-n$. потом$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$неотрицательно и даже. По предположению индукции мы можем перейти к$(x',y)$ в $n-1$шаги. Достигнуть$(x,y)$ в $n$ шаги, продолжаем $n$ единиц в X-направлении.
  • $y\ge n$. Это симметрично вышеописанному случаю.
  • $0\le x\lt n$ а также $0\le y\lt n$. Есть два подслучая.
    • $x\ge 2$ а также $y\ge 2$. Позволять$x'=(n-1)-x$ а также $y'=n-y$. потом$|x'|\le n-3$ а также $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ Паритет $(n-1)(n-1)/2-(|x'|+|y'|)$ такой же как $n(n+1)/2-(|x|+|y|)$, т. е. даже. По предположению индукции мы можем перейти к$(x',y')$ в $n-2$шаги. Поменяв все шаги вспять, мы можем перейти к$(-x', -y')$ в $n-2$шаги тоже. Достигнуть$(x,y)$ в $n$ шаги, мы можем продолжить еще два шага, $n$ единиц в направлении X и $n+1$ единиц в Y-направлении.
    • Один из $x$ а также $y$ является $0$ или же $1$. Позволять$g(k)=k(k+1)/2-(|x|+|y|)$. Наименьшее неотрицательное целое число такое, что$g(k)\ge0$ является $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Поскольку оба$x$ а также $y$ находятся $\lt n$ и один из них $0$ или же $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ Когда $g(m)$ даже, $n=m$по определению. Когда$g$ нечетно, так как либо $g(m+1)=g(m)+(m+1)$ или же $g(m+2)=g(m)+(m+1)+(m+2)$ должно быть даже $m+1$ или же $m+2$ должно быть $n$. Итак, будь$g(m)$ четное или нечетное, у нас есть $$n\le m+2.$$ Комбинируя два приведенных выше неравенства, имеем $$n\le \frac{5+\sqrt{8n+1}}2,$$ что подразумевает $n\le 6$. Поскольку направления X и Y симметричны, предположим, что$y=0,1$. С$x\lt n$, $x\lt 6$. Так что достаточно проверить случаи, когда$(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$ Проверить каждый из них несложно.

$\ \checkmark$