JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
2.4.? Commonly used DP state domains | Reply
Problem:
The most creative part of inventing dynamic programming solution is defining recurrent relations. The recurrent relations consist of two parts: state domain and transitions. State domain is a set of states (subproblems) in dynamic programming. For each state the subresult will be calculated eventually. Transitions are the relations between different states which help calculate the subresults.

This recipe covers frequently used state domain types. The general approaches of dealing with them and real SRM examples are given. Also few optimizations specific to particular domains are mentioned here.



Solution
Code of DP solution usually contains an array representing subresults on the state domain. For example, classic knapsack problem solution will be like:
  int maxcost[items+1][space+1];
  memset(maxcost, -63, sizeof(maxcost));   //fill with negative infinity
  maxcost[0][0] = 0;                       //base of DP
  for (int i = 0; i<items; i++)            //iterations over states in proper order
    for (int j = 0; j<=space; j++) {
      int mc = maxcost[i][j];              //we handle two types forward transitions
      int ni, nj, nmc;                     //from state (i,j)->mc to state (ni,nj)->nmc
 
      ni = i + 1;                          //forward transition: do not add i-th item
      nj = j;
      nmc = mc;      
      if (maxcost[ni][nj] < nmc)           //relaxing result for new state
        maxcost[ni][nj] = nmc;
 
      ni = i + 1;                          //forward transition: add i-th item
      nj = j + size[i];
      nmc = mc + cost[i];
      if (nj <= space && maxcost[ni][nj] < nmc)
        maxcost[ni][nj] = nmc;
    }
  int answer = -1000000000;                //getting answer from state results
  for (j = 0; j<=space; j++)
    if (maxcost[items][j] > answer)
      answer = maxcost[items][j];
  return answer;

Here (i,j) is state of DP with result equal to maxcost[i][j]. The result here means the maximal cost of items we can get by taking some of first i items with overall size of exactly j. So the set of (i,j) pairs and concept of maxcost[i][j] here comprise a state domain. The forward transition is adding or not adding the i-th item to the set of items we have already chosen.

The order of iterations through all DP states is important. The code above iterates through states with pairs (i,j) sorted lexicographically. It is correct since any transition goes from set (i,*) to set (i+1,*), so we see that i is increasing by one. Speaking in backward (recurrent) style, the result for each state (i,j) directly depends only on the results for the states (i-1,*).

To determine order or iteration through states we have to define order on state domain. We say that state (i1,j1) is greater than state (i2,j2) if (i1,j1) directly or indirectly (i.e. through several other states) depends on (i2,j2). This is definition of order on the state domain used. In DP solution any state must be considered after all the lesser states. Else the solution would give incorrect result.


Multidimensional array
The knapsack DP solution described above is an example of multidimensional array state domain (with 2 dimensions). A lot of other problems have similar state domains. Generally speaking, in this category states are represented by k parameters: (i1, i2, i3, ..., ik). So in the code we define a multidimensional array for state results like: int Result[N1][N2][N3]...[Nk]. Of course there are some transition rules (recurrent relations). These rules themselves can be complex, but the order of states is usually simple.

In most cases the states can be iterated through in lexicographical order. To do this you have to ensure that if I = (i1, i2, i3, ..., ik) directly depends on J = (j1, j2, j3, ..., jk) then I is lexicographically greater that J. This can be achieved by permuting parameters (like using (j,i) instead of (i,j)) or reversing them. But it is usually easier to change the order and direction of nested loops. Here is general code of lexicographical traversion:
  for (int i1 = 0; i1<N1; i1++)
    for (int i2 = 0; i2<N1; i2++)
      ...
        for (int ik = 0; ik<Nk; ik++) {
          //get some states (j1, j2, j3, ..., jk) -> jres by performing transitions
          //and handle them
        }

Note: changing order of DP parameters in array and order of nested loops can noticably affect performance on modern computers due to CPU cache behavior.

This type of state domain is the easiest to understand and implement, that's why most DP tutorials show problems of this type. But it is not the most frequently used type of state domain in SRMs. DP over subsets is much more popular.
Subject Author Date
2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:16 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:16 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST
Re: 2.4.? Commonly used DP state domains caustique Jan 4, 2011 at 10:53 AM EST
Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 10:39 PM EST
Re: 2.4.? Commonly used DP state domains supersmecher Jan 9, 2011 at 3:46 AM EST
Re: 2.4.? Commonly used DP state domains i_want_passion Apr 11, 2013 at 6:51 PM EDT
Re: 2.4.? Commonly used DP state domains akshayk0406 Feb 4, 2011 at 11:57 PM EST
Re: 2.4.? Commonly used DP state domains syg96 Feb 12, 2011 at 11:35 AM EST
Re: 2.4.? Commonly used DP state domains akshayk0406 Feb 13, 2011 at 6:20 AM EST
Re: 2.4.? Commonly used DP state domains innocentboy2 Feb 17, 2011 at 5:28 AM EST
Re: 2.4.? Commonly used DP state domains sadek_romel Oct 17, 2017 at 12:34 PM EDT
Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 11:09 PM EST
Re: 2.4.? Commonly used DP state domains dimkadimon Jan 7, 2011 at 7:18 PM EST
Re: 2.4.? Commonly used DP state domains syg96 Jan 8, 2011 at 1:46 AM EST
Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 10:44 PM EST
Re: 2.4.? Commonly used DP state domains M.G.Z Feb 13, 2013 at 4:32 PM EST
Re: 2.4.? Commonly used DP state domains syg96 Mar 22, 2013 at 10:58 AM EDT
RSS