Algoritmi efficienti per l’enumerazione di alberi con...

Roberto AringhieriDipartimento di Tecnologie dell’Informazione

http://www.dti.unimi.it/~aringhieri

Università degli Studi di Milano

Algoritmi efficienti perl’enumerazione di alberi

con grado limitato

Roberto Aringhieri - Algoritmi per l'Enumerazione di alberi con grado limitato 2

Outline

Introduzione:• definizione del problema• un pò di storia

Algoritmi per la codifica di alberi:• N-tuple code per alberi radicati• N-tuple code per alberi non radicati• Centered N-tuple code

Algoritmi di Enumerazione:• one-to-one enumeration• constructive enumeration

Conclusioni


Alberi con grado limitato

Dato un albero T=(N,A) ed un nodo u∈A,

definiamo il grado d(u) di un nodo u come

Quindi, dato K intero, un albero con gradolimitato TK=(N,A) è un albero tale che


Definizione del problema

Due problemi collegati!

(Counting problem)

Dato n = |N| ed un intero K, quanti sono glialberi TK(N,A) diversi?

(Enumeration problem)

Dato n = |N| ed un intero K, quali sono glialberi TK(N,A) diversi?


Dimensione del problema per K=4

6171056142814828419

366319

60523

24894

10359

4347

1858

802

355

Alberi diversi

29

27

26

25

24

23

22

21

n

159050712120

24021580318

9383941217

3679758816

1449024515

573158014

227865813

91072612

Alberi diversin


Un pò di storia

Il problema di contare e/o enumerare quantisono gli alberi affonda le sue radici agli inizi del1800 quando i chimici dell’epoca si posero ilproblema di classificare le molecole di alcano

Alcuni lavori:

• Berzelius, 1830, Ann. Phys. Chem.definizione del problema

• Jordan, 1869teorema per la composizione di alberi

• Cayley, 1875, Ber. Dtsch. Chem. Ges.enumerazione sino a n = 13


Codifica di alberi/1

Per progettare algoritmi di enumerazioneefficienti occorre poter manipolare gli alberiagevolmente.

Problemi:

• memoria: RAM e spazio disco possono risultareinsufficienti

• database: è poco agevole memorizzare lastruttura dati che rappresenta l’albero

Occorre pensare ad una codifica compatta


Codifica di alberi/2

Buone caratteristiche di un codice (Read 1972):

• lineare rispetto la dimensione dell’albero

• di definizione univoca

• ben definito

• facilmente comprensibile

• codificabile e decodificabile in modo efficiente

Codici di tipo N-tuple


Ordine lessicografico

Una sequenza di interi

C = c … clè lessicograficamente più grande di

C’ = c’ … c’l’se:

esiste un intero j (1�j� min { l, l’ }) t.c.

ci=c’i per i=1,…,j-1 e cj>c’joppure

l>l’ e ci = c’i per ogni i=1,…,l’


Codice N-tuple/1

N-tuple su albero di radice r è così definito:

• una foglia ha codice 0

• sia g il numero di nodi (v, v, … , vg) adiacentialla radice r;

• si “cancella” r ottenendo g sottoalberi per i qualisi calcola il relativo codice N-tuple;

• si compongono i codici dei g sottoalberi in mododa ottenere una sequenza S massima dal puntodi vista lessicografico

• il codice C è dato dalla composizione di g e S


Esempio

r

4 200 10 0 0

20010 0

0

0

0 0

Grafo con 8 nodi


Codice N-tuple/2

Caso di albero non radicato:

• sia M l’insieme dei nodi di grado massimo

• si calcola il codice Cu per ogni nodo u∈M

• il codice dell’albero C è dato da

dove il massimo è da intendersi in sensolessicografico


Esempio

4 200 131000 0 0

4 1320000 10 0 0

Grafo con 12 nodi

4 200 131000 0 0 > 4 1320000 10 0 0


Codice Centered N-tuple

Il codice Centered N-tuple (CN-tuple) per alberinon radicati è una particolare specifica delcodice N-tuple

Anziché calcolare il codice N-tuple per ogninodo di grado massimo, esso viene calcolatosolo sul nodo al “centro” dell’albero

Occorre dare quindi una definizione di centro diun albero


Centro di un albero

La definizione di centro di un albero T è data inmodo ricorsivo:

• si eliminano le foglie (e l’arco incidente in esso)da T ottenendo un albero T ’ più piccolo;

• se T ’ contiene un nodo, oppure due nodiadiacenti, questo è il centro;

• altrimenti, si ripete il procedimento

Nel caso di centro composto da due nodi, sicalcola il codice N-tuple su entrambi i nodi e sisceglie il massimo


Esempio/1

Nodi di grado massimo

centro 2 320000 31000


Esempio/2

