Dynamic Programming

**RoyalFlush** · May 12th 2010, 05:36 AM

A person needs to drive between two cities - Townsville and Villagevile. These cities are joined by a network of roads and towns where the possible paths and distance between towns are attached below.

Along the way, the person will need to stop for fuel and food.
Due to traffic, the car travels at an average speed of 60km\hr. The driver has just finished eating before setting off and can go at most 4 hours between meals - end of one meal to start of the next. The driver will eat with friends on arrival in 'Villagevile' at no cost. The car uses 10 litres per 100km and can safely go at most 400km on a tank. Whenever the driver stops to refuel, he completely fills the tank. The tank is full when leaving Townsville. When the car arrives at Villageville iw will need to be refulled using the fuel cost in Villageville.

What is the cheapest path for the driver?

Other information:

Location MealCost FuelCost/litre
A $76.00 $1.68
B $94.00 $1.25
C $68.00 $1.50
D $75.00 $1.87
E $64.00 $1.34
F $64.00 $1.75
G $71.00 $1.41
H $80.00 $1.64
I $88.00 $1.60
Villagevile $1.28

**Dougy** · May 12th 2010, 12:12 PM

You have no choice that doing an algorithm that tries the 9! different path (all the possible orders of the cities visited) and calculate for each path the cost for all different ways that he can eat, refuel, and so on, under certain condition that you can put in your program ,he has to eat at least once every 4 hours(anoying dude by the way) and refuel before he does 400km, ....So calculate the cost of all paths and all different ways allowed that he can do them correctly (food+gaz) and then simply keep at the end the cheapest one. If you manage to find an algorithm fatser than an exponential one like this one, let us know because then you have solve the N vs NP problem and that's worth 1 million dollars!

PS: I would be carefull not to forget he still has to finish filling this tank at the arrival, that could change the actual cheapest path if you forget that!

**undefined** · May 12th 2010, 07:13 PM

Dynamic programming (DP) is useful for when we have multiple ways to get the same intermediate path, and then we can lump them all together under a state corresponding to that path. Takes some getting used to but offers vast improvements over brute force in many cases. But using DP in this case does not constitute a solution to the million dollar P/NP problem!

