如何加速递归算法

Question

我正在尝试解决Hackerrank挑战石头游戏，以下是（缩短的）问题陈述。

我想出了以下解决方案：

# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def which_player_wins(n):
    if n <= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        next_ns = map(lambda x: n - x, legal_moves)
        next_ns = filter(lambda x: x >= 0, next_ns)
        next_n_rewards = map(which_player_wins, next_ns)      # Reward for opponent
        if any(map(lambda x: x=="Second", next_n_rewards)):            # Opponent enters a losing position
            return "First"
        else:
            return "Second"

for n in ns:
    print which_player_wins(n)

这个算法本质上是极小化极大算法，因为它会向前看一步，然后递归调用同一个函数。问题在于，在Hackerrank中，由于超时而终止：

事实上，我注意到评估which_player_wins(40)已经需要约2秒钟。有没有更快的解决方案，不会超时？

- Kurt Peek

---

你熟悉动态规划吗？你可以在任何好的算法书中阅读相关内容（例如Steven Skiena的Algorithm Design Manual）。 - Colonel Panic

提示：从1到n逐步计算，无需递归。这就是你在纸上解决问题的方法。 - Colonel Panic

Answer 1

从问题描述来看，您能够保留每次计算的中间和最终结果以在后续计算中使用。如果是这样，递归算法并不是最优选择。取而代之的是使用动态规划方式。

换句话说，保留一个全局数组，其中存储了先前确定胜利和失败的结果。当您确定一个新的值 n 时，而不是一直递归到底部，请使用之前的确定结果。

例如，当您到达 n=10 时，您会发现第一个玩家移除3个石头后还剩下7个石头，而您已经看到这是第二个玩家的胜利。因此，10个石头对于第一个玩家来说是胜利的。

我认为您的递归算法会重新计算 n=7 的结果，而不是使用先前的工作。

- Rory Daulton

Answer 2

你的解决方案可以运行（虽然速度非常慢），如果你有无限递归级别可用。但由于你没有重复使用已经计算过的结果，所以很快就会达到Python的递归限制。一个好的解决方案是，像上面建议的那样，使用非递归算法重新编写代码。

或者，你可以保留你现有的代码，但让它重复使用你已经看到过的任何结果。这被称为记忆化，一种实现的简单方法是将记忆化装饰器添加到计算下一步的代码部分。以下是使用记忆化加速递归算法的方法，我认为这正是你特别要求的：

1. 将第一个else后的所有代码转换为函数next_move(n)，该函数返回'First'或'Second'。
2. 添加memoize(f)函数，它将接受next_move(n)，并在n的结果已经被计算过时避免递归调用。
3. 在next_move定义之前立即添加装饰器行@memoize。

以下是代码：

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def next_move(n):
    next_ns = map(lambda x: n - x, legal_moves)
    next_ns = filter(lambda x: x >= 0, next_ns)
    next_n_rewards = map(which_player_wins, next_ns)  # Reward for opponent
    if any(map(lambda x: x == "Second", next_n_rewards)):  # Opponent enters a losing position
        return "First"
    else:
        return "Second"

def which_player_wins(n):
    if n <= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        return next_move(n)

for n in ns:
    print which_player_wins(n)

这大大加快了计算速度，同时减少了所需的递归级别。在我的电脑上，n=100的问题可以在0.8毫秒内解决。

- MichaelMaggs

---

要在Python 3+中运行此代码，请将最后一行更改为print(which_player_wins(n))。 - MichaelMaggs

Answer 3

在Rory Daulton的建议下，我使用动态规划重写了which_player_wins方法，如下所示：

# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

def which_player_wins(n):
    moves = [2, 3, 5]
    table = {j:"" for j in range(n+1)}
    table[0] = "Second"     # If it is the first player's turn an no stones are on the table, the second player wins
    table[1] = "Second"     # No legal moves are available with only one stone left on the board

    for i in range(2,n+1):
        next_n = [i - move for move in moves if i - move >= 0]
        next_n_results = [table[k] for k in next_n]
        if any([result == "Second" for result in next_n_results]):
            table[i] = "First"
        else:
            table[i] = "Second"

    return table[n]

for n in ns:
    print which_player_wins(n)

这导致成功解决了挑战（见下文）。

- Kurt Peek