The nodes in each column represent the possible values of a single variable. Each edge is weighted by the output energy of the factor for the corresponding values of its input variables. With this representation, a single path from the start node to the end node represents one possible configuration of all the variables. The sum of the weights along a path is equal to the total energy for the corresponding configuration. Therefore, the inference problem can be reduced to searching for the shortest path in this graph. This can be performed using a dynamic programming method such as the Viterbi algorithm, or the A* algorithm. The cost is proportional to the number of edges (16), which is exponentially smaller than the number of paths in general.
Les nœuds de chaque colonne représentent les valeurs possibles d’une seule variable. Chaque arc est pondéré par l’énergie de sortie du facteur pour les valeurs correspondantes de ses variables d’entrée. Avec cette représentation, un seul chemin du nœud de départ au nœud d’arrivée représente une configuration possible de toutes les variables. La somme des poids le long d’un chemin est égale à l’énergie totale pour la configuration correspondante. Par conséquent, le problème d’inférence peut être réduit à la recherche du plus court chemin dans ce graphe. Ceci peut être réalisé en utilisant une méthode de programmation dynamique telle que l’algorithme de Viterbi ou l’algorithme A*. Le coût est proportionnel au nombre d’arêtes (16) qui est exponentiellement plus petit que le nombre de chemins en général.