Estoy jugando con la implementación de un algoritmo de árbol de unión para la propagación de creencias en una red bayesiana. Estoy luchando un poco al triangular el gráfico para que se puedan formar los árboles de unión.Algoritmo de propósito general para triangular un gráfico no dirigido?
Entiendo que encontrar la triangulación óptima es NP-completa, pero ¿puede apuntarme a un algoritmo de propósito general que dé como resultado una triangulación "suficientemente buena" para redes bayesianas relativamente simples?
Este es un ejercicio de aprendizaje (hobby, no deberes), así que no me importa mucho la complejidad del espacio/tiempo, siempre que el algoritmo resulte en un gráfico triangulado dado cualquier gráfico no dirigido. En última instancia, estoy tratando de entender cómo funcionan los algoritmos de inferencia exactos incluso antes de intentar hacer algún tipo de aproximación.
Estoy retocando en Python usando NetworkX, pero cualquier descripción de pseudocódigo de dicho algoritmo usando la terminología típica de cruce de gráficos sería valiosa.
Gracias!
Cuando dice "tamaño de la camarilla (s)", ¿quiere decir las variables que ya se ha conectado entre sí debido a la una eliminación? Es decir. Si un gráfico contiene una camarilla de 5, ¿reconoce su método esto en la primera iteración o trata inicialmente todas las variables como 1 camarilla? Quiero evitar llamar a un método que encuentre camarillas máximas cada vez que necesite calcular C (i). – user