It would take me a decent chunk of time and effort to code a DP solution to your problem. Ideally if it were me, I would also want to try out a brute force to verify the results of the DP, which would take additional time, assuming a brute force is fast enough to run in reasonable time (I haven't looked too closely at the numbers).

Wikipedia has a decent article on DP. It did take me quite a while to understand the example of balanced 0-1 matrices, but it is a very good example. If you can understand that example you will have a decent idea of how it works, and with further experience you will begin to feel comfortable with it.

If you are struggling, I should be able to devote some time to it. Just post a reply.

**undefined** · May 14th 2010, 12:53 AM

In the end it was decided that dynamic programming is not appropriate for this problem. I thought it was possible to choose any path, from a to b to c to d, etc. if desired, but there are only 17 paths with three intermediate stops each, and this is well within range of brute force. Here is a backtracking solution, for anyone who's interested.

Code:

import java.util.HashMap;
import java.util.Iterator;

public class TownsvillePaths17 {
    static final int A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9;
    
    static int[] dists1 = {105, 175, 175, 135};
    static int[] dists2 = {140, 120, 175, 135};
    static int[] dists3 = {105, 175, 170, 110};
    static int[] dists4 = {140, 145, 95, 165};
    static int[] dists5 = {140, 120, 115, 165};
    static int[] dists6 = {140, 145, 145, 110};
    static int[] dists7 = {95, 130, 175, 135};
    static int[] dists8 = {105, 160, 95, 165};
    static int[] dists9 = {105, 160, 145, 110};
    static int[] dists10 = {95, 130, 170, 110};
    static int[] dists11 = {140, 145, 80, 135};
    static int[] dists12 = {105, 85, 175, 135};
    static int[] dists13 = {105, 160, 80, 135};
    static int[] dists14 = {105, 85, 115, 165};
    static int[] dists15 = {95, 110, 95, 165};
    static int[] dists16 = {95, 110, 145, 110};
    static int[] dists17 = {95, 110, 80, 135};

    static int[][] dists = {dists1, dists2, dists3, dists4, dists5, dists6,
            dists7, dists8, dists9, dists10, dists11, dists12, dists13,
            dists14, dists15, dists16, dists17};

    static int[] towns1 = {B, F, H};
    static int[] towns2 = {A, D, H};
    static int[] towns3 = {B, F, I};
    static int[] towns4 = {A, E, G};
    static int[] towns5 = {A, D, G};
    static int[] towns6 = {A, E, I};
    static int[] towns7 = {C, F, H};
    static int[] towns8 = {B, E, G};
    static int[] towns9 = {B, E, I};
    static int[] towns10 = {C, F, I};
    static int[] towns11 = {A, E, H};
    static int[] towns12 = {B, D, H};
    static int[] towns13 = {B, E, H};
    static int[] towns14 = {B, D, G};
    static int[] towns15 = {C, E, G};
    static int[] towns16 = {C, E, I};
    static int[] towns17 = {C, E, H};

    static int[][] towns = {towns1, towns2, towns3, towns4, towns5, towns6,
            towns7, towns8, towns9, towns10, towns11, towns12, towns13,
            towns14, towns15, towns16, towns17};
    
    static int[] mealCosts = {76, 94, 68, 75, 64, 64, 71, 80, 88}; // dollars
    static int[] gasCosts = {168, 125, 150, 187, 134, 175, 141, 164, 160, 128}; // cents
    
    static int minCost = Integer.MAX_VALUE;
    
    static HashMap<String, Integer> candPaths = new HashMap<String, Integer>();
    
    public static void init() {
        for (int i = 0; i < mealCosts.length; i++)
            mealCosts[i] *= 1000;
    }
    
    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        init();
        for (int i = 0; i < 17; i++)
            backtrack(i, 0, 0, 400, 0, "");
        Iterator<String> iter = candPaths.keySet().iterator();
        System.out.println("The minimum cost is (unrounded) $" + minCost/1000.0);
        while (iter.hasNext()) {
            String currkey = iter.next();
            if (candPaths.get(currkey) == minCost)
                System.out.println(currkey + " is such a path.");
        }
        System.out.println("in " + (System.currentTimeMillis()-time)/1000.0 + " s");
    }
    
    // to keep everything in integers, spent is given in tenths of a cent!
    // and gasleft is given in tenths of a litre
    // elapsed means time elapsed since last meal
    public static void backtrack(int pathnum, int ind, int spent, int gasleft, int elapsed,
            String pathkey) {
        if (gasleft < 0) return;
        if (elapsed > 360) return;
        if (ind == 4) {
            int fillamount = 400 - gasleft;
            spent += fillamount * gasCosts[J];
            if (spent <= minCost) {
                minCost = spent;
                candPaths.put(pathkey.substring(0, pathkey.length()-2), spent);
            }
            return;
        }
        if (spent > minCost) return;
        if (ind == 0) pathkey += Integer.toString(pathnum+1) + ": ";
        int dist = dists[pathnum][ind];
        
        // go on without stopping
        backtrack(pathnum, ind+1, spent, gasleft-dist, elapsed+dist, pathkey +
                Integer.toString(ind+1) + ", ");
        
        if (ind > 0) {
            int town = towns[pathnum][ind-1];
            int fillamount = 400 - gasleft;
            int gascost = fillamount * gasCosts[town];
            int mealcost = mealCosts[town];
            // stop just for gas
            backtrack(pathnum, ind+1, spent+gascost, 400-dist, elapsed+dist, pathkey +
                    Integer.toString(ind+1) + "G, ");
            // stop just to eat
            backtrack(pathnum, ind+1, spent+mealcost, gasleft-dist, dist, pathkey +
                    Integer.toString(ind+1) + "F, ");
            // stop to get gas and eat
            backtrack(pathnum, ind+1, spent+mealcost+gascost, 400-dist, dist, pathkey +
                    Integer.toString(ind+1) + "GF, ");
        }
    }
}

