python - 避免 DP 的尾递归 python

Question

我用 Python 编写了以下递归函数，用于在 DP 算法中计算加权间隔调度问题的解决方案，其中间隔为“sorted_operations”。我正在关注Kleinberg和Tardos的《算法设计》一书，OPT和p_list已经计算出来了。它似乎适用于相对较小的实例，但是一旦问题的规模增加，我就会超过“最大递归深度”，并且会收到错误。由于增加 sys.setrecursionlimit 会使我的内核崩溃，我想知道是否还有其他方法来编写此函数。

solution_set = []
def compute_solution(j):
    if j<=0:
       pass
    else:
        if sorted_operations[j]['weight'] + OPT[p_list[j]] > OPT[j - 1]:
            solution_set.append(sorted_operations[j])
            print(j)
            compute_solution(p_list[j])
        else:
            compute_solution(j - 1)

compute_solution(len(sorted_operations) - 1)

Answer 1

如果不了解您的代码的更多信息，我无法真正提供详细的解决方案。然而，你的算法的一部分确实在我的脑海中留下了深刻的印象:compute_solution(j - 1)。由于j是一个整数，因此使用j - 1再次调用算法比方法调用更适合循环，特别是因为这些在Python中往往有点昂贵。所以，我会像这样修改你的算法:

solution_set = []
def compute_solution(j):
    while (j > 0):
        if sorted_operations[j]['weight'] + OPT[p_list[j]] > OPT[j - 1]:
            solution_set.append(sorted_operations[j])
            print(j)
            compute_solution(p_list[j])
            return
        else:
            j = j - 1

compute_solution(len(sorted_operations) - 1)

根据 else 语句运行的频率，这可能是一个重大好处。