due nodi centrali

2 320000 3000

4 200 13000 0 0


Complessità/1

N-tuple: O(n)

CN-tuple: O(n log n)Su una RAM machine:

• N-tuple e CN-tuple: O(n)• Random Access Machine: modello teorico di

computazione con parola di memoria illimitata,memoria illimitata, operazioni elementari in O(1)

Risultati tratti da:• P. Hansen et al.,

Coding Chemical Trees with the Centered N-tupleCode, 34:782-790, 1994.


Complessità/2

• Il calcolo dei codici di tipo N-tuple richiede lavisita dell’albero ed un certo numero di confrontiper l’ordine lessicografico

• Complessità � O(n) × O(num. confronti)

• Il numero dei confronti è limitato superiormentedalla lunghezza del cammino radice-foglia

• La scelta del nodo centrale permette di ottenereun albero quasi bilanciato e quindi avere unalunghezza cammino-foglia pari a O(log n)


Esempio

CN-tupleN-tuple


Algoritmi di enumerazione

Nel seguito vedremo due algoritmi dienumerazione:

one-to-one enumeration

enumerazione degli alberi con n nodi aggiungendoun nodo in tutti i possibili modi a ciascuno deglialberi con n-1 nodi

constructive enumeration

costruzione di alberi con n nodi per composizione diun certo numero alberi più piccoli


one-to-one enumeration

Metodo intuitivo

Dato T=(N,A) albero di origine con n- nodi e

posto:

aggiungendo un nodo a T possiamo ottenere|N+| alberi di n nodi


Univocità dell’enumerazione/1

Gli |N+| alberi sono tutti diversi?

Esempio

A

B C

D

A = B = C ≠ D codici?

3000

31000

31000 31000

40000



Gli |N+| alberi sono tutti diversi?

Esempio3000

2100

31000



Gli esempi illustrano due tipi di enumerazionenon univoca:

• stessa enumerazione dallo stesso albero3000 può generare 3 volte 31000

• stessa enumerazione da alberi diversi3000 e 2100 generano entrambi 31000



Possibili soluzioni:

• liste di codici/alberi già generati e scansione(algoritmo di Trinajstic et al. � TNKMS)

• hashing

• Reverse Search (RS) + Symmetry Detection (SD)


Notazione

• To: albero di origine di una enumerazione

• Td: albero generato da To

• Tree Generation Function

• Multi-insiemi:


Reverse Search

Introdotta per l’enumerazione dei vertici di unpoliedro

Enumeration Rule 1:

Un albero Td = GT(To) è accettato come valido se e

solo se To è il massimo lessicografico in O(Td)

La regola permette di evitare l’enumerazione dialberi identici da alberi diversi


Applicazione Enumeration Rule 1

3000

2100

31000

3000>2100 allora accetto 31000 solo se è generato da 3000


Simmetrie: un esempio

Gli alberigenerati dasottoalberi

identicisono

identici

Tutti hannoinfatti

codice31000


Simmetrie in un albero

L’idea si basa su considerazioni topologiche

• individuare almeno due sottoalberi identici in To

Sia To con radice r e due sottoalberi S e Sradicati rispettivamente in v e w. Posto lr(v) la

distanza tra r e v in numero di archi, diciamo

che:

• S e S sono simmetrici se e solo se i due codicicoincidono e lr(v) = lr(w)


Symmetry Detection

Enumeration Rule 2:

Dati Si sottoalberi simmetrici di To con i = 1,…,q e

2�q�4, gli alberi generati da To sono solo quelli

ottenuti aggiungendo nodi in Sq.


Applicazione Enumeration Rule 2

S=0S=0

S=0


Albero dei codici

Per implementare efficientemente le due regoledi enumerazione, introduciamo una strutturadati detta albero dei codici o CTree

CTree è un albero radicato nel nodo dove vienecalcolato il codice e composto di livelli tali che:

• al livello 0 abbiamo l’intero codice

• al livello i, i codici dei sottoalberi a distanza i da r


Esempio

3 21010 10 0

21010 10 0

10 10 0

00

Livelli

0

1

2

3


CTree per calcolare nuovo codice

CTree è utile per calcolare il codice di Td :

• aggiunta di una foglia a To significa aggiungereuna foglia con codice 0 in CTree e modificare ilcodice del relativo sottoalbero

• ordinamento: il codice modificato assieme aicodici “fratelli” deve essere riordinato in modolessicografico

• composizione: se l’ordine viene modificato, sidetermina un nuovo codice al livello superiore equindi il procedimento viene reiterato

• il procedimento termina al livello 0

Analogamente posso calcolare To da Td


Esempio3 21010 10 0

21010 10 0

10 200 0

00 0

3 21010 10 0

21010 10 0

10200 0

0 00

3 21010 10 0

