A road named NoNameUno

Suppose there is a train system that goes from station 1 to destination station N. Name the stations as you wish instead of 1, 2, ... N. You are suppose to get a ticket that minimize cost to go from 1 to N. The costs of the fairs going from i to j station is given as Cij, i < j.

 Based on the cost matrix C, we can see that we could draw a graph. Please try simple train system like: 3 stations, and see.

 First thing we need to comeup with a functional equation. In order to arrive at N station, we have to get to some intermediate station, and from their we need one more step to get to N.

Lets F(i,j) = Minimal cost from station i to j, i < j;  Then

F(i,j) = min { F(i, j-1) + C<j-1, j>  ;  C<i,j>  }, where C<i,j> is the fair to go from Ci to Cj

Now is the time for a try ...

//

//  TicketMaster.c

//  DP

//

//  Created by Admin on 5/10/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

/*

 * TicketMaster is usually a person who gives you ticket to your destination station from the station you are now.

 *

 * U R given a simple railroad with stations 1, 2, 3, ... N. U R going from station 1 to N, and between each pair of

 * stations (i,j), s.t. i < j there is a cost per ticket c(i,j). How do you minimize the cost of your travel from 1 to N

 * In general minimize the cost from i to j.

 *

 * This can be represented as Directed Acylic Graph (DAG). Try drawing a simple graph on 3 station to have the feel.

 * In Algos, and in general in Math, it is essential to find the nature of the problem, categorize if possible, classify

 * to a know group of problmes, finally find a pattern or two and possibly reduce it to know problem.

 *

 * It surely looks like shortest path problem, since length and costs are interchangeable. Also it looks like a staged

 * DP problem. Once we understand this much, it is time to comeup with Functional equation for the DP or just a

 * recursive formulation of the problem. NOTE: While DP problems are   back-tracking  in nature, recursive are bottom up

 * also depends on how you look at.

 * FUCTIONAL EQUATION ::

 *

 * Let F(i,j) = Minimal cost to travel from i to j, s.t i<j. Then

 *

 * F(i,j) = Min { F(i, j-1) + C(j-1, j); C(i,j) }

 *          i<j

 *

 * As you can see this is the recursive formulation !! Why? Because it is not using any intermediate calculations !!

 * Can we memoize the intermediate computations ? I'm not sure though, just will have to play around with some

 * concret example

 */

#include <stdio.h>

unsigned int Min ( unsigned int a, unsigned int b)

{

    return ( a < b ? a : b);

}

unsigned int C[4][4] = {

    {9999, 4, 6, 14},

    {9999, 9999, 5, 7},

    {9999, 9999, 9999, 3},

    {9999, 9999, 9999, 9999}

};

unsigned int TicketMaster(unsigned i, unsigned j)

{

    int highNo = 999999;

    if ( i >=j){

        return highNo;

    }

    int result =  Min ( TicketMaster(i, j-1) + C[j-1][j],  C[i][j]) ;

    printf( "result=%d, i=%d, j=%d, C[j-1][j] = %d C[i][j]=%d\n", result, i, j, C[j-1][j],  C[i][j]); 

    return result;

}

int main(int argc, const char * argv[]) 

 {

    unsigned int  Minticketcost = TicketMaster(0, 3);

    printf("Minticketcost = %d\n", Minticketcost); 

    return 0;

}

// --- Traces ---

result=4, i=0, j=1, C[j-1][j] = 4 C[i][j]=4

result=6, i=0, j=2, C[j-1][j] = 5 C[i][j]=6

result=9, i=0, j=3, C[j-1][j] = 3 C[i][j]=14

Minticketcost = 9

Note that in this case it is 3 stage process. DP formulation might not be needed !!!

In DP3 we talked about recursive implementation for minimal coins needed for a given change amout.

Recursive algorithm is best seen as top-down tree. Drawing that tree for small sample shows there are redundant computations of sub-problems. So we need to store intermediate solution to sub-problems.

In general, Understanding the substructures and their relations to Original problem is the key.

