Polialberi

I polialberi sono una tipologia di rete logica in cui i nodi sono connessi tra loro tramite un solo collegamento ( link ) al massimo. Sono anche conosciuti come alberi singolarmente connessi. Dati due nodi qualsiasi della rete, tra questi c'è al massimo un solo cammino ( path ) non orientato.

Esempio di polialbero

Nel seguente esempio di polialbero il nodo A è collegato al nodo B con un solo cammino. Allo stesso modo, il nodo B è collegato al nodo C con un solo cammino.

Qual è il vantaggio dei polialberi?

Nel calcolo computazionale i polialberi hanno una complessità lineare. La complessità spaziale e temporale del calcolo cresce in modo lineare con la dimensione della rete, ossia con il numero dei nodi e con il range di valori che possono assumere le variabili nei nodi ( elementi delle tabelle ).

Nell'esempio precedente la rete è composta da tre nodi ( n=3 ) ognuno dei quali può assumere due valori ( 0 oppure 1 ). Si tratta di variabili binarie. La complessità della rete è pari a O(n²).

Introducendo un nodo aggiuntivo (D) all'albero la complessità aumenta in modo lineare, diventando O((n+1)²), poiché il nodo aggiuntivo è ancora una volta una variabile binaria ed è singolarmente connesso con un altro nodo della rete.

Per questa loro caratteristica i polialberi sono particolarmente utili nei processi inferenziali con enumerazione esatta.