重复子问题 overlapping subproblem

如果求出一个问题的最优解时需要对同样的某个问题求解多次，那么这个问题就具有重叠子问题。

an optimal solution involves solving the same problem multiple times.

比如，佩波那契数的 fib (2), fib (3) 等，要被递归调用到很多很多次。 归并排序没有表现出这个特性，尽管我们会进行多次合并，但每次合并的都是不同的列表。

关键特征是 same，关键动作是 memo。

最优子结构 optimal substructure

如果一个问题的全局最优解可以通过组合局部子问题的最优解求出，那么这个问题就具有最优子结构。

a globally optimal solution can be found by combining optimal solutions to local subproblems.

比如，归并排序对一个列表进行排序的方式就是先对子列表进行排序，然后再合并子列表的排序结果。

关键特征是 local，关键动作是 merge。

只用递归写的佩波那契数的算法，复杂度是多少？

据说是 O (fib (n)).

fib (120) 是 8 670 007 398 507 948 658 051 921，8.67x10^24.

我的电脑 2.6GHz，大概要算 9500 万年。

从佩波那契数的结构中看出什么特点？可以怎么利用它简化计算？

1. 它的递归公式 fib (n) = fib (n-1) + fib (n-2) 自然就是最优子结构：小范围的解可以合并出大范围的解。
2. 图中 fib (3) 出现了 3 次，被计算了 3 次。一样的问题，可以不必重复计算，返回记住的结果就好了。这是典型的 “重复子问题”。

怎样用代码实现快速计算佩波那契数？

备忘录法

def fastFib (n, memo = {}):
    """ 假设
        n 是非负整数，
        memo 只在递归调用中使用，默认值是空字典，无需使用者创建。
    返回
        第 n 个斐波那契数 """
    if n == 0 or n == 1:
        return 1
    try:
        return memo [n]
    except KeyError:
        result = fastFib (n-1, memo) + fastFib (n-2, memo)
        memo [n] = result
        return result

复杂度是 O (n)。既然查字典是常数时间，那么计算量就只和 n 有关了。

什么是 “根二叉树”？

a rooted binary tree = a graph, an acyclic directed graph

• 关于根，只有一个根 root，它没有母 parent 节点。
• 关于母关系，每个非根节点都只有一个母节点。
• 关于子关系，每个节点最多只有两个子节点，没有子节点的称为 leaf。

有向 directed：母子关系。

无环 acyclic：只能从上往下，不能返回上面，不会形成闭环。

O/1 背包问题的二叉树描述方式？

作为推导解决方案的第一步，我们先基于穷举法得到一个指数级别的解法。核心思想就是构造一个根二叉树，枚举所有满足重量约束的状态，从而探索可行解空间。

枚举的不是所有状态，而是满足重量约束的。根据是否满足重量约束，就可以修改二叉树了。

在 0/1 背包问题的搜索树中，每个节点都使用一个四元组 quadruple 进行标注，这个四元组表示的是这种背包问题的一个局部解。四元组中的四个元素如下：

1. 要带走的物品集合 set；
2. 还没有决定是否要带走的物品列表 list；
3. 要带走的物品集合中的物品总价值（这个值只是为了优化算法，因为可以从集合中计算出这个值）；
4. 背包的剩余空间（这也同样是一种算法优化方式，因为这个值可以通过背包允许的总重量减去当前要带走的物品总重量计算出来）。

O/1 背包问题的二叉树决策树，与上一章的贪婪算法和暴力穷举法有什么异同？

决策树和暴力解法都是穷举，但是视角不同。

核心是换一个角度理解问题，把组合问题，看作选择问题：拿还是不拿下一个件，形成二叉树的决策树。

决策树和贪婪算法都是一个一个地拿，在拿下一个物品时，做一步选择比较。

贪婪算法，只看一项指标，以此指标排序，取其中最大者。贪婪算法并不穷举。

从 0/1 背包问题的决策树里看出哪几个意思？

从上图中看出：

• 叶子没有子节点，因为达到了两种境地：房间里没有东西可拿，或者，背包里没有空间可装。
• 遍历所有情况的话，是 2^4=16 种，其中符合重量条件的有 7 种。
• 两处有类似情况：待选列表是 [c, d]，剩余重量空间是 2。
• 相同层级的节点，有一样的待选项列表。

O/1 背包问题的二叉树结构代码？