Code:

The minimum cost is (unrounded) $118.99
17: 1, 2, 3GF, 4 is such a path.
in 0.0090 s

It's possible I made a mistake; criticism is welcome.

The path string means that we chose path 17, we did nothing at towns 2 and 4 (and 1 automatically), and we got gas and ate food at town 3 (which is town E).

**RoyalFlush** · May 16th 2010, 04:38 PM

Okay, this is officially a 'Resource Constrained Shortest Path' problem. I have been given an algorithm in class , but I'm having a really difficult time understanding it. The algorithm is as follows:

Let $R$ be a set of resources.
Let $N$ be the set of nodes.
Let $A_i$ be the set of nodes connected to node $i$ .
Let $d_{ij}$ be the length of arc from $i$ to $j$ , assumed to be positive for all arcs.
Let $U_{ij}$ be the vector of resource consumption on the arc from $i$ to $j$ . It is not necessary that these are positive. Some arcs can replenish resources.

Let $L_i$ be the set of labels for node $i$ .

( $i, s V, done$ ) - the data stored with a label: $i$ the node, $s$ the relevant path length, $V$ the vector of resource levels, $done$ a boolean flag. For label $l$ these can be written as $i_l, s_l, V_l, done_l$ .

Assume we start at the origin $O$ with an initial vector of resources $V_O$ . We can define a resource constrained shortest path algorithm as follows:
(1) Set $L_i =$ ∅, $i \in N$ ; $L_O = \{(O, 0, V_O, false)\}$ .

(2) Choose $l$ the label such that $s_l = min \{s_l | done_l = false\}$

(3) If $i_l = D$ then stop.

(4) Set $done_l = true.$

(5) For all $j \in A_ij$ , such that $V_l - U_{ij} \geq 0$
AddLabel $\{j, s_l +d_{ij}, V_l - U_{ij}, false\}$
(6) Go to step 2

The process AddLabel removes and labels (including the label to be added itself) if the are dominated by some other label. By definition, label $l_1$ dominates label $l_2$ if and only if

$i_{l_1} = i_{l_2}, s_{l_1} \leq s_{l_2}, V_{l_1} \geq V_{l_2}$

One label dominating another implies a separate path to the same node that is shorter (or at least no longer) and consumes less (or at least no more) of every resource. In the case of no resource this algorithm reduces to a shortest path algorithm.

What I have to do is write down a general purpose formulation (recursion or algorithm) for calculating the cheapest way from Townsville to Villageville, using the above algorithm, and find the shortest path from each node to Villageville. How can the this information (shortest path to destination from each node) be used to find a lower bound on the cost of completing any partial journey using the algorithm used to find the cheapest way from Townsville to Villageville.

I am also unsure what is meant by the lower bound.

**undefined** · May 16th 2010, 08:40 PM

Originally Posted by RoyalFlush

Okay, this is officially a 'Resource Constrained Shortest Path' problem. I have been given an algorithm in class , but I'm having a really difficult time understanding it. The algorithm is as follows:

Let $R$ be a set of resources.
Let $N$ be the set of nodes.
Let $A_i$ be the set of nodes connected to node $i$ .
Let $d_{ij}$ be the length of arc from $i$ to $j$ , assumed to be positive for all arcs.
Let $U_{ij}$ be the vector of resource consumption on the arc from $i$ to $j$ . It is not necessary that these are positive. Some arcs can replenish resources.

Let $L_i$ be the set of labels for node $i$ .

( $i, s V, done$ ) - the data stored with a label: $i$ the node, $s$ the relevant path length, $V$ the vector of resource levels, $done$ a boolean flag. For label $l$ these can be written as $i_l, s_l, V_l, done_l$ .

