Conserva un albero vicino ai vicini vicini

Question

Conserva un albero vicino ai vicini vicini

#1 da (1 voti)
#2 da (0 voti)

-1

Vorrei trovare una struttura efficiente (velocità e volume) per memorizzare i nodi e il loro vicinato.

Il mio input è formato da punture nel seguente formato

 ./X/Y.log

dove X ∈ [0,359] e Y ∈ [0,169] e ciascuna coppia di ( X, Y ) hanno definito le coordinate di cella su una griglia della dimensione [170x360].

Vorrei trovare quali celle sono vicine (sopra, sotto, destra e sinistra), al massimo 4 possibilità e memorizzare queste informazioni (coordinate e direzione). La struttura, in cui verranno archiviate le informazioni, non deve contenere informazioni duplicate (ad esempio, la cella (50,50) è vicina alla cella (51,50) dal lato sinistro, ma la cella (51,50) è anche vicina alla cella (50,50) dal lato destro. Dovrebbe essere memorizzato solo uno di questi ".

Un'informazione aggiuntiva, il numero di stringhe di input (formato ./ X / Y.log ) non è più del 5% della quantità totale di celle possibili (360 * 170 = 61200 celle possibili ).

Quale struttura di archiviazione dovrei essere all'altezza del mio problema? (Il codice dovrebbe essere scritto in C ++)

c++ data-structures algorithms trees

posta Eagle 21.06.2013 - 00:49

fonte

2 risposte

Leggi altre domande sui tag c++ data-structures algorithms trees

Verifica l'unicità del nuovo contenuto Git Branch Model per progetti iOS con uno sviluppatore [duplicato]

score 1 · Answer 1

Penso che una struttura dati grafica possa risolvere il tuo problema. Poiché le connessioni non sono direzionali, un albero potrebbe essere difficile da implementare. Inoltre, con un albero, il "figlio" di un nodo potrebbe essere il "figlio" di un altro nodo che porta a problemi su come costruire la struttura ad albero.

score 0 · Answer 2

Per l'accesso rapido e l'archiviazione efficiente dei dati desiderati, è possibile memorizzare una coppia di oggetti std::set le cui voci sono le coordinate delle celle. Il primo è l'insieme di celle con un vicino a destra, il secondo l'insieme di quelle con un vicino di sotto.

Se l'efficienza che produce questa struttura è importante per te, allora ti consiglio di creare un insieme di tutte le coordinate di celle, quindi di scorrere su di esso e per ogni cella scoprire se i suoi vicini a destra e in basso sono nel set. (Entrambe le ricerche sono veloci.)

Se devi considerare i vicini più lontani, usa std::map per memorizzare le coordinate della cella come chiave e le coordinate del vicino come valore. Per trovare quei vicini, puoi utilizzare un collegamento .