[C] Alberi n-ari: quale implementazione? [Archivio]

View Full Version : [C] Alberi n-ari: quale implementazione?

Red_Knight

05-01-2010, 16:14

Salve a tutti... gradirei dalle vostre menti geniali un suggerimento: devo calcolare il diametro (il più lungo cammino minimo tra due nodi) di un albero generico. Più che un consiglio sull'algoritmo (che comunque non mi dispiacerebbe :D) mi servirebbe un'idea per la struttura dati da utilizzare per rappresentare l'albero n-ario: vorrei trovare la più snella possibile. Il tutto senza l'ausilio di librerie non basilari.

fero86

05-01-2010, 17:43

esiste una nota biezione tra l'insieme degli alberi N-ari e quello degli alberi binari. per rappresentare un albero N-ario basta che ogni nodo sia rappresentato dalla seguente struct:
typedef struct _NODE
{
struct _NODE *m_pFirstChild;
struct _NODE *m_pNextSibling;
} NODE, *PNODE; dove m_pFirstChild é il puntatore al primo dei figli del nodo e m_pNextSibling é il puntatore al prossimo fratello del nodo; in sostanza i figli di un nodo vengono mantenuti in una lista linkata di cui la testa é puntata dal campo m_pFirstChild del nodo stesso e ogni figlio punta al successivo tramite il proprio campo m_pNextSibling. il motivo per cui ho parlato di biezione con l'insieme degli alberi binari é che quella che vedi sopra é una struct contenente due puntatori, la stessa struttura dati che useresti per rappresentare alberi binari.

Red_Knight

05-01-2010, 17:48

Grazie mille, ma la struttura "figlio a sinistra - fratello a destra" permette un accesso sequenziale e non conserva esplicitamente i legami di parentela; come faccio poi a calcolare il diametro? A me - ammetto di essere molto disabituato alla programmazione - non è venuto in mente niente :(

khelidan1980

05-01-2010, 19:53

Red_Knight

05-01-2010, 21:57

Che da un singolo nodo non è possibile risalire alla paternità del nodo stesso; e - ripeto, sono io scarso - non mi viene in mente come calcolare il diametro senza sfruttare la paternità.

wingman87

05-01-2010, 22:38

Riguardo la definizione di diametro, ho trovato una definizione differente: definito C(l) la cardinalità dei nodi del livello l si definisce diametro il massimo valore di C(l).
Per risolvere il problema credo che il modo migliore sia fare una visita per livelli contando di volta in volta i nodi del livello corrente ed aggiornando eventualmente il massimo.

Red_Knight

05-01-2010, 23:17

Può darsi che la definizione comunemente intesa di diametro sia quella - io non ne ho idea - ma purtroppo io devo trovare il diametro secondo la definizione che ho dato io :(

fero86

06-01-2010, 02:07

Che da un singolo nodo non è possibile risalire alla paternità del nodo stesso; e - ripeto, sono io scarso - non mi viene in mente come calcolare il diametro senza sfruttare la paternità. e allora aggiungi un terzo puntatore:
typedef struct _NODE
{
struct _NODE *m_pParent;
struct _NODE *m_pFirstChild;
struct _NODE *m_pNextSibling;
} NODE, *PNODE;

fero86

06-01-2010, 02:28

Può darsi che la definizione comunemente intesa di diametro sia quella - io non ne ho idea - ma purtroppo io devo trovare il diametro secondo la definizione che ho dato io :( veramente la tua definizione non é molto chiara: hai detto che il diametro tra due nodi é il piu lungo cammino minimo tra i due, la qual cosa suppone che nel caso generale esistano tra due nodi tanti cammini minimi, ma si puó dimostrare per induzione strutturale che in un albero N-ario tra due nodi esiste uno e un solo cammino minimo; tutti gli altri cammini, non minimi, ripassano piu volte per gli stessi archi. per l'induzione strutturale si usano come costruttori di alberi N-ari una funzione banale che spara in output un albero costituito da un solo nodo e una famiglia di funzioni fk (fai conto che k é scritto piccolo in basso) ciascuna delle quali prende in input k alberi N-ari e lega tutte le radici assieme ad un nuovo nodo radice (quindi questo nuovo nodo ha k figli). segue la dimostrazione.
caso base, albero N-ario generato dalla funzione banale: ammettiamo che la tesi abbia senso e diamola per vera.
caso induttivo, albero generato da una generica funzione fk: ci sono tre casi distinti:
1) entrambi gli estremi del cammino si trovano dentro uno dei k alberi in input - teorema verificato per ipotesi induttiva.
2) uno degli estremi del cammino é la nuova radice e l'altro si trova dentro uno dei k alberi, diciamo l'i-esimo albero; per costruzione il cammino tra i due nodi deve passare per la radice dell'albero i-esimo (chiamiamola radice i-esima), quindi il cammino in questione é formato dall'arco che unisce la radice i-esima alla nuova radice comune piu il cammino minimo tra la radice i-esima e l'estremo che sta dentro l'albero i-esimo; quest'ultimo cammino é minimo e unico per ipotesi induttiva, quindi tutto il cammino é minimo e unico.
3) i due estremi del cammino si trovano in due diversi alberi in input, diciamo l'i-esimo e il j-esimo; per costruzione il cammino passa per la nuova radice comune, quindi semplicemente vale lo stesso l'argomento del caso precedente applicato due volte ai due alberi, i-esimo e j-esimo.

