Algoritmo per trovare due punti più lontani l'uno dall'altro

StackOverflow https://stackoverflow.com/questions/477591

Domanda

Sto cercando un algoritmo da usare in un gioco di corse. La mappa / livello / traccia è generata casualmente, quindi ho bisogno di trovare due posizioni, inizio e obiettivo, che sfrutti la maggior parte della mappa.

  • L'algoritmo funziona all'interno di uno spazio bidimensionale
  • Da ogni punto, si può attraversare solo il punto successivo in quattro direzioni; su, giù, a sinistra, a destra
  • I punti possono essere solo bloccati o non bloccati, solo i punti non bloccati possono essere attraversati

Per quanto riguarda il calcolo della distanza, non dovrebbe essere il "percorso degli uccelli" per mancanza di una parola migliore. Il percorso tra A e B dovrebbe essere più lungo se c'è un muro (o altra area di blocco) tra di loro.

Non sono sicuro da dove cominciare, i commenti sono molto graditi e le soluzioni proposte sono preferite nello pseudo codice.

Modifica: Esatto. Dopo aver guardato codice gs I ci ha dato un altro colpo. Invece di Python, questa volta l'ho scritto in C ++. Tuttavia, anche dopo aver letto l'algoritmo Dijkstras , inondazione e Soluzione di Hosam Alys , non riesco a individuare alcuna differenza cruciale. Il mio codice funziona ancora, ma non così velocemente come sembra che tu stia eseguendo il tuo. La fonte completa è su pastie . Le uniche righe interessanti (immagino) è la variante Dijkstra stessa nelle righe 78-118.

Ma la velocità non è il problema principale qui. Gradirei molto l'aiuto se qualcuno fosse così gentile da evidenziare le differenze negli algoritmi.

  • Nell'algoritmo di Hosam Alys, l'unica differenza che scansiona dai bordi invece che da ogni nodo?
  • In Dijkstras tieni traccia e sovrascrivi la distanza percorsa, ma non in piena, ma è tutto?
È stato utile?

Soluzione

Supponendo che la mappa sia rettangolare, è possibile scorrere su tutti i punti di confine e iniziare un riempimento per trovare il punto più distante dal punto di partenza: 

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

