algorithme universel pour trianguler un graphe non orienté?

Question

Je joue dans la mise en œuvre d'un algorithme d'arbre de jonction pour la propagation des croyances sur un réseau bayésien. Je me bats un peu avec trianguler le graphique de sorte que les arbres de jonction peuvent être formés.

Je comprends que trouver la triangulation optimale est NP-complet, mais pouvez-vous me pointer vers un algorithme universel qui se traduit par une triangulation « assez bonne » pour les réseaux bayésiens relativement simples?

Ceci est un exercice d'apprentissage (passe-temps, pas les devoirs), donc je ne me soucie pas beaucoup sur la complexité espace / temps tant que les résultats de l'algorithme dans un graphe triangulé donné un graphe non orienté. En fin de compte, je suis en train de comprendre comment l'inférence exacte des algorithmes de travail avant d'essayer même faire toute sorte d'approximation.

Je bricoler en Python à l'aide NetworkX, mais toute la description pseudo-code d'un tel algorithme en utilisant la terminologie graphique typique traversal serait utile.

Merci!

Answer 1

Si Xi est une variable possible (nœud) à supprimer puis,

• S (i) sera la taille de la clique créée par la suppression de cette variable
• C (i) sera la somme de la taille des cliques de la sous-graphe données par Xi et de ses nœuds adjacents

Heuristique:

Dans chaque cas, sélectionner une variable Xi parmi l'ensemble des variables possibles à supprimer avec S minimal (i) / C (i)

Référence: algorithmes heuristiques pour la Triangulation de graphiques