Life can only be understood going backwards, but it must be lived going forwards. --- Kierkegaard. 考慮一組變數 $w,x,y,z$ 且我們希望最佳化下列的成本函數 \[ f(w,x) + g(x,y) + h(y,z) \]讀者可已注意到上述的成本函數中有特殊的結構,亦即每一項只有兩個變數。 Backward Dynamic Programming 若我們考慮 $w$ 固定,則上述最佳化問題 \[ \min_{x,y,z} f(w,x) + g(x,y) + h(y,z) \]可以改寫為 分別最佳化的子問題 \[\mathop {\min }\limits_x \left[ {f(w,x) + \mathop {\min }\limits_y \left[ {g(x,y) + \mathop {\min }\limits_z h(y,z)} \right]} \right]\]故我們可以先解最內部的最佳化問題並得到對應的最佳解 $z^*$ 與 最佳解對應的成本值 $h^*$ \[\left\{ \begin{array}{l} \mathop {\min }\limits_z h(y,z): = {h^*}\left( y \right)\\ \arg \mathop {\min }\limits_z h(y,z): = {z^*}\left( y \right) \end{array} \right.\]接著我們求解第二部分的 最佳化的子問題 \[\mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]\]其對應的解 \[\left\{ \begin{array}{l} \mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]: = {g^*}\left( x \right)\\ \arg \mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]: = {y^*}\l
If you can’t solve a problem, then there is an easier problem you can solve: find it. -George Polya