déplacement minimum d'un point à un autre avec des étapes incrémentielles

Aug 19 2020

C'est la première fois que je pose une question ici. J'ai un curieux problème d'algorithme, au centre du plan cartésien (0,0) je dois aller à un autre point (x,y) -x et y appartiennent à des nombres Z - mais je ne peux utiliser que des étapes horizontales et verticales et ce pas augmente d'une unité, une unité est une distance de (0,0) à (0,1), (1,0), (-1,0) ou (0,-1).

Par exemple, je dois aller au point (1,1) et les étapes sont :

  • Aller à (1,0), un pas de 1 unité.
  • Passez en (1,-2) un pas de 2 unités.
  • Enfin, passez en (1,1) un pas de 3 unités.

Et pour cet exemple, la réponse est j'ai besoin de 3 étapes avec 6 unités de distance.

Évidemment, il y a plusieurs façons d'aller à un point du centre mais le problème a besoin du minimum.

Existe-t-il une formule ou un algorithme pour trouver le nombre minimum de pas et la distance de ce chemin ?

Eh bien, si vous trouvez l'un d'entre eux (pas ou distance), l'autre est facile à trouver car la distance est une somme de N (nombre de pas) premiers nombres naturels.

Merci d'avoir lu ceci et pour vos réponses et suggestions.

Réponses

1 JohnL. Aug 21 2020 at 11:54

Question interessante. Il est surprenant que la réponse ne dépende que de$|x|+|y|$. Par exemple, le même nombre d'étapes est nécessaire pour atteindre$(1,1)$ou$(0,2)$.


Le pas minimum est le plus petit entier non négatif$n$tel que$n(n+1)/2-(|x|+|y|)$est pair et non négatif.

Voici un$O(1)$-time algorithme qui renvoie la valeur décrite ci-dessus, où least_n, c'est-à-dire,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, est le plus petit entier non négatif$n$tel 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

Vu le nombre d'étapes$s$, la distance parcourue est$1+2+\cdots+s=s(s+1)/2$.


L'exactitude de la formule et de l'algorithme ci-dessus provient de la caractérisation suivante.

Proposition. Le nombre minimum d'étapes à partir de$(0,0)$à$(x,y)$est le plus petit entier non négatif$n$tel que$n(n+1)/2-(|x|+|y|)$est non négatif et pair.

Preuve . Si nous pouvons aller à$(x,y)$dans$n$étapes, la somme de certains nombres entre 1 et$n$ou leurs négations doivent être$x$et la somme des nombres restants ou leurs négations doit être$y$, c'est à dire,$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$pour un choix de tous$\pm$'s. Cela signifie,$$1+2+\cdots+ n - (|x| + |y|)$$est non négatif et pair.

Maintenant, il suffit de prouver que$(x,y)$est accessible dans$n$étapes si$n(n+1)/2-(|x|+|y|)$est non négatif et pair. Démontrons-le par induction sur$n$.

Les cas de base,$n=0$ou$1$moyens$(x,y)=(0,0), (0,1), (1,0)$. Ces cas sont immédiats à vérifier.

Supposons, comme hypothèse d'induction, qu'elle soit correcte pour les plus petits$n$'s. Considérons maintenant le cas de$n\ge2$avec$n(n+1)/2-(|x|+|y|)$non négatif et pair. Nous pouvons supposer$x$et$y$sont non négatifs ; sinon, par exemple, si$x$est négatif, nous pouvons changer$x$à sa valeur absolue et inverser le sens de tous les pas parallèles à$X$-axe.

Il y a trois cas.

  • $x \ge n$. Laisser$x'= x-n$. Alors$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$est non négatif et pair. Par hypothèse d'induction, on peut passer à$(x',y)$dans$n-1$pas. Atteindre$(x,y)$dans$n$étapes, nous continuons$n$unités dans la direction X.
  • $y\ge n$. Ceci est symétrique au cas ci-dessus.
  • $0\le x\lt n$et$0\le y\lt n$. Il y a deux sous-cas.
    • $x\ge 2$et$y\ge 2$. Laisser$x'=(n-1)-x$et$y'=n-y$. Alors$|x'|\le n-3$et$|y'|\le n-2$.$$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$La parité de$(n-1)(n-1)/2-(|x'|+|y'|)$est le même que$n(n+1)/2-(|x|+|y|)$, c'est-à-dire pair. Par hypothèse d'induction, on peut passer à$(x',y')$dans$n-2$pas . En inversant toutes les étapes, on peut passer à$(-x', -y')$dans$n-2$étapes également. Atteindre$(x,y)$dans$n$étapes, nous pouvons continuer avec deux autres étapes,$n$unités dans la direction X et$n+1$unités dans la direction Y.
    • Un des$x$et$y$est$0$ou$1$. Laisser$g(k)=k(k+1)/2-(|x|+|y|)$. Le plus petit entier non négatif tel que$g(k)\ge0$est$m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Puisque les deux$x$et$y$sommes$\lt n$et l'un d'eux est$0$ou$1$,$$m\le \frac{1+\sqrt{8n+1}}2.$$Lorsque$g(m)$est même,$n=m$par définition. Lorsque$g$est étrange, puisque soit$g(m+1)=g(m)+(m+1)$ou$g(m+2)=g(m)+(m+1)+(m+2)$doit être pair, soit$m+1$ou$m+2$doit être$n$. Alors, que ce soit$g(m)$est pair ou impair, on a$$n\le m+2.$$En combinant les deux inégalités ci-dessus, on a$$n\le \frac{5+\sqrt{8n+1}}2,$$ce qui implique$n\le 6$. Puisque la direction X et la direction Y sont symétriques, supposons$y=0,1$. Depuis$x\lt n$,$x\lt 6$. Il suffit donc de vérifier les cas où$(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)\}.$Il est facile de vérifier chacun d'eux.

$\ \checkmark$