Suppongo che questo sarebbe in O (n ^ 2) . Se non sbaglio, è (L + W) * 2 * (L * W) * 4 , dove L è la lunghezza e W è la larghezza della mappa, (L + W) * 2 rappresenta il numero di punti del bordo sopra il perimetro, (L * W) è il numero di punti, e 4 è il presupposto che un alluvione accedesse ad un punto per un massimo di 4 volte (da tutte le direzioni). Poiché n è equivalente al numero di punti, questo equivale a (L + W) * 8 * n , che dovrebbe essere migliore di O (n 2 ) . (Se la mappa è quadrata, l'ordine sarebbe O(16n1.5 ) .)

Aggiornamento: come da commenti, dal momento che la mappa è più un labirinto (rispetto a uno con ostacoli semplici come pensavo inizialmente), potresti fare la stessa logica sopra, ma controllando tutti i punti nella mappa (al contrario dei punti sul bordo). Questo dovrebbe essere in ordine di O(4n2 ) , che è comunque migliore sia di F-W che di Dijkstra.

Nota: Riempimento di inondazioni è più adatto a questo problema , poiché tutti i vertici sono collegati direttamente attraverso solo 4 bordi. Un primo passaggio trasversale della mappa può produrre risultati in modo relativamente rapido (solo in O (n) ). Suppongo che ogni punto possa essere verificato nel riempimento di alluvione da ciascuno dei suoi 4 vicini, quindi il coefficiente nelle formule sopra.

Aggiornamento 2: Sono grato per tutto il feedback positivo che ho ricevuto riguardo a questo algoritmo. Un ringraziamento speciale a @Georg per la sua recensione .

P.S. Eventuali commenti o correzioni sono ben accetti.

Altri suggerimenti

Seguire la domanda su Floyd-Warshall o il semplice algoritmo di Hosam Aly :

Ho creato un programma di test che può utilizzare entrambi i metodi. Questi sono i file:

In tutti i casi di test Floyd-Warshall è stato di gran lunga più lento, probabilmente a causa della quantità molto limitata di bordi che aiutano questo algoritmo a raggiungere questo obiettivo.

Erano le volte, ogni volta che il campo era quadruplo e 3 campi su 10 erano un ostacolo. 

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

Il tempo di Hosam Aly sembra quadratico, quindi consiglierei di usare quell'algoritmo.  Anche il consumo di memoria di Floyd-Warshall è n 2 , chiaramente più del necessario. Se hai idea del perché Floyd-Warshall è così lento, lascia un commento o modifica questo post.

PS: non scrivo C o C ++ da molto tempo, spero di non aver fatto troppi errori.

Ho eliminato il mio post originale raccomandando l'algoritmo Floyd-Warshall. : (

gs ha fatto un benchmark realistico e indovina un po ', FW è sostanzialmente più lento del "riempimento di inondazione" di Hosam Aly algoritmo per dimensioni di mappe tipiche! Quindi anche se F-W è un algoritmo interessante e molto più veloce di Dijkstra per i grafici densi, non posso più consigliarlo per il problema del PO, che coinvolge grafici molto sparsi (ogni vertice ha solo 4 bordi).

Per la cronaca:

  • Un'implementazione efficiente di L'algoritmo di Dijkstra richiede tempo O (Elog V) per un grafico con bordi E e vertici V.
  • Hosam Aly's "fill flood" è una breadth first search , ovvero O (V). Questo può essere considerato come un caso speciale dell'algoritmo di Dijkstra in cui nessun vertice può essere rivisto alla stima della distanza.
  • Algoritmo Floyd-Warshall accetta O (V ^ 3 ) tempo, è molto facile da codificare ed è ancora il più veloce per i grafici densi (quei grafici in cui i vertici sono in genere collegati a molti altri vertici). Ma non è la scelta giusta per l'attività del PO, che implica grafici molto sparsi.

Sembra che ciò che desideri siano i punti finali separati dal diametro del grafico . Un'approssimazione abbastanza buona e facile da calcolare è quella di scegliere un punto casuale, trovare il punto più lontano da quello e quindi trovare il punto più lontano da lì. Questi ultimi due punti dovrebbero essere vicini al massimo separato.

Per un labirinto rettangolare, ciò significa che due riempimenti di alluvione dovrebbero darti una coppia abbastanza buona di punti di inizio e fine.

Raimund Seidel fornisce un metodo semplice usando la moltiplicazione della matrice per calcolare la matrice della distanza di tutte le coppie su un grafico non ponderato e non orientato (che è esattamente quello che vuoi) nella prima sezione del suo documento Sul problema del percorso più breve per tutte le coppie in grafici non ponderati non indirizzati  [Pdf] .

L'ingresso è la matrice di adiacenza e l'uscita è la matrice della distanza del percorso più breve di tutte le coppie. Il tempo di esecuzione è O (M (n) * log (n)) per n punti in cui M (n) è il tempo di esecuzione dell'algoritmo di moltiplicazione della matrice.

L'articolo fornisce anche il metodo per calcolare i percorsi effettivi (nello stesso tempo di esecuzione) se ne hai bisogno anche tu.

L'algoritmo di Seidel è interessante perché il tempo di esecuzione è indipendente dal numero di spigoli, ma in realtà qui non ci interessa perché il nostro grafico è scarso. Tuttavia, questa potrebbe essere comunque una buona scelta (nonostante il tempo di esecuzione leggermente peggiore di n ^ 2) se si desidera la matrice della distanza di tutte le coppie, e ciò potrebbe anche essere più facile da implementare e eseguire il debug rispetto alle inondazioni su un labirinto.

Ecco lo pseudocodice: 

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

Per ottenere la coppia di punti con la massima distanza, restituiamo semplicemente argmax_ij (d_ij)

Terminato un mockup di pitone della soluzione dijkstra al problema. Il codice è diventato un po 'lungo quindi l'ho pubblicato altrove: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

Nella dimensione impostata, sono necessari circa 1,5 secondi per eseguire l'algoritmo per un nodo. L'esecuzione per ogni nodo richiede alcuni minuti.

Non sembra funzionare però, mostra sempre l'angolo superiore sinistro e inferiore destro come il percorso più lungo; 58 piastrelle. Che ovviamente è vero, quando non hai ostacoli. Ma anche aggiungendo un paio di quelli posizionati casualmente, il programma trova ancora quello più lungo. Forse è ancora vero, difficile da testare senza forme più avanzate.

Ma forse può almeno mostrare la mia ambizione.

Ok, "algoritmo di Hosam" è una prima ricerca ampia con una preselezione sui nodi. L'algoritmo di Dijkstra NON deve essere applicato qui, perché i bordi non hanno pesi.

La differenza è cruciale, perché se i pesi dei bordi variano, è necessario tenere aperte molte opzioni (percorsi alternativi) e verificarle ad ogni passaggio. Questo rende l'algoritmo più complesso. Con l'ampiezza della prima ricerca, esplori semplicemente tutti i bordi una volta in modo da garantire che trovi il percorso più breve per ciascun nodo. cioè esplorando i bordi nell'ordine in cui li trovi.

Quindi sostanzialmente la differenza è che Dijkstra deve "tornare indietro" e guardare i bordi che ha esplorato prima per assicurarsi che stia seguendo il percorso più breve, mentre la prima ricerca dell'ampiezza sa sempre che sta seguendo il percorso più breve.

Inoltre, in un labirinto non è garantito che i punti sul bordo esterno facciano parte del percorso più lungo. Ad esempio, se hai un labirinto a forma di spirale gigante, ma con l'estremità esterna che ritorna al centro, potresti avere due punti uno nel cuore della spirale e l'altro alla fine della spirale, entrambi nel mezzo!

Quindi, un buon modo per farlo è usare una prima ricerca ampia da ogni punto, ma rimuovere il punto di partenza dopo una ricerca (conosci già tutti i percorsi da e verso esso). La complessità della larghezza prima è O (n), dove n = | V | + | E |. Lo facciamo una volta per ogni nodo in V, quindi diventa O (n ^ 2).

La tua descrizione mi sembra un problema routing labirinto . Dai un'occhiata al Lee Algorithm . Libri sui problemi di localizzazione e percorso nella progettazione di VLSI possono aiutarti - Sherwani's & Algorithms for VLSI Physical Design Automation " è buono e potresti trovare VLSI Physical Design Automation di Sait e Youssef utile (e più economico nella sua versione di Google ...)

Se i tuoi oggetti (punti) non si muovono frequentemente, puoi eseguire tale calcolo in un tempo molto più breve di O (n ^ 3).

Tutto ciò che serve è dividere lo spazio in griglie di grandi dimensioni e pre-calcolare la distanza tra le griglie. Quindi la selezione di coppie di punti che occupano griglie più distanti è una questione di semplice ricerca nella tabella. In media, dovrai accoppiare solo una piccola serie di oggetti.

Questa soluzione funziona se le metriche della distanza sono continue. Quindi se, ad esempio, ci sono molte barriere nella mappa (come nei labirinti), questo metodo potrebbe fallire.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top