fero86

06-01-2010, 12:17

altra dimostrazione, molto piu semplice: se tra due nodi di un albero esistessero piu cammini distinti almeno in parte, l'albero conterrebbe cicli e non sarebbe un albero. é detta in maniera solo intuitiva ma si puó approfondire.

marco.r

06-01-2010, 13:48

Può darsi che la definizione comunemente intesa di diametro sia quella - io non ne ho idea - ma purtroppo io devo trovare il diametro secondo la definizione che ho dato io :(

La struttura dati inizialmente proposta da fero86 va bene. In alternativa puoi usarne una in cui hai un puntatore al padre e una lista di figli, (ognuno quindi con puntatore al padre) ma e' praticamente la stessa cosa.

In ogni caso il puntatore al padre non ti serve perche' puoi ottenere il risultato che cerchi con una visita ricorsiva dell'albero.

L'osservazione di base da fare e' che il diametro massimo per un albero e' uno dei seguenti:

- Il diametro massimo di uno dei figli (ovvero un cammino che non passa per la radice)

- Presi i due figli di altezza maggiore, sommi le due altezze + 1 (ovvero un cammino che passa per la radice). Questo solo nel caso ci siano almeno due figli.

Procedi ricorsivamente con questo concetto ed ottieni la soluzione.
Come vedi non e' affatto necessario sapere chi e' il padre.

BlackAuron

06-01-2010, 13:54

Con diametro, solitamente si intende:

max(min(d(x,y)))

con x e y nodi dell'albero. In poche parole, detto A l'insieme delle distanze minime tra i nodi di T, il diametro è dato da diam(T) = max(A).
Ora, per risolvere il problema, quello che ti consiglio di fare è usare
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
con questo, per ogni nodo trovi il costo minimo per andare dal nodo x a tutti gli altri nodi dell'albero.
Se cicli l'algoritmo su tutti i nodi, e prendi il massimo dei valori che ottieni, hai il diametro cercato.
Poi ci sono casi particolari: se i pesi fossero tutti non negativi, allora ti potresti limitare a controllare i costi delle foglie dell'albero ... tutto sta nello stabilire cosa intendi per generico :)

PS: se i costi degli archi fossero tutti unari, il problema si converte nel trovare la profondità dell'albero, problema che, come han detto sopra, si risolve in modo elementare con una funzione ricorsiva:

h(padre) = 1+max(h(figli))

fero86

06-01-2010, 14:43

Con diametro, solitamente si intende:

max(min(d(x,y)))

con x e y nodi dell'albero. In poche parole, detto A l'insieme delle distanze minime tra i nodi di T, il diametro è dato da diam(T) = max(A). scusa ma non sto capendo: cos'é d? cos'é una "distanza" tra due nodi? cos'é diam?

Poi ci sono casi particolari: se i pesi fossero tutti non negativi, [...] quali pesi? :mbe:

PS: se i costi degli archi fossero tutti unari, il problema si converte nel trovare la profondità dell'albero, problema che, come han detto sopra, si risolve in modo elementare con una funzione ricorsiva:

h(padre) = 1+max(h(figli))
non so cosa sia il diametro ma questa funzione ricorsiva trova l'altezza dell'albero.

BlackAuron

06-01-2010, 15:22

d è la distanza tra due nodi.
min{d(x,y)} è la distanza minima tra due nodi x e y
max{min{d(x,y)}} è il massimo dell'insieme delle distanze minime tra due nodi dell'albero.
Solitamente quello che si cerca è il diametro di un grafo, ma dal momento che un albero altro non è che un grafo non orientato e privo di cicli ... la definizione si può riutilizzare.

Quella funzione ricorsiva lo so pure io che calcola la profondità di un albero, e infatti ho specificato che è da utilizzarsi nel caso in cui il costo degli archi dell'albero sia 1.

In caso contrario ( nessuno vieta che gli archi che compongono l'albero abbiano un costo non unitario), bisogna ricorrere ad altri escamotages.

PS: peso = costo di un arco

Red_Knight

06-01-2010, 15:30

Allora intanto grazie infinite per i vostri post che vi hanno portato via tempo (un giorno sarò abbastanza esperto da rendere il favore al forum, lo prometto) e le mie scuse per l'imprecisione dei miei: allora ovviamente sì, esiste un solo cammino tra due nodi perché per definizione l'albero è un grafo connesso e aciclico. Sorry per la fesseria, è che c'è proprio scritto così (la consegna dev'essere stata mutuata da un esercizio sui grafi generici) e ho copiato.

Allora, per "albero generico" intendo un albero coi rami non pesati (il costo è unitario) e dove ogni nodo può avere un numero qualsiasi di figli. Il diametro che devo trovare - chiedo scusa ancora per l'eventuale uso inappropriato del termine - è la distanza, espressa in numero di archi, tra i due nodi più lontani che si possono trovare nell'albero.

Per esempio, nell'albero seguente

...O........
./.|..\.....
O.O...O...
|....../.\..
O....O...O

il diametro è 4.

BlackAuron

06-01-2010, 19:14

a questo punto, direi che puoi affermare che: i due nodi che andranno a stabilire il diametro sono foglie.
Quindi, detto d(x,y) un algoritmo che torna il costo del cammino minimo tra due nodi, hai che il tuo programma sarà qualcosa del tipo:

pseudocodice:

int m;
for(x in F){
for(y in F){
m = max(m,d(x,y));
}
}
return m;

dove con F ho indicato l'insieme delle foglie dell'albero.

PS: probabilmente quello che ho sopra descritto non è un algoritmo ottimo, visto che è dell'ordine di O(n^2) nel numero n delle foglie dell'albero, ma di certo è il più semplice :)

