1
$\begingroup$

This is a question regarding dynamic programming.

The document to which I am referring isthis (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$

Here $v_n(s_n)$ is the minimum time spent on and after the $n^{th}$ stage.

Doesn't the "Min" function work for at least two values? How does $\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$ even make sense??

Math1000's user avatar
Math1000
38.3k5 gold badges41 silver badges105 bronze badges
askedJun 19, 2015 at 12:09
$\endgroup$
1
  • $\begingroup$You're generally minimizing over your choice for your next state plus the cost of the optimal path from that state to the end.$\endgroup$CommentedJun 19, 2015 at 13:14

1 Answer1

1
$\begingroup$

I think they meant something like $$v_n(s_n)=\text{Min}_{i\leq n}\{t_i(s_i)+v_{i-1}(s_{i-1})\}$$,or the minimum over all the previous states + cost of next state

Take a look atthis to check the possible dyn. prog. relations.

answeredJun 19, 2015 at 14:04
FisherDisinformation's user avatar
$\endgroup$

You mustlog in to answer this question.