В рекурсивном DP разбить рекурсивный вызов, сохранив переменные: неэффективно? - PullRequest
Новая
       21

В рекурсивном DP разбить рекурсивный вызов, сохранив переменные: неэффективно?

0 голосов
/ 11 марта 2019

Предположим, я рекурсивно решаю задачу динамического программирования (сверху вниз).Например, рекурсивное решение самой длинной общей проблемы подпоследовательности: 

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); 
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) );
return result;
}

Часто в такой задаче DP в какой-то момент мы должны взять максимум некоторых выражений, представляющих возврат к различным вариантам, которые мы можем сделать.В приведенном выше случае у нас есть максимум двух простых выражений, но в худших случаях это может быть максимум из трех или четырех довольно сложных выражений, включающих длинные вызовы функций.В таких ситуациях я часто испытываю желание дать этим сложным выражениям их собственные имена переменных, чтобы сделать код более читабельным.В вышеупомянутом случае это означало бы, что я написал бы 

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); 
else
    a = LCS(S,n-1,T,m);
    b = LCS(S, n, T, m-1); 
    result = max(a, b);
return result;
}

(В этом упрощенном случае a и b не сложны, но в других случаях они есть, и может быть даже больше аргументовфункция max, так что это действительно может помочь сделать ее более понятной.)

Мой вопрос: Это ужасная идея?Насколько я понимаю, я добавляю переменную к каждому слою стека вызовов, и я думаю, что это может быть расточительным.Но, с другой стороны, на каждом слое он все равно должен вычислять временную переменную LCS(S,n,T,m) (скажу, я имею в виду C ++), и, насколько мне известно, между стоимостьюдвумя способами.

Если это ужасная идея, есть ли более эффективный способ разбить сложный рекурсивный вызов функции, чтобы сделать его более читабельным?

1 Ответ

1 голос
/ 12 марта 2019

C ++ имеет правило «как если», которое гласит, что компилятор может делать все, что ему захочется, при условии, что наблюдаемые эффекты неотличимы от того, что определено в стандарте. В этом случае тривиально доказать, что оба фрагмента имеют одинаковое значение, и компилятор, вероятно, выдаст одинаковые инструкции для обоих.

Примечание. Динамическое программирование здесь не выполняется, так как вы не запоминаете пары параметров / результатов.

...