Rete a connessione multipla
Una rete a connessione multipla è composta da nodi con più di una connessione. Questa tipologia di rete aumenta la complessità computazionale dell'algoritmo poiché si creano diverse combinazioni di percorso.
Esempio di rete con connessioni multiple
Il seguente diagramma è composto da quattro nodi ( A, B, C, D ). Dal nodo A si diramano due cammini ( path ), uno verso il nodo B e l'altro verso il nodo C. Si tratta di due cammini alternativi poiché entrambi conducono verso il nodo finale D ( obiettivo ).
Per giungere all'obiettivo finale l'algoritmo può scegliere tra il percorso A-B-D e A-C-D. In questo caso, sono entrambi ottimali in quanto il numero dei passi ( step ) è uguale e il costo del passo è identico in tutta la rete.
La complessità computazionale delle reti
La complessità spaziale e temporale della rete è determinata dal numero dei nodi, dal numero degli elementi ossia dei valori che ciascuna variabile ( nodo ) può assumere e dalla combinazione dei percorsi possibili.
Nell'esempio precedente sono presenti due combinazioni di percorso su quattro nodi ( n=4 ), ogni nodo è identificato da una variabile binaria ( A, B, C, D ) e può assumere soltanto due valori ( zero o uno ). In questo caso, la complessità computazionale è pari a O(2 n2).
Le reti a connessione multipla possono celare situazioni peggiori, in cui la complessità cresce in modo esponenziale con il numero dei nodi ( variabili ). La complessità della situazione può diventare O(nn) ossia NP-difficile.
Nel peggiore dei casi l'algoritmo non potrà mai giungere alla soluzione ottimale, perché il processo diventa troppo lungo ( complessità temporale ) oppure richiede un'enorme quantità dello spazio di memoria hardware per svolgere i calcoli ( complessità spaziale ).
Per questa ragione le reti a connessione multipla non sono adatte alla risoluzione dei processi di inferenza a enumerazione completa sulle reti bayesiane. La complessità computazionale
La tecnica del clustering per semplificare la rete
Per ridurre la complessità computazionale di una rete a connessione multipla, è possibile utilizzare la tecnica del raggruppamento dei nodi ( clustering ). In alcuni casi è possibile accorpare nodi differenti in un unico nodo cluster.
Nel migliore dei casi la tecnica del clustering potrebbe anche trasformare una rete a connessione multipla in una rete a connessione singola ( polialbero ).
I due nodi sono stati sostituiti da un unico nodo-cluster associato a una tabella CPT composta dalle possibili combinazioni delle due variabili. Dopo l'accorpamento la rete assume la forma di un polialbero in quanto i nodi hanno tutti al massimo una connessione singola.