def maxVal (toConsider, avail):
    """ 假设 toConsider 是一个物品列表 list，avail 表示背包还能再装的重量值。
       返回一个元组表示 0/1 背包问题的解，包括物品总价值和带走的物品元组。"""

    #典型二叉树判断：是否有子节点，如果有，是只有一个，还是两个？
    if toConsider == [] or avail == 0:
        #这是叶节点，是 base case，它的解就是（0，空），返回。
        result = (0, ())
    elif toConsider [0].getWeight ()> avail:
        #如果如此，只能探索右侧分支，右侧分支的值作为返回值。
        result = maxVal (toConsider [1:], avail)
    else:
        #如果下一个物品可以装进去，两个分支都需要探索。
        nextItem = toConsider [0]

        #左侧分支的两个值写成
        withVal, withToTake = maxVal (toConsider [1:],
                                     avail - nextItem.getWeight ())
        withVal += nextItem.getValue ()

        #右侧分支写成
        withoutVal, withoutToTake = maxVal (toConsider [1:], avail)

        #选择更好（物品总价更大）的分支的值，作为函数返回值。
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    return result

O/1 背包问题采用二叉树结构表达和编码，计算复杂度是多少？

虽然排除了几个不满足背包重量的分支节点，但是理论上说，每个层级的节点数目仍然是 2^n。

并没有比暴力穷举法改善多少。所以说，0/1 背包问题从本质上来说，是指数级复杂度。

如果它有某些特性，比如有很多重复子问题，那么可以减少计算次数。

O/1 背包问题的二叉树结构，是否具有优化子结构和重复子问题？

优化子结构

母节点有两个子节点，母节点问题的答案，是在两个子节点答案中选更好的那个。这代表了局部优化后的答案，提供了整体优化的基础。或者说，局部的答案，可以通过一个简单的比大小的方式，就 merge 成了上层结构的答案。

重复子问题

看似每个子节点的都不同，但是它们面临的问题相同：满足背包剩余重量约束，从剩余的物品列表中，选择最优的组合。这个问题与已经选了什么物品无关，与已经选择的物品重价无关。用这个眼光看，就能发现节点 2 和节点 7 面临着同样一个问题，不必重复计算，可以用备忘录字典。

带备忘录的 0/1 背包问题代码怎么写？为什么可以用剩余物品列表的长度作为备忘录字典的关键值？

def fastMaxVal (toConsider, avail, memo = {}):
    """ 假设 toConsider 是物品列表，avail 表示重量
         memo 进行递归调用
       返回一个元组表示 0/1 背包问题的解，包括物品总价值和物品列表 """

    #为什么 toConsider 列表的长度竟然就有代表性？
    #因为决策树上相同的层级有一样的待选列表，长度也一样，不同层级之间长度不同。
    #待选列表总是从一个方向剔除元素，所以其长度就成了它精简的代表。
    if (len (toConsider), avail) in memo:
        result = memo [(len (toConsider), avail)]
    elif toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider [0].getWeight ()> avail:
        #探索右侧分支
        result = fastMaxVal (toConsider [1:], avail, memo)
    else:
        nextItem = toConsider [0]
        #探索左侧分支
        withVal, withToTake =\
                 fastMaxVal (toConsider [1:],
                            avail - nextItem.getWeight (), memo)
        withVal += nextItem.getValue ()
        #探索右侧分支
        withoutVal, withoutToTake = fastMaxVal (toConsider [1:],
                                                avail, memo)
        #选择更好的分支
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    memo [(len (toConsider), avail)] = result
    return result

因为决策树上相同的层级有一样的待选列表，长度也一样，不同层级之间长度不同。

待选列表总是从一个方向剔除元素，所以其长度就成了它精简的代表。

用了备忘录技术 memoization technique 的 0/1 背包问题，计算复杂度是多少？

memo 字典以 (len (toConsider), avail) 为关键字。

toConsider 中可能的值的数量不会超过 len (items)。

关键是 avail 中可能的值的数量。如果背包最多容纳 n 个物品（基于背包容量和可用物品的重量），那么 avail 最多可以有 2^n 个不同的值。理论上，这是个相当大的值，但实际情况下一般不会那么大。即使背包的容量很大，如果物品重量来自一个相当小的重量集合，那么很多物品集合都会具有相同的总重量，这样就极大地缩短了程序运行时间。

这样的算法复杂度称为伪多项式 pseudo-polynomial 复杂度。简言之，fastMaxVal 的复杂度与表示 avail 可能值所需的位数成指数关系。

fastMaxVal is exponential in the number of bits needed to represent the possible values of avail.

不太明白。

算法改进能创造奇迹吗？

不能。

miraculous

common sense：extraordinary and bringing welcome consequences.

liturgial sense: 奇迹。

动态规划与分治算法的两点重要区别是什么？

母问题与子问题的规模差异

• 分治算法每分一次，规模都大幅减少。比如二分查找和归并排序。
• 动态规划的子问题，规模并不比母问题小多少。比如 fib (19) 与 fib (20)。

效率是否依赖于结构化算法

• 分治算法的复杂度基本是确定的。
• 动态规划的降低了复杂度，因为结构中子问题重复 overlapping 得多。换句话说，子问题可以有很多很多，但是其中真正不同的子问题相对是很少的，只有在这种情况下，动态规划才是高效的。

以上，2018-04-29。