[Optimization] Advanced Dynamic programming

这里主要是较为详细地理解动态规划的思想，思考一些高质量的案例，同时也响应如下这么一句口号：

“迭代(regression)是人，递归(recursion)是神，动态规划是what?”

Video series for Dynamic Programming

---

 

Planning a company party

Ref: http://mypathtothe4.blogspot.com.au/2013/03/dynamic-programming-company-party.html

Stewart教授是一家公司总裁的顾问，这家公司计划一个公司聚会。这个公司有一个层次结构；也就是，管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名，这是一个实数。为了使每个参加者都喜欢这个聚会，总裁不希望一个雇员和他（她）的直接上司同时参加。

生成一张客人列表，使得客人喜欢聚会的程度的总和最大。

Naive Recursive Solution

Idea 1

1. 1. 变成了从大集合中挑N个人组合，当然，最好是由多到少的选人。
   2. 然后判断这个集合是否满足情况。

Idea 2

Find-Max-Conv(Node n)
    if n.children = null
        return max(, n.rating)   

    return max( Sum(Find-Max-Conv(i)) for all i = n.children),
                Sum(Find-Max-Conv(i) for all i = n.grandchildren) + n.rating)

//return 的内容有问题，不过不要紧

Let's take a quick look at what this recursion does: the base case (leaves) in lines (1, 2) simply returns the max value of not 0 (not inviting someone) and the conviviality rating of the person. (We need the comparison with 0 in case the conviviality is negative). Line 3 is our recursive call; the solution, given some node, will be the maximum of inviting the current node (person) and not inviting the current node (person). If we invite the current node, we cannot invite children, and thus we sum the current value with the maximum ratings of the current node's grandchildren. If we don't invite the current node, then the maximum value would be the sum of maximum convivialities over all children.

Consider the running time of this algorithm. We go through every node in the tree, and consider adding or not adding it. So there are two options for each of n nodes (0, 1), meaning the number of operations will be some function of 2^n. This is exponential running time and undesirable.

Dynamic Programming

如何寻找sub-problem。

The principal idea then, is to start from node n and work back to the root, each time basing the current optimal conviviality on previously computed sub-problems that have been stored in some memoization table.

Find-Max-Conv(Tree t)
   Let MC[ ] be an array of length n that contains max conviviality from this node down in the tree
   for i = Node n down to
MC[i] = max(i.rating + Sum of all MC[i.grandchildren], Sum of all MC[i.children])
            (If node i has no grandchildren or children, replace i.grandchildren and/or i.children with )
   return MC[]

寻找子问题

节点（青绿）不参加的话，孩子都能参加。那么孩子的高兴值在sub-problem中应该是计算过了，保存在MC[]中。

节点（暗灰）若参加的话，孩子不能参加。那么孙子的高兴值在sub-problem中应该是计算过了，保存在MC[]中。

计算n个节点的SelectRoot和UnselRoot，每次计算都只使用子节点的域值，所以整个计算的过程也只累加了树中除了根的其它节点的域值（每个节点就被用一次）。所以算法复杂度为O(n)。

Find if a string is interleaved of two other strings

Ref: http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/

For example A = “XXY”, string B = “XXZ” and string C = “XXZXXXY”

两个字符串交叉得到的字符串，其中隐含了"顺序性"

Naive Recursive Solution

以下方式相当于遍历完了所有情况，有点围棋穷举的意思。

// A simple recursive function to check whether C is an interleaving of A and B
bool isInterleaved(char *A, char *B, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *B || *C))
        return true;

    // If C is empty and any of the two strings is not empty
    if (*C == '\0')
        return false;

    // If any of the above mentioned two possibilities is true,
    // then return true, otherwise false
    return ( (*C == *A) && isInterleaved(A+, B, C+))
         || ((*C == *B) && isInterleaved(A, B+, C+));
}

The worst-case time complexity of the recursive solution is O(2ⁿ).　　// 从return的形式可见"二叉树的node的扩展方式"

The above recursive solution certainly has many overlapping subproblems. For example, if we consider A = “XXX”, B = “XXX” and C = “XXXXXX” and draw recursion tree, there will be many overlapping subproblems.
Therefore, like other typical Dynamic Programming problems, we can solve it by creating a table and store results of subproblems in bottom up manner.

Dynamic Programming

Algorithm:

s1 = “aabcc”       <- x
s2 = “dbbca”       <- y
s3 = “aadbbcbcac”  <- z

