recorrido mínimo de punto a punto con pasos incrementales

Aug 19 2020

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

1 JohnL. Aug 21 2020 at 11:54

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$