1
$\begingroup$

I am reading Dynamic programming using MIT OCW applied mathematics programming here.

An elementary example is given there in 11.1 as shortest delay to reach parking slot from home. The objective function is having following constraint as we move backward as :

$$ s_{n-1} = \begin{cases} s_n+1, & \text{if we choose up and $n$ is even } \\ s_n-1 , & \text{if we choose down and $n$ is odd } \\ s_n , & \text{otherwise} \end{cases} $$

I am not able to understand this constraint and why we are adding/ subtracting 1 while it is even/odd ?

$\endgroup$
1
$\begingroup$

It's just got to do with the indexing and the picture here. Check out Figure 11.1; each column is a stage $n$, starting at $0$ for the far right and $5$ for the far left. The states $s_n$ are counted from the bottom up starting from $1$ going up to $6$, and the value at each state $t_n(s_n)$ is the number inside the node. For example, $t_0(1) = 3$ because $n=0$ is the far right column, and $s_n=1$ is the bottom state in that column, and the bottom right node has the number $3$ in it. Another example, $t_2(5) = 9$.

The transition function tells you what the next state is based on the current state and the decision. The current state, as before, is an integer from $1$ to $6$, and the decision is up or down (which branch you take to go from one column to the next). Note that, in the picture, the even columns are staggered higher, while the odd ones are lower. If you are in an even column and take the upper branch, the state number will go up by one. If you are on an odd column and take the lower branch, the state number will go down by one. However, if you are in an odd column and you take the upper branch, the state number will stay the same, as it will if you are in an even column and take the upper branch.

$\endgroup$
  • $\begingroup$ stage vs stage made me confused . horizontal is stage and vertical is state representation ? $\endgroup$ – optional Jul 31 '18 at 14:36
  • 1
    $\begingroup$ Yes, in this example with the given picture, the horizontal axis represents stage (which step you're on) and the vertical axis represents state (which option you're on for that step). $\endgroup$ – AlexanderJ93 Jul 31 '18 at 14:39
  • 1
    $\begingroup$ Now it is self explanatory for forward induction as well $\endgroup$ – optional Jul 31 '18 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.