Strutturazione dei dati per rappresentare un albero con scoiattoli

Naviga le tue risposte
2

Cosa voglio rappresentare

Supponiamo di avere diversi schemi del seguente tipo:

È un albero su cui le posizioni degli scoiattoli sono rappresentate da un punto blu. Il numero di biforcazioni differisce da un albero all'altro, il numero di scoiattoli varia da un albero all'altro, le posizioni degli scoiattoli variano (e sono su una scala continua), tutti gli alberi non sono necessariamente simmetrici (a differenza dell'immagine) e la lunghezza dei rami è diversa (nella figura la lunghezza dei secondi rami sono tutti uguali, le lunghezze dei terzi rami sono tutte uguali.) Questo non è necessariamente sempre il caso).

Il problema

Sto cercando di descrivere questi alberi con i numeri in modo da poter giocare con questi numeri e calcolare facilmente la distanza tra due scoiattoli (seguendo i rami, non saltando), calcola la distanza tra uno scoiattolo e il terreno (il fondo del tronco) o calcolare la densità degli scoiattoli per ramo.

Gli angoli tra i rami non contano e i rami non hanno larghezza (sono solo linee). Le informazioni di cui ho bisogno sono la lunghezza dei rami (su una scala continua), le posizioni degli scoiattoli (su una scala continua) rispetto al loro ramo, il numero di biforcazioni e le posizioni dei rami rispetto ad altri rami (se uno ramo è collegato a un altro).

Le mie (molto) soluzioni povere

Un modo per descrivere questo albero è di digitalizzarlo. Potrei creare un grande array con 0 s ovunque non ci sia nulla, 1 s ovunque ci sia un ramo e un 2 ovunque ci sia uno scoiattolo (e un ramo necessariamente, nessun scoiattolo volante sull'immagine!). Sarebbe una soluzione, ma vorrei array molto grandi e non è molto utile dedurre cose come la distanza media tra due scoiattoli. Inoltre, perdiamo precisione sulle posizioni degli scoiattoli e sulle lunghezze dei rami

Un'altra soluzione sarebbe quella di avere due serie di vettori e un set di punti. La prima serie di vettori descrive le posizioni di ciascun scoiattolo rispetto all'angolo in basso a sinistra, un'altra serie di vettori definisce la lunghezza e la direzione (anche se non abbiamo bisogno direttamente di queste informazioni) di ciascun ramo e l'insieme di punti indica dove i punti di partenza dei vettori che descrivono i rami. Non sembra davvero una buona idea; è troppo descrittivo (troppe informazioni) e non è molto utile per fare il tipo di calcoli che devo eseguire in seguito.

Mi sento come se fossi concentrato troppo sull'immagine e ho difficoltà a capire come le informazioni di cui ho bisogno potrebbero essere codificate / memorizzate. Puoi aiutarmi con quello?

    
posta Remi.b 23.01.2015 - 03:53
fonte

2 risposte

2

I rami sono abbastanza semplici:

La radice dell'albero è "1".

La prima biforcazione si traduce in rami "1x1" e "1x2" contando da sinistra.

Quindi il ramo in alto a destra dell'albero è etichettato come "1x2x2x2".

Questo schema è molto utile per l'interrogazione in quanto è possibile ottenere tutti i rami secondari di dire "1x2" con un semplice "LIKE" 1x2% "" in SQL.

La posizione dello scoiattolo è più problematica, ma suggerirei una distanza semplice dall'inizio del ramo.

Quindi la tabella sarà simile a: 

Branches:
      Branch    Length
      1         4
      1x1       3
      1x1x1     2
      1x1x1x1   1
      1x2       3
      ...................
      1x2x2     2
      1x2x2x1   1
      1x2x2x1   1

  Branch    Position   Name
  ------    --------   ----
  1         2          Fluffytail
  1         3          Nutkin
  1x1       1          Brighteyes
  1x1       2          Loopy
  1x1x1     1          Lefty
....................
  1x2x2     3          Jumper
  1x2x2x1   1          Topper
  1x2x2x2   1          Rightmost
    
risposta data 23.01.2015 - 08:12
fonte
0

Il modo classico di memorizzare un albero in un database consiste nell'utilizzare una tabella autoreferenziale. Se prendi la tabella delle filiali di James Anderson e aggiungi un campo parentBranchID opzionale, sei lì. L'unico ramo con parentBranchId null sarà il nodo root.

Allo stesso modo, leggi l'intera tabella in memoria usando le classi branch che hanno sia un parentBranchID che un puntatore dell'istanza parentBranch. La classe avrà anche bisogno di una collezione di scoiattoli - questa può essere creata (in Java) con uno strumento OR come myBatis o Hibernate.

Scorrere l'elenco delle classi, creare i collegamenti del puntatore padre e compilare un elenco di rami figlio in ciascun ramo. Ora disponi di un albero in memoria che può essere attraversato in entrambe le direzioni.

Trovare la distanza tra 2 scoiattoli è probabilmente un processo in due fasi.

  1. Partendo da uno scoiattolo, sali sull'albero (verso il nodo radice) fino a trovare un nodo che sia anche un genitore del secondo scoiattolo.
  2. Scrivi una funzione membro ramo come getDistanceTo (scoiattolo scoiattolo). È probabile che sia ricorsivo, come se lo scoiattolo non fosse sul ramo, è necessario provare a turno ogni ramo figlio. Chiama la funzione per ogni scoiattolo e aggiungi le distanze.
risposta data 23.01.2015 - 21:34
fonte

Leggi altre domande sui tag

Principi SOA, incapsulamento e autonomia Le caratteristiche dei contenitori serverlet contro la scalabilità e la tolleranza di errore di un'applicazione Web?