The following is a map where nodes (with capital letters) represent towns and the numbers shown are the distances between two directly connected towns. A traveller, starting from t = 0 at Town 0, can choose to go to one of Towns A,B,C at t = 1, and then one of Towns E,F,G,H at t 2, and one of Towns I, J at t = 3, and finally reaches Town D at t = 4. The traveller would like to find the shortest path from Town ( to Town D along with the corresponding shortest distance he will need to travel. a) Define the value function V(t, x): the shortest distance from Town x to Town D starting at time t where t = 0,1, 2, 3, 4 and x is a possible town associated with t (e.g., when t=1, x is either A or B or C). Derive a relationship between V(t, x) and V(t+1, y) analogous to Bellman's principle of optimality (Theorem 2.1 in Lecture 9). b) Hence, starting from the trivial fact that V(4, D) = 0, derive all the values of V(t, x) recursively in a backward manner including V(0,0). c) Find the shortest path from 0 to D. d) If, half way through, the traveller finds himself deviating from the original optimal path obtained in c), how can he find the shortest path? Explain. E 3 A 4 7 6 3 F 5 I 3 2 4 3 O B D 5 G 2 6 J 5 6 5 5 2 3 H The following is a map where nodes (with capital letters) represent towns and the numbers shown are the distances between two directly connected towns. A traveller, starting from t = 0 at Town 0, can choose to go to one of Towns A,B,C at t = 1, and then one of Towns E,F,G,H at t 2, and one of Towns I, J at t = 3, and finally reaches Town D at t = 4. The traveller would like to find the shortest path from Town ( to Town D along with the corresponding shortest distance he will need to travel. a) Define the value function V(t, x): the shortest distance from Town x to Town D starting at time t where t = 0,1, 2, 3, 4 and x is a possible town associated with t (e.g., when t=1, x is either A or B or C). Derive a relationship between V(t, x) and V(t+1, y) analogous to Bellman's principle of optimality (Theorem 2.1 in Lecture 9). b) Hence, starting from the trivial fact that V(4, D) = 0, derive all the values of V(t, x) recursively in a backward manner including V(0,0). c) Find the shortest path from 0 to D. d) If, half way through, the traveller finds himself deviating from the original optimal path obtained in c), how can he find the shortest path? Explain. E 3 A 4 7 6 3 F 5 I 3 2 4 3 O B D 5 G 2 6 J 5 6 5 5 2 3 H