【算法】记忆化搜索_python 记忆化搜索

Part.I Introduction

记忆化（英语：memoization）是一种提高计算机程序执行速度的优化技术。通过储存大计算量函数的返回值，当这个结果再次被需要时将其从缓存提取，而不用再次计算来节省计算时间。记忆化是一种典型的在计算时间与电脑存储器空间之中获取平衡的方案。在计算中，记忆或记忆化是一种优化技术，主要用于存储大开销函数调用的结果，并在相同输入再次出现时返回缓存结果，从而加速计算机程序。记忆化也用于其他上下文（以及速度增益以外的目的），例如在简单的相互递归下降解析中。虽然与缓存相关，但记忆化是指这种优化的一种特定情况，与缓存形式（如缓冲或缓存文件置换机制）不同。在某些逻辑编程语言的上下文中，记忆化也被称为 tabling。

上面说了一大堆，实际上记忆化很简单。它就是用一个列表讲之前算的结果保存下来(比如保存到列表中)，然后再有相同的需求的时候，直接从列表中取出来，避免重复操作。
因为它相较于之前不采用记忆化的操作，增加了一个列表的内存开支，但是避免了重复操作；所以说它是计算时间与电脑存储器空间之中获取平衡的方案。

Part.II 记忆化搜索的实现

下面根据一个例子，针对几种笔者常用的语言，简单记录一下记忆化是在实际工作中如何实现的。

---

首先是题目描述：

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

• 提供 100ml 的 汤A 和 0ml 的 汤B 。
• 提供 75ml 的 汤A 和 25ml 的 汤B 。
• 提供 50ml 的 汤A 和 50ml 的 汤B 。
• 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意：不存在先分配 100 ml 汤B 的操作，$0\le n\le 10^9$。

需要返回的值： 汤 A 先分配完的概率 + 汤 A 和汤 B 同时分配完的概率 / 2。返回值在正确答案 $10^{-5}$ 的范围内将被认为是正确的。

---

简单分析(摘自 LeetCode@ylb 大佬)：

因为每次分配都是分配25的整数倍，所以不妨将数据规模缩小(均除以25，向上取整)，那么分配方案变为：

• 提供 4 单位 A，0 单位 B
• 提供 3 单位 A，1 单位 B
• 提供 2 单位 A，2 单位 B
• 提供 1 单位 A，3 单位 B

我们以dfs(i,j)表示对i单位A和j单位B的『我们想要的分配概率』，注意这个名词的理解，我们想要的是『A被分配完』的概率+『A，B同时被分配完』的概率 / 2；对于dfs(i,j)它有四种分配方案，各占0.25

• dfs(i-4,j)
• dfs(i-3,j-1)
• dfs(i-2,j-2)
• dfs(i-1,j-3)

换言之，dfs(i,j)=0.25 * (dfs(i-4,j), dfs(i-3,j-1), dfs(i-2,j-2), dfs(i-1,j-3))。很显然这是一个自上而下的迭代，迭代的终止条件为：

• i<=0 && j>0：返回 1，仅仅『A被分配完』的概率
• i<=0 && j<=0：返回 0.5，『A，B同时被分配完』的概率 / 2
• i>0 && j<=0：返回 0，仅仅『B被分配完』的概率，不是我们所需，所以为0

经过上面的分析，答案就呼之欲出了！

---

一些优化：

• 因为$0\le n\le 10^9$，但是经过实际操作我们可以发现：当我们发现在 n=4800n=4800 时，结果为 $0.999994994426$，而题目要求的精度为 $10^{-5}$ ，并且随着 $n$ 的增大，结果越来越接近 $1$，因此，当 $n>4800$ 时，直接返回 $1$ 即可。

---

Chap.I Python

对于 Python 3.9 及以上的版本，可以使用functools包中的提供的高阶函数cache，它是简单轻量级无长度限制的函数缓存，这种缓存有时称为 “memoize”（记忆化）。

语法为 @functools.cache(user_function)，创建一个查找函数参数的字典的简单包装器。 因为它不需要移出旧值，缓存大小没有限制，所以比带有大小限制的 lru_cache() 更小更快。这个 @cache 装饰器是 Python 3.9 版本中的新功能，对于上述问题的代码为：

from functools import cache

class Solution:
    def soupServings(self, n: int) -> float:
        @cache
        def dfs(i: int, j: int):
            if i<=0 and j<=0:
                return 0.5
            if i<=0:
                return 1
            if j<=0:
                return 0
            return 0.25*(dfs(i-4,j)+dfs(i-3,j-1)+dfs(i-2,j-2)+dfs(i-1,j-3))
        return 1 if n>4800 else dfs((n+24)//25,(n+24)//25)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

对于 Python 3.9 以下的版本，可以使用 @lru_cache(MaxSize) ，代码如下：

class Solution:
    def soupServings(self, n: int) -> float:
        MaxSize=100000
        @lru_cache(MaxSize)
        def dfs(i: int, j: int):
            if i<=0 and j<=0:
                return 0.5
            if i<=0:
                return 1
            if j<=0:
                return 0
            return 0.25*(dfs(i-4,j)+dfs(i-3,j-1)+dfs(i-2,j-2)+dfs(i-1,j-3))
        return 1 if n>4800 else dfs((n+24)//25,(n+24)//25)
1
2
3
4
5
6
7
8
9
10
11
12
13

Chap.II C++

C++ 中类似@cache之类的装饰器，所以只能自己定义一个数组来存储那些有结果的函数值，对于这道题的解答如下：

class Solution {
public:
    double soupServings(int n) {
        double f[200][200]={0.0};
        function<double(int,int)> dfs=[&](int i,int j) -> double {
            if(i<=0 && j<=0) return 0.5;
            if(i<=0) return 1;
            if(j<=0) return 0;
            if(f[i][j]>0) return f[i][j];
            double ans=0.25*(dfs(i-4,j)+dfs(i-3,j-1)+dfs(i-2,j-2)+dfs(i-1,j-3));
            f[i][j]=ans;
            return ans;
        };
        return n>4800?1:dfs((n+24)/25,(n+24)/25);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16