recorrido mínimo de punto a punto con pasos incrementales
Es la primera vez que hago una pregunta aquí. Tengo un problema curioso sobre el algoritmo, en el centro del plano cartesiano (0,0) necesito ir a otro punto (x,y) -x e y pertenecen a los números Z - pero solo puedo usar pasos horizontales y verticales y estos pasos aumentan de una en una unidades, una unidad es una distancia de (0,0) a (0,1), (1,0), (-1,0) o (0,-1).
Por ejemplo, necesito ir al punto (1,1) y los pasos son:
- Ir a (1,0), un paso de 1 unidad.
- Ir a (1,-2) un paso de 2 unidades.
- Finalmente, vaya a (1,1) un paso de 3 unidades.
Y para este ejemplo la respuesta es necesito 3 pasos con 6 unidades de distancia.
Obviamente, hay varias formas de ir a un punto desde el centro, pero el problema necesita el mínimo.
¿Existe una fórmula o un algoritmo para encontrar el número mínimo de pasos y la distancia de este camino?
Bueno, si encuentras uno de ellos (pasos o distancia), el otro es fácil de encontrar porque la distancia es una suma de N (conteo de pasos) primeros números naturales.
Gracias por leer esto y por sus respuestas y sugerencias.
Respuestas
Interesante pregunta. Es sorprendente que la respuesta dependa sólo de$|x|+|y|$. Por ejemplo, se necesita el mismo número de pasos para alcanzar$(1,1)$o$(0,2)$.
El paso mínimo es el menor entero no negativo$n$tal que$n(n+1)/2-(|x|+|y|)$es par y no negativo.
Aquí hay un$O(1)$-algoritmo de tiempo que devuelve el valor descrito anteriormente, donde least_n
, es decir,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, es el menor entero no negativo$n$tal que$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
Dado el número de pasos$s$, la distancia recorrida es$1+2+\cdots+s=s(s+1)/2$.
La corrección de la fórmula y el algoritmo anterior proviene de la siguiente caracterización.
Proposición. El conteo mínimo de pasos desde$(0,0)$a$(x,y)$es el menor entero no negativo$n$tal que$n(n+1)/2-(|x|+|y|)$es no negativo y par.
prueba _ si podemos ir a$(x,y)$en$n$pasos, la suma de algunos números entre 1 y$n$o sus negaciones deben ser$x$y la suma de los números restantes o sus negaciones debe ser$y$, es decir,$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$para alguna elección de todos$\pm$'s. Eso significa,$$1+2+\cdots+ n - (|x| + |y|)$$es no negativo y par.
Ahora basta probar que$(x,y)$es accesible en$n$pasos si$n(n+1)/2-(|x|+|y|)$es no negativo y par. Probémoslo por inducción sobre$n$.
Los casos base,$n=0$o$1$medio$(x,y)=(0,0), (0,1), (1,0)$. Estos casos son inmediatos de verificar.
Supongamos, como hipótesis de inducción, que es correcta para valores más pequeños$n$'s. Ahora considere el caso de$n\ge2$con$n(n+1)/2-(|x|+|y|)$no negativo e incluso. podemos asumir$x$y$y$son no negativos; de lo contrario, por ejemplo, si$x$es negativo, podemos cambiar$x$a su valor absoluto e invertir la dirección de todos los pasos que son paralelos a$X$-eje.
Hay tres casos.
- $x \ge n$. Dejar$x'= x-n$. Después$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$es no negativo y par. Por hipótesis de inducción, podemos ir a$(x',y)$en$n-1$pasos. Alcanzar$(x,y)$en$n$pasos, seguimos$n$unidades en la dirección X.
- $y\ge n$. Esto es simétrico al caso anterior.
- $0\le x\lt n$y$0\le y\lt n$. Hay dos subcasos.
- $x\ge 2$y$y\ge 2$. Dejar$x'=(n-1)-x$y$y'=n-y$. Después$|x'|\le n-3$y$|y'|\le n-2$.$$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$la paridad de$(n-1)(n-1)/2-(|x'|+|y'|)$es lo mismo que$n(n+1)/2-(|x|+|y|)$, es decir, incluso. Por hipótesis de inducción, podemos ir a$(x',y')$en$n-2$pasos . Invirtiendo todos los pasos, podemos ir a$(-x', -y')$en$n-2$pasos también. Alcanzar$(x,y)$en$n$pasos, podemos continuar con dos pasos más,$n$unidades en la dirección X y$n+1$unidades en la dirección Y.
- Uno de$x$y$y$es$0$o$1$. Dejar$g(k)=k(k+1)/2-(|x|+|y|)$. El entero no negativo más pequeño tal que$g(k)\ge0$es$m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Ya que ambos$x$y$y$son$\lt n$y uno de ellos es$0$o$1$,$$m\le \frac{1+\sqrt{8n+1}}2.$$Cuando$g(m)$incluso,$n=m$por definición. Cuando$g$es extraño, ya que cualquiera$g(m+1)=g(m)+(m+1)$o$g(m+2)=g(m)+(m+1)+(m+2)$debe ser incluso, ya sea$m+1$o$m+2$debe ser$n$. Entonces, si$g(m)$es par o impar, tenemos$$n\le m+2.$$Combinando las dos desigualdades anteriores, tenemos$$n\le \frac{5+\sqrt{8n+1}}2,$$lo que implica$n\le 6$. Dado que la dirección X y la dirección Y son simétricas, supongamos$y=0,1$. Ya que$x\lt n$,$x\lt 6$. Por lo tanto, basta verificar los casos en que$(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)\}.$Es fácil verificar cada uno de ellos.
$\ \checkmark$