寻找子问题

理解：

当len z = 4时，只会是len x + len y = 4的情况；

那么，这些情况中的一些，是在sub-problem中解决了的；

在表格中，只需关心“子问题”为T的格子，以及临近的两个格子（右，下）。

Idea:

在已有的可以的情况下的头顶加一个合格的帽子是没问题的。

不影响sub-problem的内部合理性，帽子也是满足：

"If z is the interleaving of x and y, it contains a subproblem z'= z₁...z_m+n−1 and the last bit z_m+n must be x_m or y_n."

len z = 4时（黄色格子），sub-problem的结果就是桔黄色的格子如下。

进一步地，规律如下，T的方格构成的必须是连通图。

Weights and Measures - Turtle Tower

叠乌龟问题：极其经典，研究价值五星 - 你值得拥有！ - 因为五星，所以配图。

From: http://cgi.cse.unsw.edu.au/~cs3121/Lectures/COMP3121_Lecture_Notes_DP.pdf

You are given n turtles, and for each turtle you are given its weight and its strength.

The strength of a turtle is the maximal weight you can put on it without cracking its shell.

Find the largest possible number of turtles which you can stack one on top of the other without cracking any turtle.

Naive Recursive Solution

　　/* 非常复杂，不太现实 */

Dynamic Programming

Subproblem P(j): Find the largest possible number of turtles from the set {T₁ , . . . , T_j } 
which you can stack one on top of the other without cracking any turtle.

常规"子问题"没办法迭代！

思考：10个龟情况下的叠起来的方案，能否用于加了一个11th龟后的情况？

P(11) 的所有子情况是：

• • P(10)的最优解
  • P(09)的最优解
  • ...
  • P(01)的最优解

那么，P(11) 能利用这些么？

• • new P(11)的最优解中T₁₁是最下面的位置么？
  • new P(10)的最优解中T₁₁是最下面的位置么？
  • new P(09)的最优解中T₁₁是最下面的位置么？
  • ...
  • new P(01)的最优解中T₁₁是最下面的位置么？

不能保证！

加一个“龟”，会破坏子问题的situation，导致必须重新思考“子问题”

故，new P(09)的最优解就不是extension of P(09) 的最优解。

如何找到正确的“子问题”

那什么feature才能保证永远在最优方案最下面的位置呢？

（推理一）

Answer: strength + weight

Thus, we order turtles according to the sum of their strength plus their weight, i.e., assume that for all i, j ≤ n

关于这个意义在于，它保证了一种叠海归的方案，这个方案的最底下的海龟是新海龟，因为它的strength + weight最大。

本就是按照有小到大的顺序依次处理的嘛。更直接地说：T_j相对于已有在处理的海龟集都是最大的。

也就是说：子问题扩展的时候，提供了一种安全的“添加一个海龟”的顺序。

感性理解

To guarantee that optimal towers can be obtained from the previous optimal towers

we build a sequence of lightest possible towers of every possible height.

P(10) height:3 的构造过程：

        

T₁₀ 若能承受w1+w2，则T10必定在最底下。 　　　　<-- 保证了recursion的可行性！

T₁₀ 不能承受w1+w2，则不管如何排1，2，T10 都是不可能的。

假设，1，2都是只能承受一个node的主儿，那么height:3时，就会是右图所示，去掉了2。

Key理解：

"在P(10) height:3可行的大前提下，如此，必定真正的P(10) height:3就是这么组合的了"

何为"可行"？就是直接看s_T10 > w₁+w₂就是可行。（因为有推理一作为保证）

P()　　// Now

• • • height 1  --> 若干results, 只选最轻的那一个
    • height 2  --> 若干results, 只选最轻的那一个
    • height 3  --> 若干results, 只选最轻的那一个
    • ...
    • height 10 --> 若干results, 只选最轻的那一个

P()　　// Sub-problem

• • • height 1 --> 若干results, 只选最轻的那一个
    • height 2 --> 若干results, 只选最轻的那一个
    • height 3 --> 若干results, 只选最轻的那一个
    • ...
    • height 9 --> 若干results, 只选最轻的那一个

etc.

Thus, we solve the following generalisations of our problem, for every j ≤ n:

Subproblem P(j):

For each k ≤ j for which there exists a tower of turtles of length k built from turtles {T₁, . . . , T_j} (not necessarily containing T_j ),

find the lightest one.

Recursion:

With this subproblem, we can solve any P(i) like this:　　// P(10)

*************************************************************

