Я играю с реализацией алгоритма дерева соединений для распространения убеждений в байесовской сети. Я немного борюсь с триангуляцией графа, чтобы образовались соединительные деревья.
Я понимаю, что нахождение оптимальной триангуляции является NP-полным, но можете ли вы указать мне алгоритм общего назначения, который приводит к "достаточно хорошей" триангуляции для относительно простых байесовских сетей?
Это учебное упражнение (хобби, а не домашняя работа), поэтому меня не волнует сложность пространства / времени, пока алгоритм приводит к триангулированному графу с учетом любого неориентированного графа. В конечном счете, я пытаюсь понять, как работают алгоритмы точного вывода, прежде чем даже попытаться выполнить какое-либо приближение.
Я работаю в Python, используя NetworkX, но любое псевдокодовое описание такого алгоритма, использующего типичную терминологию обхода графа, было бы полезно.
Спасибо!