Dynamic Programming Equations

Given: a constraint network N, variable x with domain D, and value $v\in D$, q(x,v) is the probability that variable x gets value v in a complete solution.

U_d(x) is the breadth-first search tree of depth d around x, q_d(x,v) is the probability that x takes value v in a solution in the network U_d(x), $y_1,\ldots, y_m$ are the neighbors of x, B_d(x,y_i) is the y_i-branch of U_d+1(x), b_d(x,y_i,w) is the probability that y_i takes value w in the network B_d(x,y_i).

$$q_0(x,v) = p(x,v) \mbox{\rm \ \ \ and\ \ \ } b_0(x,y_i,w) = p(y_i,w).$$

$$q_d(x,v) = k_d(x) p(x,v) \cdot \prod_{i=1}^m \sum_{w \vert \mbox{\sf match}(y_i, w, x, v)} b_{d-1}(x, y_i, w),$$

where k_d(x) is the normalization constant.

$$b_d(y_i,x,v) = k_d(y_i,x) p(x,v) \cdot \prod_{j=1..m, j \neq... ..._{w \vert \mbox{\sf match}(y_j, w, x, v)} b_{d-1}(x, y_j, w).}$$