Рекурсия: различия между версиями

8 байт добавлено ,  13 лет назад
м
На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
 
Решить эту задачу за разумное время помогает '''динамическое программирование'''. Суть динамического программирования хорошо описана в книге Р. Беллмана \cite{BellmRef|Bell}. Есть и более современные учебники \cite{AhoRef|2}, Kormen{Ref|3}, в них можно найти много интересных алгоритмов, основанных на динамическом программировании.
 
Общая идея динамического программирования заключается в том, что мы рассматриваем вместо одной задачи целое семейство задач. Это семейство задач у нас будет таким: найти наилучший путь из вершины (i,j). Для каждой пары i,j получим одну задачу. При i=1 и j=1 получается исходная задача, которую нам нужно решить. '''Начнём решать эти задачи с простых: сначала для нижней строчки, затем второй снизу и так далее, пока не дойдём до самой верхней строчки треугольника'''.
Пусть значения чисел a(i,j) в треугольнике не хранятся в массиве, а быстро вычисляются некоторой внешней функцией от двух аргументов. Придумайте алгоритм, который использует память <math>\Theta(N)</math> и работает время <math>\Theta(N^2)</math>.
 
'''Подсказка''': В памяти достаточно хранить значения <math>(i,j)</math> для одной последней строчки — самой верхней из рассмотренных.
 
Эта задача показывает, что придумать рекурсивный алгоритм часто намного проще, чем не рекурсивный. Также несложно добавить к рекурсии запоминание вычисленных значений. Но нередко существует более быстрый алгоритм, основанный на динамическом программировании, который использует меньше памяти, нежели рекурсия с запоминанием, и делает в два раза меньше операций обращения к памяти.
1224

правки