Allzweck-Algorithmus einen ungerichteten Graphen für die Triangulation?

Question

Ich spiele um mit einer Kreuzung Tree-Algorithmus für Belief Propagation auf einem Bayes-Netzwerk zu implementieren. Ich bin mit Triangulation die Grafik ein wenig zu kämpfen, so dass die Verbindungs ??Bäume gebildet werden.

Ich verstehe, dass die optimale Triangulierung der Suche nach NP-vollständig ist, aber können Sie mir zeigen auf einem Allzweck-Algorithmus, dass die Ergebnisse in einem ‚gut genug‘ Triangulation für relativ einfache Bayesian Networks?

Dies ist eine Lernübung (Hobby, keine Hausaufgaben), so dass ich nicht viel über Raum / Zeit-Komplexität ist es egal, solange der Algorithmus führt zu einem triangulierten Graphen jeden ungerichteten Graphen gegeben. Letztlich, ich versuche, wie genau Inferenzalgorithmen Arbeit zu verstehen, bevor ich überhaupt jede Art von Annäherung versuchen zu tun.

Ich bin in Python bastelt NetworkX verwenden, aber jeder Pseudo-Code-Beschreibung eines solchen Algorithmus unter Verwendung typischer Graph Traversal Terminologie wäre wertvoll.

Danke!

Answer 1

Wenn Xi ist eine mögliche Variable (node) dann gelöscht werden,

• S (i) wird die Größe der Clique durch das Löschen dieser Variable
erstellt werden
• C (i) wird die Summe der Größe der Cliquen des Subgraphen von Xi und seinen benachbarten Knoten
gegeben sein

Heuristic:

In jedem Fall wählen Sie ein Variable Xi unter dem Satz von möglichen Variablen, die mit minimal S gelöscht werden (i) / C (i)

Referenz: heuristische Algorithmen für die Triangulation Graphs