时间戳

首页 > 解决方案 > 避免DP的尾递归python

python - 避免DP的尾递归python

问题描述

我用 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)

标签： pythonrecursiondynamic-programmingtail-recursion

解决方案

在不了解您的代码的情况下，我无法真正提供详细的解决方案。但是，您算法的一部分确实在我脑海中突出：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语句的运行频率，这可能是一个主要好处。

推荐阅读