избежать хвостовой рекурсии питона для DP - PullRequest
Новая
       40

избежать хвостовой рекурсии питона для DP

0 голосов
/ 05 октября 2018

Я написал в Python следующую рекурсивную функцию для вычисления решения в алгоритме DP для задачи планирования взвешенных интервалов, где интервалы являются «sorted_operations».Я слежу за книгой «Разработка алгоритмов» Кляйнберга и Тардоса, а 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)

1 Ответ

0 голосов
/ 05 октября 2018

Не зная больше о вашем коде, я не могу действительно предложить подробное решение.Тем не менее, одна часть вашего алгоритма действительно запомнилась: 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, это может быть основным преимуществом.

...