wingman87

06-01-2010, 20:44

Secondo me il modo migliore è usare una variante della funzione altezza h(r) dove r è la radice dell'albero/sottoalbero
PSEUDOCODICE:
(h, d)diametroRec(r){ //Ritorna due valori, altezza di r e diametro di r
Se r è una foglia: return 0,0
maxD,maxH1,maxH2 //maxD conterrà il massimo diametro tra i sottoalberi figli, maxH1 e maxH2 le due altezze maggiori tra i sotto alberi figli
Richiamo diametroRec sui figli per assegnare le varie variabili
return maxH1+1, maxD>maxH1+maxH2+2 ? maxD : maxH1+maxH2+2;
}

Edit: non ho considerato il caso in cui un nodo abbia un solo figlio ma credo che basti fare le giuste inizializzazioni di maxH1 e maxH2 per correggere

BlackAuron

06-01-2010, 21:27

Quella che hai postato è la seconda idea che mi era venuta in mente... l'unico dubbio che però mi ha fatto propendere per l'altro algoritmo, oltre alla semplicità di scrittura, è che in quel modo ti trovi a fare una serie di ricerche di massimi tra i figli di ogni nodo ( per determinare maxh1 e maxh2) ... ora, son pigro e non voglio controllare, ma non ho la certezza che a livello computazionale la cosa convenga ( quantomeno non se si ha un albero con un fattore di diramazione alto).
Ma ripeto, non ho fatto alcun calcolo pratico ( e in effetti nell'algoritmo che ho scritto c'è da cercare in continuazione cammini minimi... ), quindi non saprei dire in fin dei conti cosa convenga :)

