Come calcolare il percorso più breve tra due punti in una griglia

Question

So che molti algoritmi sono disponibili per calcolare il percorso più breve tra due punti in un grafico o in una griglia, come larghezza-prima, tutte le coppie (Floyd's), Dijkstra's .

Tuttavia, come notato, tutti questi algoritmi calcolare tutti i percorsi in tale grafico o griglia, non solo quelle tra i due punti che ci interessano

mia domanda è:. se ho una griglia, cioè una matrice bidimensionale, e sono interessato a calcolare il percorso più breve tra due punti, ad esempio P1 e P2, e se ci sono restrizioni sul modo in cui posso spostarmi sulla griglia (per esempio solo in diagonale o solo diagonalmente e verso l'alto, ecc.), quale algoritmo è in grado di calcolare questo?

Si noti che se si dispone di una risposta, vorrei che si inserisse il nome dell'algoritmo piuttosto che l'algoritmo stesso (ovviamente, meglio ancora se si pubblica anche l'algoritmo); per esempio, se è l'algoritmo di Dijkstra, o Floyd's, o qualsiasi altra cosa.

Per favore aiutatemi, ci ho pensato per mesi!

---

ragazzi Okey Ho trovato questo algoritmo su TOPCODER.COM qui nella griglia si può muovere solo (in diagonale in su) ma non riesco a capire che cosa è questo algoritmo con qualsiasi mezzo qualcuno potrebbe sapere?

#include<iostream> 
#include <cmath> 

using namespace std; 




inline int Calc(int x,int y) 

{ 



if(abs(x)>=abs(y)) return abs(x); 
int z=(abs(x)+abs(y))/2; 
return z+abs(abs(x)-z); 
} 

class SliverDistance 
{ 


    public: 
int minSteps(int x1,int y1, int x2, int y2) 
{ 
    int ret=0; 
    if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++; 
    return ret+Calc(x2-x1,y2-y1); 
} 
}; 

Answer 1

algoritmo di Lee: http://en.wikipedia.org/wiki/Lee_algorithm

E 'essenzialmente una ricerca di BF, ecco un esempio: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

applicarlo correttamente, controllare la mia risposta qui: Change FloodFill-Algorithm to get Voronoi Territory for two data points? - quando dico marchio, si contrassegna con il numero nella posizione in cui sei venuto da + 1.

Ad esempio, se hai questa griglia, dove un ostacolo * = e puoi muoverti su, giù, sinistra e destra, e inizi da S e devi andare a D, e 0 = posizione libera:

S 0 0 0 
* * 0 * 
* 0 0 * 
0 0 * * 
* 0 0 D 

Hai messo S in coda, poi "espandere" lo:

S 1 0 0 
* * 0 * 
* 0 0 * 
0 0 * * 
* 0 0 D 

quindi espandere tutti i suoi vicini:

S 1 2 0 
* * 0 * 
* 0 0 * 
0 0 * * 
* 0 0 D 

E tutti i vicini quelle dei vicini:

S 1 2 3 
* * 3 * 
* 0 0 * 
0 0 * * 
* 0 0 D 

E così via, alla fine si ottiene:

S 1 2 3 
* * 3 * 
* 5 4 * 
7 6 * * 
* 7 8 9 

Quindi la distanza da S a D è 9. Il tempo di esecuzione è O (NM), dove N = numero di righe e M = numero di colonne. Penso che questo sia l'algoritmo più semplice da implementare sulle griglie, ed è anche molto efficace nella pratica. Dovrebbe essere più veloce di un classico dijkstra, sebbene dijkstra potrebbe vincere se lo si implementa usando gli heap.

Answer 2

Utilizzare l'algoritmo A Star (A*).

Answer 3

Potrebbe essersi verificato un errore. Esistono diverse varianti dell'algoritmo di Dijkstra. Si calcola il percorso più breve da ogni punto a ogni altro punto (come quello di Floyd).

Tuttavia, l'algoritmo Dijkstra tipico si basa su una coda di priorità e calcola solo il percorso minimo richiesto. Costruisce diversi percorsi durante la sua esecuzione, ma quelli sono tutti percorsi parziali da A ad altri nodi che potrebbero trovarsi sul percorso della soluzione finale.

Quindi, puoi facilmente interpretare la griglia come un grafico (le restrizioni come le diagonali possono quindi essere prese in considerazione di conseguenza) ed eseguire una ricerca Dijkstra per il percorso più breve da A a B su quello. Si tratta solo di modellare il tuo problema, non di aver bisogno di un algoritmo elaborato.

Answer 4

Se il movimento è abbastanza restrittivo (ad esempio, è possibile spostarsi solo verso destra, verso l'alto o verso la diagonale verso l'alto e verso destra), è possibile sfruttare i suoi sottoproblemi sovrapposti e la natura di sottostruttura subottimale e utilizzare dynamic programming.

Answer 5

Quello che non riesco a capire è, se si desidera il percorso più breve tra A e B, non è ancora necessario guardare da A a C e da A a D se C e D puntare a B? Il tuo percorso più breve potrebbe benissimo essere A-C-B o A-D-B. Hai solo bisogno di eliminare nodi non connessi. In uno dei miei progetti, ho preso i punti A e B, controllato per vedere quali altri punti erano collegati e quelli che non erano stati cancellati dall'intero grafico. Quindi ho proceduto con l'algoritmo di Dijkstra.

Answer 6

La griglia forma un grafico (o almeno può essere visualizzato come un grafico). Eliminare alcune direzioni di movimento indica che si tratta di un grafico diretto. Se non è possibile spostarsi da un nodo a un altro, questo è un bordo che non è presente nel grafico.

Una volta che hai codificato la griglia in forma di grafico, è una semplice questione selezionare tra i ben noti algoritmi di grafi (di cui sei apparentemente già a conoscenza) per attraversarlo per il tipo di risultato desiderato (es. percorso più breve).

Modifica: ho guardato la risposta che hai postato, ma non sono sicuro di cosa dovrebbe essere/fare quel codice. Ad esempio, ha: if(y>=0) max(abs(x),y);. Questo non sembra (almeno per me) avere molto senso - il risultato dello max viene semplicemente gettato via. Per realizzare qualcosa di utile, deve essere restituito o assegnato o qualcosa su quell'ordine. Così com'è, il meglio che si possa sperare è che il compilatore lo identifica come codice morto e non genera nulla per esso.

La mia ipotesi è che il codice non funzioni proprio come previsto, e se fa qualcosa di utile, è più per caso che per il design. Ci vorrebbero un bel po 'di tempo e impegno per essere sicuri di aver risolto problemi come questo al punto che eri veramente sicuro di quello che ha fatto, e ancora più difficile da indovinare cosa fosse realmente previsto.

Answer 7

utilizzare un algoritmo A * per trovare il percorso tra due punti in una griglia 2D. http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

Answer 8

Ecco un'implementazione python del percorso più breve in una matrice da (0,0) a (0, m-1) utilizzando BFS. Puoi cambiarlo per adattarlo a punti variabili.

n,m,k1,k2=[int(i) for i in input().split()] 
arr=[[int(j) for j in input().split()] for i in range(n)] 
x=[[-1 for i in range(m)] for j in range(n)] 
x[0][0]=0 
vis={} 
q=[(0,0)] 
while len(q)!=0: 
    curr=q[0] 
    rem=q.pop(0) 
    vis[curr]=True 
    r=curr[0] 
    c=curr[1] 
    if r-1>=0 and arr[r-1][c]==0: 
     if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True: 
      q.append((r-1,c)) 
      x[r-1][c]=x[r][c]+1 
    if r+1<n and arr[r+1][c]==0: 
     if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True: 
      q.append((r+1,c)) 
      x[r+1][c]=x[r][c]+1 
    if c-1>=0 and arr[r][c-1]==0: 
     if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True: 
      q.append((r,c-1)) 
      x[r][c-1]=x[r][c]+1 
    if c+1<m and arr[r][c+1]==0: 
     if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True: 
      q.append((r,c+1)) 
      x[r][c+1]=x[r][c]+1 
    #for i in x: 
     #print(i) 
ans=x[0][m-1] 
if ans==-1: 
    print(-1) 
else: 
    print(ans) 

• matrice di ingresso dovrebbe consistere di 0 e di 1. 0 è per il possibile movimento.
• n è il numero di righe.
• m è il numero di colonne.
• arr è la matrice indicata.
• x è la matrice della distanza da (0,0).
• vis è un dizionario che fornisce un valore booleano se il nodo è visitato.
• l'output di -1 indica che non esiste un percorso simile.