минимальное перемещение от точки к точке с инкрементными шагами
Я впервые задаю здесь вопрос. У меня любопытная проблема с алгоритмом, в центре декартовой плоскости (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 (количество шагов) первых натуральных чисел.
Спасибо, что прочитали это, а также за ваши ответы и предложения.
Ответы
Интересный вопрос. Удивительно, что ответ зависит только от$|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$