220010 10 0

10200 0

0 00Passo 1:

aggiunta nodo ecalcolo codicesottoalbero

Passo 2:

ordinamentolessicografico

Passo 3:

composizionee stop


Generazione di D(To)

Passi:

• genero CTree di To• eseguo una visita BFS del CTree:

– trovare una simmetria corrisponde a trovare due nodifratelli con lo stesso codice

• ad ogni passo della BFS:– se il nodo u non è simmetrico e d(u)<K, genero Td e

se soddisfa l’enumeration rule 1 viene memorizzato inD(To) altrimenti viene scartato

– vengono messi in coda per la visita i codici figlio delnodo

• al termine della visita si restituisce D(To)


procedure GenSetD


Algoritmo complessivo

Al passo i-esimo (i = 3, … , n):

• estraggo un albero To con i-1 nodi

• applico To a GenSetD ottenendo D(To)• aggiungo gli alberi in D(To) all’insieme degli

alberi con i nodi ed aggiorno il counter deglialberi

• il passo termina quando ho estratto tutti gli albericon i-1 nodi

Inizializzazione:

• insieme alberi con 2 nodi � {10}


procedure OneToOneEnumeration


constructive enumeration

Idea:

posso ottenere un albero con n nodi unendo 1nodo ed un certo numero di sottoalberi i cuinodi siano complessivamente pari a n-1

Regole per determinare il numero di sottoalberie la loro cardinalità si derivano dal teorema diJordan che descrive come comporre alberiradicati per ottenere alberi non radicati


Teorema di Jordan/1


Teorema di Jordan/2


Esempio

Generazione degli alberi con 10 nodi:

• composizione di un nodo con al più 3 o 4sottoalberi tali che il numero di nodi complessivosia 9

• composizione di 2 sottoalberi con 5 nodi

Osservazione:

• sottoalberi radicati diversi ma di ugualecardinalità generano alberi diversi


Idea di base dell’algoritmo

Nel caso del centroide, la scelta dellacardinalità dei sottoalberi corrisponde a trovare3 o 4 numeri la cui somma sia pari a n-1

Quindi l’enumerazione può essere impostatanel seguente modo:

• determino composizione dei numeri per otteneren-1

• combino in tutti i modi possibili gli alberi dicardinalità corrispondente alla sequenza dinumeri del passo precedente


Confronto tra algoritmi

Confrontiamo 4 algoritmi:

• TNKMS:one-to-one enumeration con lista, N-tuple

• HPVK:one-to-one enumeration con RS e SD, N-tuple

• AHM:one-to-one enumeration con RS e SD, CN-tuple

• KP:constructive enumeration, CN-tuple

Siano Kn e Sn rispettivamente le cardinalità degli insiemi

di alberi radicati e degli alberi non radicati con n nodi


Complessità

Confronto tra un ciclo dell’algoritmo

KP

AHM

HPVK

???TNKMS


Liste vs. RS e SD

tempi in secondi


Running Time


Osservazioni/1

TNKMS peggiore di tutti

AHM e HPVK comparabili

KP di gran lunga il migliore di tutti

• non perde tempo nella verifica delle enumerationrules (enumerazione univoca garantita dalteorema di Jordan)

• per generare 366319 alberi con 20 nodi, KPgenera 879 alberi radicati mentre AHM e HPVKgenerano 251731 alberi


Osservazioni/2

AHM e HPVK generano di fatto tutte le famigliedi alberi sino a n nodi

KP genera solo quella con n nodi

Confronto tempi di calcolo:

• dalla tabella dei tempi si osserva che anchesommando l’intera colonna dei tempi KP (come segenerasse tutte le famiglie di alberi), KP rimanepiù efficiente di AHM e HPVK


Conclusioni

• Applicazione di semplici regole di enumerazionegarantiscono l’univocità dell’enumerazione

• one-to-one enumeration non efficiente quanto laconstructive enumeration

• Algoritmi estendibili (KP con più difficoltà) a casipiù generali

• Open problem: one-to-one enumeration conhashing


Bibliografia

• P. Hansen et al.,Coding Chemical Trees with the Centered N-tupleCode, J. Chem. Inf. Comput. Sci., 34:782-790,1994

• R. Aringhieri, P. Hansen, F. Malucelli,Chemical trees enumeration algorithms, 4OR,1(1): , 2003.

• R. Aringhieri, P. Hansen, F. Malucelli,A Linear Algorithm for the Hyper-Wiener Index ofChemical Trees, J. Chem. Inf. Comput. Sci.,41, 958-963, 2001.

FINE

Date post:	19-Feb-2019
Category:	Documents
Upload:	dotuyen
View:	216 times
Download:	0 times

Algoritmi efficienti per l’enumerazione di alberi con...

Documents