Algoritmo: trasformazione della distanza - qualsiasi algoritmo più veloce?

Question

Sto provando a risolvere il problema della distanza (utilizzando la distanza di Manhattan). Fondamentalmente, dando matrice 0 e 1 del programma deve assegnare distanze di ogni posizione vicina 1. Ad esempio, per questo

0000 
0100 
0000 
0000 

distanza trasformare matrice è

2123 
1012 
2123 
3234 

Possibili soluzioni da testa sono :

quelli più lento (più lenti perché ho provato per la loro attuazione - erano in ritardo rispetto a molto grandi matrici):

1. Brute-force: per ogni 1 programma letto, modificare le distanze di conseguenza dall'inizio alla fine.

2. Ricerca di ampiezza a partire da 0 - per ogni 0, il programma cerca l'interno 1 più vicino.

3. Uguale a 2 ma a partire dal segno di 1 ogni distanza verso l'esterno.

4. molto più veloce (leggere da codice di altre persone)

   Larghezza-prima ricerca dal 1 di

   1. Assign all values in the distance matrix to -1 or very big value. 
   2. While reading matrix, put all positions of 1's into queue. 
   3. While queue is not empty 
       a. Dequeue position - let it be x 
       b. For each position around x (that has distance 1 from it) 
        if position is valid (does not exceed matrix dimensions) then 
         if distance is not initialized or is greater than (distance of x) + 1 then 
          I. distance = (distance of x) + 1 
          II. enqueue position into queue 
   

volevo chiedere se c'è una soluzione più rapida a questo problema. Ho provato a cercare algoritmi per la trasformazione a distanza, ma la maggior parte di essi ha a che fare con le distanze euclidee.

Grazie in anticipo.

Answer 1

L'ampiezza della ricerca iniziale eseguirà le operazioni Θ(n*m) dove n e m sono la larghezza e l'altezza della matrice.

È necessario fornire i numeri Θ(n*m), quindi non è possibile ottenere più velocemente di quello da un punto di vista teorico.

Suppongo che tu non sia interessato ad andare verso discussioni che riguardano la cache e tali ottimizzazioni.

---

Si noti che questa soluzione funziona in casi più interessanti. Per esempio, immaginate la stessa domanda, ma ci potrebbero essere diverse "fonti":

00000 
01000 
00000 
00000 
00010 

Utilizzando BFS, si otterrà il seguente percorso residuo più vicino-source nella stessa complessità temporale:

21234 
1
21223 
32212 
1 

Tuttavia, con una singola fonte, esiste un'altra soluzione che potrebbe avere prestazioni leggermente migliori nella pratica (anche se la complessità è sempre la stessa).

Prima, osserviamo la seguente proprietà.

Proprietà: Se l'origine è in (a, b), quindi un punto (x, y) ha la seguente Manhattan distanza:

d(x, y) = abs(x - a) + abs(y - b) 

Questo dovrebbe essere abbastanza facile dimostrare. Quindi un altro algoritmo sarebbe:

for r in rows 
    for c in cols 
    d(r, c) = abc(r - a) + abs(c - b) 

che è molto breve e facile.

---

A meno che non si scriva e non si verifichi, non esiste un modo semplice per confrontare i due algoritmi. Supponendo un'implementazione efficace delimitata coda (con un array), si hanno le seguenti principali operazioni per cella:

• UST: inserimento coda/delezione, visita ogni nodo 5 volte (quattro volte da vicini, e una volta fuori della coda)
• formula Direct: due sottrazione e due if s

sarebbe davvero dipenderà dal compilatore e sue ottimizzazioni, nonche la specifica architettura della CPU e di memoria a dire che un rendimento migliore.

Detto questo, consiglierei di andare con quello che sembra più semplice per voi. Si noti tuttavia che con più fonti, nella seconda soluzione occorrerebbero più passaggi sull'array (o calcoli a distanza multipli in un solo passaggio) e che sicuramente avrebbe una prestazione peggiore di BFS per un numero sufficiente di fonti.

Answer 2

Non hai bisogno di una coda o qualcosa del genere. Nota che se (i, j) è a distanza da (k, l), un modo per capire che la distanza è di andare a sinistra o a destra | i-k | volte e poi su o giù | j-l | volte.

Quindi, inizializza la tua matrice con numeri grandi e inserisci uno zero ovunque tu abbia un 1 nel tuo input. Ora fare qualcosa di simile:

for (i = 0; i < sx-1; i++) { 
    for (j = 0; j < sy-1; j++) { 
    dist[i+1][j] = min(dist[i+1][j], dist[i][j]+1); 
    dist[i][j+1] = min(dist[i][j+1], dist[i][j]+1); 
    } 
    dist[i][sy-1] = min(dist[i][sy-1], dist[i][sy-2]+1); 
} 
for (j = 0; j < sy-1; j++) { 
    dist[sx-1][j] = min(dist[sx-1][j], dist[sx-2][j]+1); 
} 

A questo punto, avete trovato tutti i percorsi più brevi che coinvolgono solo andando verso il basso o destra. Se fai una cosa simile per andare su e sinistra, dist[i][j] ti darà la distanza da (i, j) al più vicino 1 nella tua matrice di input.