corsa minima da punto a punto con passi incrementali

Question

È la prima volta che faccio una domanda qui. Ho un curioso problema sull'algoritmo, al centro del piano cartesiano (0,0) devo andare in un altro punto (x, y) -x e y appartengono a Z numeri - ma posso usare solo passaggi orizzontali e verticali e questo passo aumenta di una unità, un'unità è una distanza da (0,0) a (0,1), (1,0), (-1,0) o (0,-1).

Ad esempio, devo andare al punto (1,1) e i passaggi sono:

• Vai a (1,0), un passo di 1 unità.
• Vai a (1,-2) un passo di 2 unità.
• Infine, vai a (1,1) un passo di 3 unità.

E per questo esempio la risposta è che ho bisogno di 3 passi con 6 unità di distanza.

Ovviamente ci sono diversi modi per raggiungere un punto dal centro ma il problema necessita del minimo.

Esiste una formula o un algoritmo per trovare il numero minimo di passi e la distanza di questa via?

Bene, se ne trovi uno (passi o distanza), l'altro è facile da trovare perché la distanza è una somma di N (conteggio di passi) primi numeri naturali.

Grazie per aver letto questo e per le vostre risposte e suggerimenti.

Answer 1

Domanda interessante. È sorprendente che la risposta dipenda solo da$|x|+|y|$. Ad esempio, è necessario raggiungere lo stesso numero di passaggi$(1,1)$o$(0,2)$.

---

Il passo minimo è il minimo intero non negativo$n$tale che$n(n+1)/2-(|x|+|y|)$è pari e non negativo.

Ecco un$O(1)$-time algoritmo che restituisce il valore sopra descritto, dove least_n, cioè,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, è il minimo intero non negativo$n$tale che$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

Dato il numero di passaggi$s$, la distanza percorsa è$1+2+\cdots+s=s(s+1)/2$.

---

La correttezza della formula e dell'algoritmo di cui sopra deriva dalla seguente caratterizzazione.

Proposizione. Il numero minimo di passaggi da$(0,0)$a$(x,y)$è il minimo intero non negativo$n$tale che$n(n+1)/2-(|x|+|y|)$è non negativo e pari.

Prova . Se possiamo andare a$(x,y)$in$n$passi, la somma di alcuni numeri compresi tra 1 e$n$o devono esserlo le loro negazioni$x$e la somma dei numeri rimanenti o delle loro negazioni deve essere$y$, cioè,$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$per una scelta di tutti$\pm$'S. Questo significa,$$1+2+\cdots+ n - (|x| + |y|)$$è non negativo e pari.

Adesso basta dimostrarlo$(x,y)$è raggiungibile in$n$passi se$n(n+1)/2-(|x|+|y|)$è non negativo e pari. Dimostriamolo per induzione su$n$.

I casi base,$n=0$o$1$significa$(x,y)=(0,0), (0,1), (1,0)$. Questi casi sono immediati da verificare.

Supponiamo che, come ipotesi di induzione, sia corretto per minore$n$'S. Si consideri ora il caso di$n\ge2$insieme a$n(n+1)/2-(|x|+|y|)$non negativo e pari. Possiamo supporre$x$e$y$sono non negativi; altrimenti, ad esempio, se$x$è negativo, possiamo cambiare$x$al suo valore assoluto e invertire la direzione di tutti i passi che sono paralleli a$X$-asse.

Ci sono tre casi.

• $x \ge n$. Permettere$x'= x-n$. Quindi$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$è non negativo e pari. Per ipotesi di induzione, possiamo andare a$(x',y)$in$n-1$passi. Raggiungere$(x,y)$in$n$passi, continuiamo$n$unità in direzione X.
• $y\ge n$. Questo è simmetrico al caso precedente.
• $0\le x\lt n$e$0\le y\lt n$. Ci sono due sottocasi.
  • $x\ge 2$e$y\ge 2$. Permettere$x'=(n-1)-x$e$y'=n-y$. Quindi$|x'|\le n-3$e$|y'|\le n-2$.$$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$La parità di$(n-1)(n-1)/2-(|x'|+|y'|)$equivale a$n(n+1)/2-(|x|+|y|)$, cioè pari. Per ipotesi di induzione, possiamo andare a$(x',y')$in$n-2$passi. Invertendo tutti i passaggi, possiamo andare a$(-x', -y')$in$n-2$anche i passi. Raggiungere$(x,y)$in$n$passi, possiamo continuare con altri due passi,$n$unità in direzione X e$n+1$unità in direzione Y.
  • Uno di$x$e$y$è$0$o$1$. Permettere$g(k)=k(k+1)/2-(|x|+|y|)$. Il più piccolo intero non negativo tale che$g(k)\ge0$è$m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Dal momento che entrambi$x$e$y$sono$\lt n$e uno di loro lo è$0$o$1$,$$m\le \frac{1+\sqrt{8n+1}}2.$$quando$g(m)$è anche,$n=m$per definizione. quando$g$è strano, dal momento che entrambi$g(m+1)=g(m)+(m+1)$o$g(m+2)=g(m)+(m+1)+(m+2)$deve essere pari, neanche$m+1$o$m+2$deve essere$n$. Quindi, se$g(m)$è pari o dispari, abbiamo$$n\le m+2.$$Combinando le due disuguaglianze di cui sopra, abbiamo$$n\le \frac{5+\sqrt{8n+1}}2,$$il che implica$n\le 6$. Poiché la direzione X e la direzione Y sono simmetriche, supponiamo$y=0,1$. Da$x\lt n$,$x\lt 6$. Quindi è sufficiente verificare i casi in cui$(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)\}.$È facile verificare ciascuno di essi.

$\ \checkmark$