Constraints in Dynamic programming

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

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 = begincases
s_n+1, & textif we choose up and $n$ is even \
s_n-1 , & textif we choose down and $n$ is odd \
s_n , & textotherwise
endcases
$$

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

optimization dynamic-programming

share|cite|improve this question

edited Jul 31 at 12:32

David M.

1,287318

asked Jul 31 at 4:59

optional

1125

add a comment | 

up vote
1
down vote

favorite

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 = begincases
s_n+1, & textif we choose up and $n$ is even \
s_n-1 , & textif we choose down and $n$ is odd \
s_n , & textotherwise
endcases
$$

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

optimization dynamic-programming

share|cite|improve this question

edited Jul 31 at 12:32

David M.

1,287318

asked Jul 31 at 4:59

optional

1125

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

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 = begincases
s_n+1, & textif we choose up and $n$ is even \
s_n-1 , & textif we choose down and $n$ is odd \
s_n , & textotherwise
endcases
$$

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

optimization dynamic-programming

share|cite|improve this question

edited Jul 31 at 12:32

David M.

1,287318

asked Jul 31 at 4:59

optional

1125

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 = begincases
s_n+1, & textif we choose up and $n$ is even \
s_n-1 , & textif we choose down and $n$ is odd \
s_n , & textotherwise
endcases
$$

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

optimization dynamic-programming

share|cite|improve this question

edited Jul 31 at 12:32

David M.

1,287318

asked Jul 31 at 4:59

optional

1125

share|cite|improve this question

share|cite|improve this question

edited Jul 31 at 12:32

David M.

1,287318

edited Jul 31 at 12:32

David M.

1,287318

edited Jul 31 at 12:32

David M.

1,287318

1,287318

asked Jul 31 at 4:59

optional

1125

asked Jul 31 at 4:59

optional

1125

asked Jul 31 at 4:59

optional

1125

1125

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote



accepted

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.

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

• 
  
  
  

  
  

  
  
  
  
  
  

  
  stage vs stage made me confused . horizontal is stage and vertical is state representation ?
  – optional
  Jul 31 at 14:36
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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).
  – AlexanderJ93
  Jul 31 at 14:39
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Now it is self explanatory for forward induction as well
  – optional
  Jul 31 at 14:40
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867675%2fconstraints-in-dynamic-programming%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

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.

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

• 
  
  
  

  
  

  
  
  
  
  
  

  
  stage vs stage made me confused . horizontal is stage and vertical is state representation ?
  – optional
  Jul 31 at 14:36
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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).
  – AlexanderJ93
  Jul 31 at 14:39
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Now it is self explanatory for forward induction as well
  – optional
  Jul 31 at 14:40
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

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.

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

• 
  
  
  

  
  

  
  
  
  
  
  

  
  stage vs stage made me confused . horizontal is stage and vertical is state representation ?
  – optional
  Jul 31 at 14:36
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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).
  – AlexanderJ93
  Jul 31 at 14:39
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Now it is self explanatory for forward induction as well
  – optional
  Jul 31 at 14:40
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

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.

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

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.

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

share|cite|improve this answer

share|cite|improve this answer

answered Jul 31 at 14:04

AlexanderJ93

4,052421

answered Jul 31 at 14:04

AlexanderJ93

4,052421

answered Jul 31 at 14:04

AlexanderJ93

4,052421

4,052421

• 
  
  
  

  
  

  
  
  
  
  
  

  
  stage vs stage made me confused . horizontal is stage and vertical is state representation ?
  – optional
  Jul 31 at 14:36
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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).
  – AlexanderJ93
  Jul 31 at 14:39
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Now it is self explanatory for forward induction as well
  – optional
  Jul 31 at 14:40
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  stage vs stage made me confused . horizontal is stage and vertical is state representation ?
  – optional
  Jul 31 at 14:36
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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).
  – AlexanderJ93
  Jul 31 at 14:39
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Now it is self explanatory for forward induction as well
  – optional
  Jul 31 at 14:40
  

  
  
  
  

stage vs stage made me confused . horizontal is stage and vertical is state representation ?
– optional
Jul 31 at 14:36

stage vs stage made me confused . horizontal is stage and vertical is state representation ?
– optional
Jul 31 at 14:36

1

1

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).
– AlexanderJ93
Jul 31 at 14:39

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).
– AlexanderJ93
Jul 31 at 14:39

1

1

Now it is self explanatory for forward induction as well
– optional
Jul 31 at 14:40

Now it is self explanatory for forward induction as well
– optional
Jul 31 at 14:40

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867675%2fconstraints-in-dynamic-programming%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email