多重和の解法のソースを表示

'''【たじゅうわのかいほう (solution of multiple summation)】'''

一般に, 多重和問題


<center>
<math>
\displaystyle{\sum \{g(x_{1}, x_{2}, x_{3}, \ldots , x_{N+1})} 
\displaystyle{\mid (x_{2}, x_{3}, \ldots , x_{N+1}) \in X^{N} \} }
\,</math>
</center>


は次の後向き再帰式で解ける: 

<center>
<math>
\begin{array}{l}
\displaystyle{w_{N+1}(x^{N+1}) = g(x^{N+1}), \quad x^{N+1} \in X^{N+1} } \\
\displaystyle{ w_{n}(x^{n}) = \sum_{y \in X}w_{n+1}(x^{n}, y), } 
\ \ \ \ \displaystyle{x^{n} \in X^{n},~ 1 \le n \le N. }
\end{array}
\,</math>
</center>


ただし,  <math> x^{n} = (x_{1}, x_{2}, \ldots , x_{n}). \,</math>

[[Category:動的・確率・多目的計画|たじゅうわのかいほう]]