Allgemeiner Algorithmus zum Triangulieren eines ungerichteten Graphen?

Question

Ich spiele mit der Implementierung eines Junction-Tree-Algorithmus für die Propagierung von Glauben in einem Bayes-Netzwerk. Ich kämpfe ein wenig mit dem Triangulieren des Graphen, damit die Verzweigungsbäume gebildet werden können.

Ich verstehe, dass das Finden der optimalen Triangulation NP-vollständig ist, aber können Sie mich auf einen Allzweckalgorithmus hinweisen, der zu einer 'gut genug' Triangulation für relativ einfache Bayes'sche Netzwerke führt?

Dies ist eine Lernübung (Hobby, keine Hausaufgabe), daher ist mir die Komplexität von Raum und Zeit egal, solange der Algorithmus in einem ungerichteten Graphen einen triangulierten Graphen ergibt. Letztendlich versuche ich zu verstehen, wie genaue Inferenzalgorithmen funktionieren, bevor ich überhaupt versuche, irgendeine Annäherung durchzuführen.

Ich bin in Python mit NetworkX basteln, aber jede Pseudo-Code-Beschreibung eines solchen Algorithmus mit typischen Graph Traversal Terminologie wäre wertvoll.

Danke!

Answer 1

Wenn Xi eine mögliche variable (Knoten) wird dann gelöscht werden,

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

Heuristic:

jeweils ein Variable Xi unter dem Satz von möglichen Variablen wählen zu de leted mit minimalen S (i)/C (i)

Referenz: Heuristic Algorithms for the Triangulation of Graphs