Алгоритм общего назначения для триангуляции неориентированного графа?

Question

Я играю с реализацией алгоритма дерева соединений для распространения убеждений в байесовской сети. Я немного борюсь с триангуляцией графа, чтобы можно было сформировать соединительные деревья.

Я понимаю, что нахождение оптимальной триангуляции является NP-полным, но можете ли вы указать мне алгоритм общего назначения, который приводит к "достаточно хорошей" триангуляции для относительно простых байесовских сетей?

Это учебное упражнение (хобби, а не домашнее задание), поэтому меня не волнует сложность пространства / времени, пока алгоритм приводит к триангулированному графу с учетом любого неориентированного графа. В конечном счете, я пытаюсь понять, как работают алгоритмы точного вывода, прежде чем пытаться делать какие-либо приближения.

Я работаю в Python, используя NetworkX, но любое псевдокодовое описание такого алгоритма с использованием типичной терминологии обхода графа будет полезным.

Спасибо!

Answer 1

Если Xi - это возможная переменная (узел), которую нужно удалить,

• S (i) будет размером клики, созданной удалением этой переменной
• C(i) будет суммой размера кликов подграфа, заданного Xi и смежными узлами

Эвристический:

В каждом случае выберите переменную Xi среди множества возможных переменных, которые будут удалены с минимальным S(i)/C(i)

Ссылка: Эвристические алгоритмы триангуляции графов