Lagmental Vicfred

Bellman's Principle Replaces a Global Search by Optimal Suffixes by Vicfred

Last updated: Fri 19 August 2016

tags: mathematics, dynamic programming, semirings, state spaces

An optimal path cannot contain a nonoptimal continuation from a state it reaches. A small computation will anchor the general statement before the abstraction takes over.

Notation

A full dynamic-programming state \(dp[i][s]\) states exactly which prefix \(i\) and mathematical state \(s\) have been processed. The recurrence is a theorem about transitions between these states.

$$ V(s)=\min_{\pi:s\rightsquigarrow T}\operatorname{cost}(\pi) $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ V(s)=\min_{a\in A(s)}\{c(s,a)+V(T(s,a))\} $$

Stress the formula

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \begin{cases}V(t)=0,&t\in T,\\V(s)=\min_{s\to u}(w(s,u)+V(u)),&s\notin T.\end{cases} $$

Interpretation

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad V(s)=\min_{\pi:s\rightsquigarrow T}\operatorname{cost}(\pi),\\[5pt] \mathsf{C}\;&:\quad V(s)=\min_{a\in A(s)}\{c(s,a)+V(T(s,a))\}. \end{aligned} $$

Limit of the argument

State compression is an implementation change, not the definition. Loop order is safe only after the uncompressed dependency graph is understood.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] V(s)=\min_{a\in A(s)}\{c(s,a)+V(T(s,a))\} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Wed 08 April 2015. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.