marco.r

06-01-2010, 21:52

BlackAuron

06-01-2010, 22:10

( e in effetti nell'algoritmo che ho scritto c'è da cercare in continuazione cammini minimi... )

Non ho sorvolato :)
mi resta comunque il dubbio che l'altro algoritmo non sia lineare nel tempo, ma piuttosto quadratico quantomeno nel caso pessimo, dal momento che per ogni nodo grossomodo c'è da fare una ricerca su tutti i figli per il massimo...

fero86

06-01-2010, 22:56

d è la distanza tra due nodi. e cos'é la distanza tra due nodi in un albero N-ario?

Allora, per "albero generico" intendo un albero coi rami non pesati (il costo è unitario) e dove ogni nodo può avere un numero qualsiasi di figli. Il diametro che devo trovare - chiedo scusa ancora per l'eventuale uso inappropriato del termine - è la distanza, espressa in numero di archi, tra i due nodi più lontani che si possono trovare nell'albero. ok, adesso é chiaro: dato un albero N-ario (V, E), cioé un grafo connesso aciclico i cui vertici sono gli elementi dell'insieme V e gli archi quelli dell'insieme E, diciamo "cammino" un insieme ordinato di elementi di V tali che per ogni vertice v avente successore succ(v) nel cammino esiste in E un elemento (v, succ(v)). questa definizione non ammette cammini che passano piu volte per gli stessi nodi perché i cammini sono stati definiti come insiemi e non multinsiemi. dato un albero N-ario si vuole trovare la cardinalitá massima dei cammini. giusto?

wingman87

06-01-2010, 23:57

Non ho sorvolato :)
mi resta comunque il dubbio che l'altro algoritmo non sia lineare nel tempo, ma piuttosto quadratico quantomeno nel caso pessimo, dal momento che per ogni nodo grossomodo c'è da fare una ricerca su tutti i figli per il massimo...
No, è sicuramente lineare: è uguale all'algoritmo per ricavare l'altezza (a meno di una costante)

EDIT: mi sono sbagliato, è a meno del coefficiente, non di una costante

Red_Knight

07-01-2010, 02:14

ok, adesso é chiaro: dato un albero N-ario (V, E), cioé un grafo connesso aciclico i cui vertici sono gli elementi dell'insieme V e gli archi quelli dell'insieme E, diciamo "cammino" un insieme ordinato di elementi di V tali che per ogni vertice v avente successore succ(v) nel cammino esiste in E un elemento (v, succ(v)). questa definizione non ammette cammini che passano piu volte per gli stessi nodi perché i cammini sono stati definiti come insiemi e non multinsiemi. dato un albero N-ario si vuole trovare la cardinalitá massima dei cammini. giusto?

Giusto!

Vedo che mi è stata data la soluzione in pseudocodice (grazie!), ma - ehm - non credo di averla capita. :(
Perché devo sfruttare le due altezze maggiori?

BlackAuron

07-01-2010, 11:31

perchè il più lungo cammino passante per un padre sarà uguale alla somma della prima e della seconda maggiore altezza dei figli. Guarda l'esempio che hai dato tu e capirlo è praticamente immediato.

Red_Knight

08-01-2010, 17:40

Scusa, la mia domanda era legata al fatto che il diametro potrebbe essere contenuto in un sottoalbero, ma ho realizzato adesso che la funzione suggeritami restituisce due valori e consente di verificare se il diametro è già stato trovato in un sottoalbero.
Ora però come faccio a far restituire due valori a una funzione in C?

marco.r

08-01-2010, 22:17

Direttamente non puoi.
Hai due alternative. La prima e' quella di ritornare un struttura con due campi, che contengono i due valori che vuoi. La seconda e' di passare due argomenti per puntatore, e modificarli.