Assume we start at the origin $O$ with an initial vector of resources $V_O$ . We can define a resource constrained shortest path algorithm as follows:
(1) Set $L_i =$ ∅, $i \in N$ ; $L_O = \{(O, 0, V_O, false)\}$ .

(2) Choose $l$ the label such that $s_l = min \{s_l | done_l = false\}$

(3) If $i_l = D$ then stop.

(4) Set $done_l = true.$

(5) For all $j \in A_ij$ , such that $V_l - U_{ij} \geq 0$
AddLabel $\{j, s_l +d_{ij}, V_l - U_{ij}, false\}$
(6) Go to step 2

The process AddLabel removes and labels (including the label to be added itself) if the are dominated by some other label. By definition, label $l_1$ dominates label $l_2$ if and only if

$i_{l_1} = i_{l_2}, s_{l_1} \leq s_{l_2}, V_{l_1} \geq V_{l_2}$

One label dominating another implies a separate path to the same node that is shorter (or at least no longer) and consumes less (or at least no more) of every resource. In the case of no resource this algorithm reduces to a shortest path algorithm.

What I have to do is write down a general purpose formulation (recursion or algorithm) for calculating the cheapest way from Townsville to Villageville, using the above algorithm, and find the shortest path from each node to Villageville. How can the this information (shortest path to destination from each node) be used to find a lower bound on the cost of completing any partial journey using the algorithm used to find the cheapest way from Townsville to Villageville.

I am also unsure what is meant by the lower bound.

Hmmm.. I come from a background of solving problems for fun haha, so the formal presentation here is a bit foreign to me. (If you're curious/interested, I'm very active on Project Euler, which has some pretty hard problems. I'll add some info on my profile in a month or whenever I get around to it heh, but I'm close to solving them all.)

Honestly I might have to see a working program or read your textbook or similar to be able to understand exactly what that discription means. I've implemented algorithms from math textbooks before, but not from computer science textbooks. Sorry I can't give you more useful advice after all the work you did writing up the algorithm with nice LaTeX and everything.

If I study what you wrote for like an hour maybe I'll see how it all fits... we'll see. But honestly I thought my approach was much simpler than all that.

There is one thing I'm unclear on that you'd have to clarify for me, because it's not in the description. Are the possible paths still the ones contained in the .doc file attached to the original post, or are we instead given a table (matrix) that has distances from each town to each town, like in train schedules? (This is the usual presentation of data, in my experience.)

Well there are some things I basically have no hope of deciphering, like $s_l = min \{s_l | done_l = false\}$ . I'm used to the format $a = min(b,c)$ and have no idea what the given syntax is supposed to mean.

Actually, I can see that it's saying choose the minimum $s$ available for which the done flag is set to false... but then where does $D$ come from?? It's just introduced out of the blue, without definition..

Well from context $D$ must be destination. I have an intuitive feel for the algorithm now. I still say $s_l = min \{s_l | done_l = false\}$ is a careless use of notation since $l$ is an undefined dummy variable on the right hand side while the same letter $l$ is being assigned for real on the left hand side.

Anyway, I'm still confused about the shortest path from each node to Villagevile part. How can we assign $V_O$ when we start from an intermediate node instead of the real origin, Townsville? We know that we have a full tank of gas and 4 hours to spare until the next meal when starting from the true origin, but from an intermediate node we can't know that.

Anyway, one thing the "lower bound" could mean is simply that it's the shortest/cheapest path. If we have a lower bound, and it's also a reachable quantity, then it must be the minimum value. (But the distinction between shortest and cheapest is also a bit blurred.)

Maybe it's just my limited exposure, but I'm not pleased with the quality of writing in the description, and I would like it to have been written more clearly (I believe you transcribed it accurately so of course I'm not blaming you for anything).

I also don't see anything in the algorithm that corresponds to filling up gas or eating a meal. The "replenishing arc" idea is rather vague.

Thread: Dynamic Programming

LinkBack

Thread Tools

Display