To obtain the lightest tower θ(k, i) of any height k built from turtles {T₁,...,T_i},　　// θ(k, 10): P()下的一系列heigh k = 3

we look at

• • the lightest tower θ(k, i−1) of height k                                                               // θ(k, 09): P()下的一系列heigh k = 3

  • the lightest tower θ(k-1, i−1) of height k − 1                                                     // θ(k, 09): P()下的一系列heigh k-1 = 2

both built from turtles T₁,T₂,...,T_i−1, which we have got in the sub-problem P(i-1).

*************************************************************

有了已解决的子问题，那么，咱们就开始判断咯：

• • If the tower obtained by extending θ(k-1, i−1) with T_i is both legitimate and lighter than θ(k, i−1), we let θ(k, i) be such a tower. (this means T_i contributes to a better lightest tower with more Residual Capacity)

  • Otherwise we let θ(k, i) = θ(k, i−1).

可以如此理解：

　　新转来一名学生，只要比较她跟班里的第三名成绩就好了：

　　* 比第三名好的话，就拿前两名加这个新生构成新的top3；

　　* 没第三名好的话，原来的top3依然保留地位。

Finally, we obtain the lightest tower θ(k, i) of any height k for P(i).

The solution to our problem is now obtained from the solution to P(n) by picking the longest tower obtained by solving P(n).

Box Stacking Problem

video讲解：https://people.cs.clemson.edu/~bcdean/dp_practice/dp_5.swf

The Box Stacking problem is a variation of LIS problem. We need to build a maximum height stack.

Following are the key points to note in the problem statement:

1) A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.

2) We can rotate boxes. For example, if there is a box with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities, {1x2x3}, {2x1x3} and {3x1x2}.

3) We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.

Following is the solution based on DP solution of LIS problem.

1) Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.

2) Sort the above generated 3n boxes in decreasing order of base area.

3) After sorting the boxes, the problem is same as LIS with following optimal substructure property.

MSH(i) = Maximum possible Stack Height with box i at top of stack　　// 这个顶上的 box i 是强制安排的

MSH(i) = { Max ( MSH(j) ) + height(i) } , where j < i and width(j) > width(i) and depth(j) > depth(i).

If there is no such j then MSH(i) = height(i)

4) To get overall maximum height, we return max(MSH(i)) where 0 < i < n

Bin-packing problem

传统的三种方式：https://www.youtube.com/watch?v=kiMFyTWqLhc

Full-bin packing Algorithm中已体现出了动规的影子，或者叫必要性。

要确保得到最优的答案，还得看动规，以下是一些可能有用的参考链接。

ref: https://www.youtube.com/watch?v=wy45-JH8_yY

ref: http://www.sciencedirect.com/science/article/pii/S0377221706004310?via%3Dihub

Idea: （核心思想）

opt(i, j, p)是由一堆子问题堆积起来的，or 推起来的。

关键在于理解这个opt(i, j, p)和下面子问题之间的关系，要如何建立之间的逻辑关系。

子问题：

条件： s1 = 2,  s2 = 3,  s3 = 5,  C = 10 (size of bin)

i = 7, j = 3, p = 3
opt(i-5, j, p)	opt(i-3, j-1, p)	opt(i-2, j-2, p)	opt(i, j-3, p)	opt(i-2, j, p-1)	opt(i-1, j-2, p-1)	opt(i, j, p-2)
opt(2, 3, 3) = 3	4, 2, 3	5, 1, 3	7, 0, 3	5, 0, 2	6, 1, 2	7, 7, 0	sub-p
		opt(0,1,3) = 2 bin	2,0,3	0,3,2	1,1,2	2,3,1	sub-p of 2,3,3
						opt(0,1,1) = 1 bin	sub-p of 0,1,3
size: 2*2+3*3+3*5=28 暗含了一个道理： 多两个s1和两个s2是肯定要 多一个bin的		size: 0*2+1*3+3*5=18 暗含了一个道理： 多两个s3是肯定要多一个bin的

可见，这是个六叉树！孩子就是子问题。

递归是从上到下，貌似预分配了所需的所有空间，也就是六叉树的所有node。

动规，则提供了自底向上的思路，每个子问题仅保存了最优的结果（一个数值），这样便节省了空间。

其实，这也体现了 prolog language 解决问题的思路，以及设计原理，即：

解决递归问题，选择prolog会更加高效，方便。

IDE online: http://potassco.sourceforge.net/clingo.html