DP problems have many classifications like: Dimensions, Stages, Deterministic vs. Non-deterministics. So understanding the structure and relate to some category is really a key insight.

During this process of trying and explaining DP problems and theirs' possible solutions I will try to cover as much as I could. But my main goal is to get to Stochastics Dynamic Programming.

Example:

We know shortest path in terms of distance or time is one such deterministic DP problem. None other than Bellman ( inventor of DP ) showed the solution using DP method.

Now lets turn around and think like ---

There is a roadway network from San Francisco, CA to Tempa,Florida. Further assume that there is a probability associated with any segment of the trip could be under construction, hence not accessible. Now the Question is how could I take the most viable route to get to the destination.

Another one, Suppose you expect N offers on your house on sale, and there a probablity associated with the i_th offer being the best offer. P(i) = Probability that the i_th offer is the best offer so far to accept and terminate the consideration process and H(i) = Probablity that it would be best to reject the offer to realize better gain later.

Above problems are some of the examples of - Stochastic Dynamic Programming. 

In DP 2, we saw that simple one dimensional problem could be fairly easy to get the DP functional equation, without going thru the recurrence relations first. This is because functional equation does not have too much dependencies. An example is Fibonacci number.

 Here we talk about CoinChange problem which is somewhat difficult to comeup with DP functional equation right away. So it is best to get a recurrence relation and solve it first. A correct solution at first is always a good idea ! Then analyze the execution and perhaps come up with DP functional equation.

I'M NO EXPERT in DP analysis, so one step at a time.

Problem statement:

Given a set of coins with infinite supplies of each denominations, like: S = {1, 5, 10, 25 }. So the set consist of pennies, nickels, dimes, and quaters.

Question: What is the minimal number of coins that make up to an amount of changes, say N.

Ex: N = 11 => {1, 10} or { 1, 5, 5}. MinNoOfCoins = 2.

Caution: Try to follow the DP 2 methods to come up with DP functional equations straight out and see if this could be easy or complex. 

Note that DP problems solving in most cases is to look at substructure from backtracking point of view.

So the recursive definition is -

MinNoOfCoins(N ) = min { 1+MinNoOfCoins(N-1); 1+MinNoOfCoins(N-5); 1+ MinNoOfCoins(N-10); 1+MinNoOfCoins(N-25)}, depending on what is the last denomination being picked.

 For this recursive definition, here is the implementation ---

//

//  Created by Admin on 5/6/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdio.h>

/*

 * Given a set of coins S = { 1, 5, 10, 25 } pennies, nickels, dimes, quaters

 * Given N the change Amout, say 73 or 62 or 49 ...

 * Find the min number of coins whose sum is N

 *

 * -- A straight DP functional equation may not be simple thing to do, becasue

 * -- D(N ) defined as Minmum no. of coins to get changes to N, then

 * -- D(N) = D(N-1) + D(N-5) + D(N-10) + D(N-25)

 * --- priming the table would be hard, laborious, and confusing.

 * -- So lets try the normal steps -- Find a recurrence equation.

 ---

 Let's MinCoins(N) = min of {  1+ Minconins(N-1); 1+ Mincoins(N-5); 1 + Mincoins(N-10); +1 + Mincoins(N-25)  }

 */

int Mincoins( int arr[], int Nodenomination, int N)

{

    int mincoins = N ;  /* the worst we can do using pennies */

    if ( N <= 0) return 0;

    /* array of coins from the denomination set S = { 1, 5, 10, 25} for example */

    for (int i = 0; i < Nodenomination; i ++) {

        if (N == arr[i])

            return 1;    /* just one more coin needed */

    }

    for (int i = 0; i < Nodenomination; i ++) {

        int numcoins;

        if ( arr[i] < N) {

            numcoins = 1 + Mincoins(arr, Nodenomination, N - arr[i]);

            mincoins = ( mincoins < numcoins) ? mincoins : numcoins;

        }

    }

    return mincoins;

}

