[C] Alberi n-ari: quale implementazione?

[Red_Knight]

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 ) 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]

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]

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]

Originariamente inviato da Red_Knight

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

in che senso non mantiene i legami di parentela?

[Red_Knight]

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]

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]

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]

Originariamente inviato da Red_Knight

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]

Originariamente inviato da Red_Knight

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]

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]

Originariamente inviato da Red_Knight

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]

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]

Originariamente inviato da BlackAuron

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?

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]

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]

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]

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]

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]

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]

Originariamente inviato da BlackAuron

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

Nell'algoritmo precedente hai sorvolato sull'implementazione di d(x,y), e non e' cosa da poco dato che e' la parte piu' rilevante del problema. Complessivamente la soluzione proposta da wingman87 e' sia piu' semplice che molto piu' performante (lineare sul numero di elementi dell'albero).

[BlackAuron]

Originariamente inviato da BlackAuron

( 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...