Calcola la raggiungibilità di un punto da un altro

Question

Calcola la raggiungibilità di un punto da un altro

#1 da (1 voti)

0

Ho una matrice che memorizza un insieme di coordinate x positive in modo ordinato, dì arr={1, 4, 5, 9, 12, 45} ecc.

E ho una distanza massima k che posso passare da un punto all'altro di un altro punto, lasciare k=3 . Ora, dati due punti x e y(arr[x]<arr[y]) ho bisogno di determinare se posso raggiungere da x a y . Potrò raggiungere y da x se la distanza tra ogni due hop è inferiore o uguale a k .

Qui supponiamo x=1 y=4 quindi posso passare da 1 & 2 2 quindi 2 & 3 3, ma poiché la distanza tra 3 e 4 è maggiore di 3 non posso andare così in questo caso non posso raggiungere.

Ma se x=1 e y=2 allora posso raggiungere.

Può essere semplicemente risolto con O (n). Ho creato un ciclo for da arr[x] a arr[y] e per ogni coppia di punti controllo se la distanza tra loro è minore o uguale a k .

Ma voglio un algoritmo migliore. Sto pensando di fare qualcosa come la ricerca binaria. Qualcuno può suggerire un buon algoritmo?

algorithms

posta biswpo 07.07.2014 - 13:29

fonte

1 risposta

Leggi altre domande sui tag algorithms

BPMN (modellazione e notazione dei processi di business) Sincronizzazione dati tra app Android in LAN

score 1 · Answer 1

Lo è abbastanza facile da fare O (1) se si precompongono tutte le risposte.

Genera una matrice 2D di differenze massime, tale che maxdiff [x, y] = max (diff [x], diff [x + 1] ... diff [y]). Dal momento che x
Si noti che maxdiff (x, y) = max (maxdiff (x, z), maxdiff (z, y)), quindi il calcolo delle sequenze più lunghe riutilizza il lavoro svolto su quelle più brevi. Costruisci prima i percorsi più corti, poi il più breve e così via.
Il risultato è vero se maxdiff [x, y] < = k.

Per un'implementazione pratica, vorrei memorizzarlo. Cioè, calcola i risultati secondo necessità e mantieni il risultato finché non è nuovamente necessario. Una volta che hai costruito tutti i maxdiff per x..y hai costruito tutte le distanze più brevi in mezzo per un uso successivo.

Questo è un tipico compromesso spazio-velocità.

Credo che questo algoritmo sia O (nlogn) per un singolo valore di (x, y, k), che cade asintoticamente verso O (n) per un grande set di dati di input o se lo stesso (x, y, k) si verifica frequentemente.

Se l'array è di grandi dimensioni, potrebbe non essere pratico costruire l'intera tabella di ricerca, ma una combinazione di memoisation e una tabella parzialmente costruita continueranno a fornire ritorni per set di dati di input di grandi dimensioni.