int main(int argc, const char * argv[]) {

    int coins_set[] = { 1, 5, 10, 25};

    int MinNoOfCoins;

    int Nodenomination = sizeof(coins_set)/ sizeof(coins_set[0]);

    MinNoOfCoins = Mincoins(coins_set, Nodenomination,  62 /*49*/);

    // insert code here...

    printf("MinNoOfCoins = %d\n", MinNoOfCoins);

    return 0;

}

RK: If we try to find the minimum numbers of coins for a change of 4093 cents, the above implementation could take some time.

First a simple problem -

Given a number N, and a set of numbers, say S = {x1, x2, x3 }. Find the number of ways to represent N as sum of the numbers from set S. Since it is sum operator, we can ignore all  x in S, s.t. x > N. So assume all x <= N in this case.

Let say N = 5; S = { 1, 3, 4 }. How the different sum repesentation would look ? 

1+1+1+1+1

1+1+3

1+3+1

3+1+1

1+4

4+1. 

So we have 6 different ways to sum Note that 4+1 and 1+4 are different representations, so are others with 3.

We define F(N) = # of ways to write N as sum of elements from set S = { x1, x2, ... xm}. Here N = 5, and S= {1,3,4}.

Looking for substructure, so we need to fix, say the last position of the sum representations. Say, the last position is 1. then the rest of the sum has to be N-1. It is nothing but F(N-1), similarly if the last position is 3 or 4, then the rest of those representation has to be F(N-3) and F(N-4) respectively. Now since we have only three such numbers in the set, F(N) = F(N-1) + F(N-3) + F(N-4). What are the base cases ??

F(1) = # ways to represent 1 as sum of elements from the set S = {1,3,4}. Only one way, just select 1. F(2) = 1, since 1+1 is the only way. F(3) = 1+1+1 or 3 representations so F(3) = 2, and F(4) = 3

Solution -

F[1] = F[2] = 1; F[3] = 2; F[4] = 3;

for ( int i = 5, i <= N; i++ )

     F[i] = F[i-1] + F[i-3] + F[i-4];

That's it !!

Whart is the takeaway from this example ?

If the set S = {3, 5, 6, 9 } what would be functional equations and dependencies ? Solve it.

Dynamic Programming(DP) is originally an analytic process for different types of optimization problems in : Engineering, Economics, and stratic processes. Usually it came from Calculus of varations and other Analytic methods of Mathematics.

Then came the Operation Researchs as a branch of studies where dynamic programming plays a central role. We would try to avoid those topics that are not related to programming.

But we may cover an interesting part -- Probabilistic Dynamic Programming just for fun.

I've seen many websites for solving Dynamic Programming problems. Perhaps way too many, including PDF down loads etc. My main concern is how to get a systematic treatment of even approaching these problems ?

I don't know yet, and I'm still looking for it. So I will have my unbiased and humiliated discussions on this ...

 Principles of attacking DP problems --

-- try to find a recursive solution first. In order to do that it is important to define a Functional equation. The functional equation, if correct will lead to a recursive implementation. And the main theme will be like : F(n) = min { F(n-k), where 0 <=k < n } or some other form. So some operatior, almost always, would be used to carry forward the solution from sub-problems' solution.  This is to get the right sub-structures of the problem.

-- Now try to reduce the problem to basic cases, and hand calculate thru the equation to see if it is satisfying your equation. Like in Binary Tree search, we can argue with small sample binary tree to see if the recussive function, hence the implementation is correct or not. 

-- Finally see if the recusive solution on small base cases gives any redundant computations. If so, then we can use dynamic programming formulation for the problem. So try to come up with a DP formulation.

Note that DP solution requires saving of previous sub-problem computations. Hence memoization is needed using some sort of tables.

Other thing to note that DP problems has it own dimenstions like 1-d, 2-d, 3-d. 2-d, 3-d problems are harder to formulate though. 

Since Optimization problems are mostly the domain for DP solution, constraint functions gives the dimensions.

EX:    Maximize  or Minimize some Objective Function, subject to some constraint.