5

Sto giocando con l'implementazione di un algoritmo di albero di giunzione per la propagazione di credenze su una rete bayesiana. Sto faticando un po 'a triangolare il grafico in modo da formare gli alberi di giunzione.Algoritmo per scopi generali per triangolare un grafo non orientato?

Capisco che trovare la triangolazione ottimale è NP-completo, ma puoi indicarmi un algoritmo di scopo generale che si traduce in una triangolazione "abbastanza buona" per reti Bayesiane relativamente semplici?

Questo è un esercizio di apprendimento (hobby, non compiti a casa), quindi non mi interessa molto della complessità spazio/tempo, purché l'algoritmo si traduca in un grafico triangolare dato alcun grafo non orientato. In definitiva, sto cercando di capire come funzionano esattamente gli algoritmi di inferenza prima ancora di provare a fare qualsiasi tipo di approssimazione.

Sto armeggiando in Python usando NetworkX, ma qualsiasi descrizione di pseudo-codice di un tale algoritmo che utilizza la tipica terminologia trasversale del grafico sarebbe preziosa.

Grazie!

risposta

3

Se Xi è un possibile variabile (nodo) da eliminare poi,

  • S (i) sarà la dimensione della cricca creato cancellando questa variabile
  • C (i) sarà la somma della dimensione delle cricche del sottografo proposta dal Xi e suoi nodi adiacenti

euristica:

In ogni caso selezionare una variabile Xi tra l'insieme di possibili variabili da de leted con S minima (i)/C (i)

Riferimento: Heuristic Algorithms for the Triangulation of Graphs

+1

Quando si dice "dimensione della cricca (s)", vuoi dire le variabili che hai già collegati tra loro a causa di una cancellazione? Cioè se un grafico contiene una 5-clique, il tuo metodo lo riconosce alla prima iterazione o inizialmente considera tutte le variabili come 1-clique? Voglio evitare di chiamare un metodo che trova cricche massimali ogni volta che ho bisogno di calcolare C (i). – user

Problemi correlati