在《A Practical Guide to Quantitative Finance interview》一书中，有一个题目叫《Dynamic Card Game, 5.3 Dynamic Programming》
根据这本书的解决方案基本如下:
E[f(b,r)] = max(b−r,(b/(b+r))∗E[f(b−1,r)]+(r/(b+r))∗E[f(b,r−1)])
具有以下边界条件。
f(0,r)=0, f(b,0)=b
我尝试在python中实现它，如下所示:
def f(b,r):
if b == 0:
return 0
elif r == 0:
return b
else:
var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1)
return max( b-r, var )
print("The solution is")
print(f(26,26))
但是，由于某种原因，上面的代码陷入了无限循环，对于像f(26,26)这样的大输入，程序没有返回任何东西。
对于较小的数字可以正常工作。例如，f(5,5)将立即返回1.11904。
谁能解释我在代码中做错了什么?
动态规划可以有效地计算这个。这只是一个创建结果表E(f(b, r))的例子，并确保按顺序填充表，以便计算当前结果所需的表项已经计算完毕。
下面的代码精确地解决了这个问题(使用分数):
from fractions import Fraction as F
def S(b, r):
E = [[i] + [0] * r for i in range(b+1)]
for i in range(1, b+1):
for j in range(1, r+1):
E[i][j] = max(i-j, F(i, i+j) * E[i-1][j] + F(j, i+j) * E[i][j-1])
return E[b][r]
print(S(5, 5))
print(S(26, 26))
输出:
47/42
41984711742427/15997372030584
程序处理这些输入基本上不花时间(在我的机器上是0.027秒)。
递归实现的问题是，您一次又一次地为相同的b和r重新计算f(b,r)。
为了说明我的意思，您可以运行以下代码段-
n = 0
def f(b,r):
global n
n += 1
if b == 0:
return 0
elif r == 0:
return b
else:
var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1)
return max( b-r, var )
for i in range(5, 12):
n = 0
f(i, i)
print(f"Number of times function f gets called for f({i},{i}) - {n}")
输出:
Number of times function f gets called for f(5,5) - 503
Number of times function f gets called for f(6,6) - 1847
Number of times function f gets called for f(7,7) - 6863
Number of times function f gets called for f(8,8) - 25739
Number of times function f gets called for f(9,9) - 97239
Number of times function f gets called for f(10,10) - 369511
Number of times function f gets called for f(11,11) - 1410863
在python中，为自顶向下递归函数缓存数据的一种简单方法是使用内置的functools。lru_cache装饰因此将代码更新为-
from functools import lru_cache
@lru_cache
def f(b,r):
if b == 0:
return 0
elif r == 0:
return b
else:
var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1)
return max( b-r, var )
修复此问题。
我可以在41毫秒内使用上述函数获得f(26,26)的结果为2.6244755489939244。
重复与第一个示例相同的测试，我们的代码具有lru_cache，结果是-
Number of times function f gets called for f(5,5) - 35
Number of times function f gets called for f(6,6) - 13
Number of times function f gets called for f(7,7) - 15
Number of times function f gets called for f(8,8) - 17
Number of times function f gets called for f(9,9) - 19
Number of times function f gets called for f(10,10) - 21
Number of times function f gets called for f(11,11) - 23
上面的值越高，计数越小，这是因为我们没有清除缓存。
根据关于' memoization'的注释，添加这个简单的装饰符@functools.lru_cache已解决
import functools
@functools.lru_cache(maxsize=None)
def f(b,r):
if b == 0:
return 0
elif r == 0:
return b
else:
var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1)
return max( b-r, var )
我也做了%timeit之间的递归和纯动态规划的解决方案，由Paul Hankin提供，递归似乎快得多。90.1 ns vs 6.1 ms