1
$\begingroup$

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem? I need a clear explanation.

enter image description here

enter image description here

$\endgroup$
1
  • $\begingroup$ Can you please tell us where you took this image from? $\endgroup$
    – nbro
    Mar 15 at 14:43

2 Answers 2

2
$\begingroup$

Like it's explained in the image's caption, DP techniques are based on the idea that you can reuse the solution to subproblems, so it assumes that you can break down the original problem into subproblems and that some subproblems overlap.

So, in your example, you can get to $B$ from $C$ and $A$. Similarly, you can get to $E$ from $C$ and $D$. Once you know the shortest path from $B$ to $Y$, you don't have to recalculate it. The same applies for $E$. So, to be clearer, the shortest path to $C$ and $A$ share a common subproblem because they are both connected to $B$. The same applies to the other example.

Now, if you look at your example, there are 10 segments, so you don't go through a segment more than once. If you start from $Y$, you can compute the solution in a bottom-up approach (see also the top-down approach in DP), and cache the results to any subproblem, so you don't have to re-evaluate anything.

In the case of exhaustive search, you basically try every possible combination and you don't cache anything, so you may revisit a segment more than once. For example, you will visit the segment from $B$ to $Y$ twice because there are 2 paths that have that segment, i.e. $X \rightarrow A \rightarrow B \rightarrow Y$ and $X \rightarrow C \rightarrow B \rightarrow Y$. You also visit the segment $X \rightarrow C$ several times because several paths have it. Try to enumerate all possible paths and then count all segments (even if repeated) - they should be 14 (I've just counted them, but you can count them yourself too)

$\endgroup$
2
$\begingroup$

Exhaustive search is just trial and error for the specified problem which has a fixed start node X and a fixed end node Y, thus every possible travel route from X to Y has to be evaluated independently which requires 14 segment evaluations of their respective reward (i.e., the negative of cost-to-go length for shortest path problem) if you count the total 5 possible ways from X to Y in your directed graph.

On the other hand, if you use model-based RL there're only 7 states as nodes and obviously its MDP's state and reward transitions are all deterministic with at most 3 actions at each state and only one action at some of the states. So by using backward dynamic programing's (DP) simplest one-sweep value iteration for this shortest path problem starting from the terminal node, the problem is decomposed into smaller subproblems represented by individual states. In many cases such as shortest path here, states closer to the terminal state have fewer successor states to consider, reducing the computational complexity and iterations to be able to directly compute optimal values within one iteration here instead of the generic algo's intermediate estimates with many iterations as mentioned by my answer to your recent post.

And since you've already known the one-line max operator algo for value iteration derived from Bellman optimality equation (not Bellman equation) in your recent post, it's easy to check for yourself here the optimal values for the 3 states closest to terminal state Y are $v_*(B)=-2, v_*(E)=-2, v_*(C)=-1$ assuming the terminal optimal value $v_*(Y)=0$, and you only need 5 segment evaluations to arrive at these 3 optimal values (note to calculate state C's optimal value we can reuse optimal values of B & E reducing the segment evaluation count essentially). Then similarly you just need another 5 segment evaluations to get the remaining 3 states' optimal values. Then you can extract shortest path from start state X by following the action with optimal value stored already in the above described step-by-step backward DP.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .