Динамическое программирование

Тема: Рекурсивные алгоритмы. Динамическое программирование.

Цель работы.

Исследование рекурсивных программ и структур данных, общие подходы к реализации рекурсивных программ: “разделяй и властвуй”, динамическое программирование.

 

Рекурсивный алгоритм — это алгоритм, решающий задачу путем решения одного или нескольких более узких вариантов той же задачи. Для реализации рекурсивных алгоритмов используются рекурсивные функции — функции, которые вызывают самих себя. Рекурсивные функции в C++ соответствуют рекурсивным определениям математических функций.

Программа 5.1. Функция вычисления факториала (рекурсивная реализация).

int factorial(int N)

{

if (N == 0) return 1;

return N*factorial(N-1);

}

Эта рекурсивная функция вычисляет функцию N!, используя стандартное рекурсивное определение. Она возвращает правильное значение, когда вызывается с неотрицательным и достаточно малым аргументом N, чтобы N! можно было представить типом int.

Рекуррентные отношения являются рекурсивно определенными функциями. Рекуррентное отношение задает функцию, областью допустимых значений которой являются неотрицательные числа, определяемые либо некоторыми начальными значениями, либо (рекурсивно) множеством ее собственных значений, полученных на основе меньших целых значений. Вероятно, наиболее известной из таких функций является функция вычисления факториала, которая определяется рекуррентным отношением

N! = N∙ (N- 1)!, для N ≥ 1, причем 0! = 1

Это определение непосредственно соответствует рекурсивной функции C++ в программе 5.1.

Программа 5.1 эквивалентна простому циклу. Например, следующий цикл for выполняет такое же вычисление:

for(t = 1, i = 1; i <= N; i++) t *= i;

 

В языках программирования, подобных C++, существует очень мало ограничений для видов создаваемых программ, но, как правило, использование рекурсивных функций ограничивается теми, которые позволяют проверять правильность своей работы методом математической индукции. Необходимо удостовериться, что создаваемые рекурсивные функции удовлетворяют двум основным условиям:

· Они должны явно решать задачу для исходного значения.

· В каждом рекурсивном вызове должны использоваться меньшие значения аргументов.

Эти утверждения являются спорными — они равнозначны тому, что мы должны располагать допустимой индуктивной проверкой для каждой создаваемой рекурсивной функции. Тем не менее, они служат полезным руководством при разработке реализаций.

Программа 5.2 — компактная реализация алгоритма Евклида для отыскания наибольшего общего делителя для двух целых чисел. Алгоритм основывается на наблюдении, что наибольший общий делитель двух целых чисел x и у, когда х > у, совпадает с наибольшим общим делителем числа у и х по модулю у (остатка от деления x на у). Число t делит и х и у тогда, и только тогда, когда оно делит и у и х mod у (х по модулю у), поскольку x равно х mod у плюс число, кратное у. Рекурсивные вызовы, созданные для примера выполнения этой программы, показаны на рис. 5.2. При реализации алгоритма Эвклида глубина рекурсии зависит от арифметических свойств аргументов (она связана с ними логарифмической зависимостью).

Программа 5.2 Алгоритм Эвклида — рекурсивный метод отыскания наибольшего общего делителя двух целых чисел.

int gcd(int m, int n)

{

if (n == 0) return m;

return gcd(n, m%n);

}

Программа 5.3 — пример с несколькими рекурсивными вызовами. Она оценивает другое выражение, по существу выполняя те же вычисления, что и программа 4.1 из лабораторной работы №4, но применительно к префиксным (а не постфиксным) выражениям, используя рекурсию вместо явного стека. Существует множество других примеров использования рекурсивных и эквивалентных программ, в которых задействуются стеки. Конкретная взаимосвязь между несколькими парами таких программ исследуется достаточно подробно.

char *a; int i;

int eval()

{

int x = 0;

while(a[i] == ' ') i++;

if (a[i] == '+')

{

i++;

return eval() + eval();

}

if (a[i] == '*')

{

i++;

return eval() * eval();

}

while((a[i] >= '0') && (a[i] <= '9'))

x = 10*x + (a[i++] - '0');

return x;

}

Рисунок 5.1 – пример оценки префиксного выражения

Эта вложенная последовательность вызовов функций иллюстрирует работу рекурсивного алгоритма оценки префиксного выражения для конкретного примера выражения.

В принципе, любой цикл for можно заменить эквивалентной рекурсивной программой. Часто рекурсивная программа предоставляет более естественный способ выражения вычисления, чем цикл for, поэтому можно воспользоваться преимуществами механизма, предоставляемого системой, поддерживающей рекурсию. Однако, этот подход имеет один скрытый недостаток, о котором следует помнить. При выполнении рекурсивной программы вызовы функций вкладываются один в другой, пока не будет достигнута точка, когда вместо рекурсивного вызова выполняется возврат. В большинстве сред программирования такие вложенные вызовы функций реализуются с помощью эквивалента встроенных стеков. Глубина рекурсии — это максимальная степень вложенности вызовов функций в ходе вычисления. В общем случае глубина будет зависеть от вводимых данных. При использовании рекурсивной программы следует учитывать, что среда программирования должна поддерживать стек, размер которого пропорционален глубине рекурсии. При решении сложных задач необходимый для этого стека объем памяти может заставить отказаться от использования рекурсивного решения.

Структуры данных, построенные из узлов с указателями, рекурсивны изначально. Например, определение связных списков является рекурсивным. Следовательно, рекурсивные программы предоставляют естественные реализации для многих часто используемых функций, работающих с такими структурами данных. Программа 5.4 содержит четыре примера. Подобные реализации гораздо проще понять, чем их нерекурсивные аналоги. Однако, рекурсивные программы, подобные программе 5.4, следует использовать обдуманно при обработке очень больших списков, поскольку глубина рекурсии может быть пропорциональна длине списков и, соответственно, требуемый для рекурсивного стека объем памяти может превысить допустимые пределы.

Программа 5.4 Примеры рекурсивных функций для связных списков.

Эти рекурсивные функции для выполнения простых задач обработки списков легко выразить, но они могут быть бесполезны для очень больших списков, поскольку глубина рекурсии может быть пропорциональна длине списка.

Первая функция count подсчитывает количество узлов в списке. Вторая, traverse, вызывает функцию visit для каждого узла списка, с начала до конца. Обе функции легко реализуются с помощью цикла for или while. Третья функция traverseR не имеет простого итеративного аналога. Она вызывает функцию visit для каждого узла списка, но в обратном порядке.

Четвертая функция remove удаляет из списка все узлы с заданным значением элемента. Основа реализации этой функции — изменение связи х = x->next в узле, предшествующем удаляемому, что возможно благодаря использованию параметра ссылки.

int count(link x)

{

if (x == 0) return 0;

return 1 + count(x->count)

}

void traverse(link h, void visit(link))

{

if (h == 0) return;

visit(h);

traverse(h->next, visit);

}

void traverseR(link h, void visit(link))

{

if (h == 0) return;

traverseR(h->next, visit);

visit(h);

}

void remove(link &x, Item v)

{

while(x!=0 && x->item == v)

{

link t = x;

x = x->next;

delete t;

}

if(x!= 0)

remove(x->next, v);

}

 

Разделяй и властвуй

Во множестве рекурсивных программ используется два рекурсивных вызова, каждый из которых работает приблизительно с половиной входных данных.

Эта рекурсивная схема — вероятно, наиболее важный случай хорошо известного метода "разделяй и властвуй" разработки алгоритмов, который служит основой для важнейших алгоритмов.

Давайте в качестве примера рассмотрим задачу отыскания максимального из N элементов, сохраненных в массиве а[0],..., a[N-l]. Эту задачу можно легко выполнить за один проход массива демонстрируется в примере:

for (t = a[0], i = 1; i < N; i++)

if (a[i] > t) t = a[i];

Рекурсивное решение типа "разделяй и властвуй", приведенное в программе 5.5 - еще один простой (хотя и совершенно иной) алгоритм решения той же задачи; он использовался только с целью иллюстрации концепции "разделяй и властвуй".

Программа 5.5 Применение алгоритма "разделяй и властвуй" для отыскания максимума

Эта функция делит массив а[l],..., а[r] на массивы а[l],…, а[m] и а[m+1] а [r], находит максимальные элементы в обоих частях (рекурсивно) и возвращает больший из них в качестве максимального элемента всего массива. В программе предполагается, что Item — тип первого класса, для которого операция > определена(например, int).

Если размер массива является четным числом, обе части имеют одинаковые размеры, если же нечетным, эти размеры различаются на 1.

Item max (Item a[], int l, int r)

{

if (A == r) return a[l];

int m = (l+r)/2;

Item u = max (a, l, m);

Item v = max (a, m+1, r);

if (u > v) return u; else return v;

}

Рисунок 5.2 - рекурсивный подход к решению задачи отыскания максимума

Рисунок 5.3 - рекурсивная структура алгоритма поиска максимума

Алгоритм "разделяй и властвуй" разделяет представляющий задачу массив, размер которого равен 11, на массивы с размерами 6 и 5, массив с размером 6 — на два массива с размерами 3 и т.д., пока не будет получен массив с размером 1 (верхний). Каждая окружность на этих схемах представляет вызов рекурсивной функции для расположенных непосредственно под ней узлов, связанных с ней линиями (квадраты представляют вызовы, для которых рекурсия завершается). На схеме в центре показано значение индекса в середине файла, который использовался для выполнения разделения; на нижней схеме показано возвращаемое значение.

 

Ни одно рассмотрение рекурсии не было бы полным без рассмотрения старинной задачи о ханойских башнях. Имеется три стержня и N дисков, которые помещаются на трех стержнях. Диски различаются размерами и вначале размещаются на одном из стержней от самого большого (диск N внизу до самого маленького (диск 1) вверху. Задача состоит в перемещении дисков на соседнюю позицию (стержень) при соблюдении следующих правил: (i) одновременно можно перемещать только один диск; и (ii) ни один диск не может быть помещен поверх диска меньшего размера. Программа 5.7 предоставляет рекурсивное решение этой задачи. Программа указывает диск, который должен быть сдвинут на каждом шагу, и направление его перемещения (+ означает перемещение на один стержень вправо с переходом к крайнему слева стержню при достижении крайнего справа стержня, а — означает перемещение на один стержень влево с переходом к крайнему справа стержню при достижении крайнего слева стержня). Рекурсия основывается на следующей идее: для перемещения N дисков вправо на один стержень вначале верхние N— 1 дисков нужно переместить на один стержень влево, затем переместить диск N на один стержень вправо, после чего еще раз переместить N — 1 дисков на один стержень влево (поверх диска N). В правильности работы этого решения можно удостовериться методом индукции. На рис. 5.4 показаны перемещения для N = 5 и рекурсивные вызовы для N = 3. Структура алгоритма достаточно очевидна; давайте рассмотрим его подробно.

Программа 5.6. Решение задачи о ханойских башнях

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

void hanoi (int N, int d)

{

if (N = 0) return;

hanoi(N-l, -d);

shift(N, d);

hanoi(N-l, -d);

}

 

 

Рисунок 5.4 – Ханойские башни

На этой схеме отображено решение задачи о ханойских башнях для случая с пятью дисками. Мы сдвигаем четыре верхних диска влево на одну позицию (левый столбец), затем перемещаем диск 5 вправо, а затем верхние четыре диска перемещаем влево на одну позицию (правый столбец). Приведенная ниже последовательность вызовов функций образует вычисление для трех дисков. Вычисленная последовательность перемещений — +1 -2 +1 +3+1-2+1 появляется в решении четыре раза (для примера показано первых семь перемещений).

 

Чтобы понять решение задачи о ханойских башнях, давайте рассмотрим простую задачу рисования меток на линейке. Каждые 1/2 дюйма на линейке отмечаются черточкой, каждые 1/4 дюйма отмечаются несколько более короткими черточками, 1/8 дюйма — еще более короткими и т.д. Задача состоит в создании программы для рисования этих меток при любом заданном разрешении, при условии, что в нашем распоряжении имеется процедура mark(x, h) для рисования меток высотой h условных единиц в позиции х.

 

Если требуемое разрешение равно 1/2" дюймов, давайте изменим масштаб, чтобы задача состояла в помещении метки в каждой точке в интервале от 0 до 2", за исключением конечных точек. Таким образом, средняя метка должна иметь высоту п условных единиц, метки в середине левой и правой половин должны иметь высоту n — 1 условных единиц и т.д.

Программа 5.7 — простой алгоритм "разделяй и властвуй" для выполнения этой задачи; работа данного алгоритма применительно к небольшому примеру проиллюстрирована на рис.5.5. С точки зрения рекурсии в основе метода лежит следующая идея. Для помещения меток на интервале, последний вначале делится на две равные половины. Затем создаются метки (более короткие) в левой половине (рекурсивно), помещается длинная метка в середине и рисуются метки (более короткие) в правой половине (рекурсивно). Если говорить об итерации, рис. 5.5 иллюстрирует, что с помощью этого метода метки создаются по порядку, слева направо — фокус заключается в вычислении длин интервалов. Дерево рекурсии, приведенное на рисунке, помогает понять вычисление: просматривая его сверху вниз, мы видим, что длина меток уменьшается на 1 для каждого вызова рекурсивной функции. Если просматривать дерево в поперечном направлении, мы получаем метки в том порядке, в каком они рисуются, поскольку для каждого данного узла вначале рисуются метки, связанные с вызовом функции слева, затем метка, связанная с данным узлом, а затем метки, связанные с вызовом функции справа.

 

Рисунок 5.8 - Вызовы функций, рисующих линейки

Программа 5.7.

void rule (int l, int r, int h)

{

int m = (l+r)/2;

if (h > 0)

{

rule(l, m, h-1);

mark(m, h);

rule(m, r, h-1);

}

}

Программа 5.8 представляет альтернативный способ рисования линейки, на который натолкнуло соответствие с двоичными числами. Эту версию алгоритма называют восходящей (bottom-up) реализацией. Она не является рекурсивной, но определенно навеяна рекурсивным алгоритмом. Это соответствие между алгоритмами типа "разделяй и властвуй" и двоичными представлениями чисел часто способствует углубленному пониманию при анализе и разработке усовершенствованных версий, таких как восходящие подходы. Данную возможность следует учитывать, чтобы понять и, возможно, усовершенствовать каждый из исследуемых алгоритмов типа "разделяй и властвуй".

Программа 5.8 Не рекурсивная программа для рисования линейки

void rule (int l, int r, int h)

{

for (int t = l, j = l; t <= h; j += j, t++)

for (int i = 0; l+j+i <= r; i += j+j)

mark(l+j+i, t);

}

Рисунок 5.9 - Рисование линейки в восходящем порядке

Восходящий подход соответствует общему методу разработки алгоритмов, при котором задача решается путем решения вначале элементарных подзадач с последующим объединением этих решений для получения решения несколько больших подзадач и т.д., пока вся задача не будет решена. Подобный подход можно было бы назвать подходом "объединяй и властвуй".

Динамическое программирование

Главная особенность алгоритмов типа "разделяй и властвуй" — разделение ими задачи на независимые подзадачи. Когда подзадачи не являются независимыми, ситуация усложняется, в первую очередь потому, что непосредственная рекурсивная реализация даже простейших алгоритмов этого типа может требовать неприемлемо больших затрат времени.

Программа 5.9 — непосредственная рекурсивная реализация рекуррентного соотношения, определяющего числа Фибоначчи.

int F(int i)

{

if (i < 1) return 0;

if (i == 1) return 1;

return F(i-1) + F(i-2);

}

 

Не используйте эту программу — она весьма неэффективна. Действительно, количество рекурсивных вызовов для вычисления F_N равно F_N+1. Но F_N приближенно равно ф^N, где ф ~ 1,618 — золотая пропорция. Как это ни удивительно, но для программы 5.9 время этого элементарного вычисления определяется экспоненциальной зависимостью. Рисунок 5.10, на котором приведены рекурсивные вызовы для небольшого примера, весьма наглядно демонстрирует требуемый объем повторных вычислений.

Рисунок 5.10 - структура рекурсивного алгоритма для вычисления чисел фибоначчи

Схема рекурсивных вызовов для вычисления F_N no стандартному рекурсивному алгоритму иллюстрирует, как рекурсия с перекрывающимися подзадачами может приводить к экспоненциальному возрастанию затрат. В данном случае второй рекурсивный вызов игнорирует вычисление, выполненное во время первого вызова, что приводит к значительным повторным вычислениям, поскольку эффект нарастает в геометрической прогрессии с увеличением количества рекурсивных вызовов.

И напротив, можно легко вычислить первые N чисел Фибоначчи за время, пропорциональное значению N, используя следующий массив:

F[0] = 0; F[1] = 1;

for(i = 2; i <= N; i++)

F[i] = F[i-1] + F[i-2]

 

Этот подход предоставляет непосредственный способ получения численных решений для любых рекуррентных соотношений. В случае с числами Фибоначчи можно даже обойтись без массива и ограничиться только первыми двумя значениями; для многих других часто встречающихся рекуррентных соотношений необходимо поддерживать массив, хранящий все известные значения.

Рекуррентное соотношение — это рекурсивная функция с целочисленными значениями. Рассуждения, приведенные в предыдущем абзаце, подсказывают, что любую такую функцию можно приближенно вычислить, вычисляя все значения функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Эта технология называется восходящим динамическим программированием (bottom-up dynamic programming). Она применима к любому рекурсивному вычислению при условии, что мы можем себе позволить хранить все ранее вычисленные значения. Такая технология разработки алгоритмов успешно используется для решения широкого круга задач. Поэтому следует уделить внимание простой технологии, которая может изменить зависимость времени выполнения алгоритма от значения аргументов с экспоненциальной на линейную!

Нисходящее динамическое программирование (top-down dynamic programming) — еще более простая технология, которая позволяет автоматически выполнять рекурсивные функции при том же (или меньшем) количестве итераций, что и восходящее динамическое программирование. При этом рекурсивная программа используется для сохранения каждого вычисленного ею (в качестве заключительного действия) значения и для проверки сохраненных значений во избежание повторного вычисления любого из них (в качестве первого действия). Программа 5.10 — механически измененная программа 5.9, в которой за счет применения нисходящего динамического программирования достигается снижение времени выполнения — его зависимость от размера входного массива становится линейной. Рисунок 5.11 служит иллюстрацией радикального уменьшения количества рекурсивных вызовов, достигнутого посредством этого простого автоматического изменения. Иногда нисходящее динамическое программирование называют также мемуаризацией (memoization).

Рисунок 5.11 - Применение нисходящего динамического программирования для вычисления чисел Фибоначчи

Из этой схемы рекурсивных вызовов, использованных для вычисления F₉ методом нисходящего динамического программирования, видно, как сохранение вычисленных значений снижает нарастание затрат с экспоненциального до линейного.

Программа 5.10 Числа Фибоначчи (динамическое программирование)

Сохранение вычисляемых значений в статическом массиве (элементы которого в C++ инициализируются 0) явным образом исключает любые повторные вычисления. int F(int i)

int F(int i)

{

static int knownF[maxN];

if (knownF[i]!= 0) return knownF[i];

int t = i;

if (i < 0) return 0;

if (i > 1) t = F(i-1) + F(i-2);

return knownF[i] = t;

}

В качестве более сложного примера давайте рассмотрим задачу о ранце: вор, грабящий сейф, находит в нем N видов предметов различных размеров и ценности, но имеет только небольшой ранец емкостью М, в котором может унести награбленное. Задача заключается в том, чтобы определить комбинацию предметов, которые вор должен уложить в ранец, чтобы общая стоимость похищенного оказалась наибольшей. Например, при наличии типов предметов, представленных на рис. 5.12, вор, располагающий ранцем, размер которого равен 17, может взять только пять (но не шесть) предметов А общей стоимостью равной 20 или предметы D и Е суммарной стоимостью равной 24 или предметы в одной из множества других комбинаций. Наша цель — найти эффективный алгоритм для определения максимума среди всех возможностей при любом заданном наборе предметов и вместимости ранца.

В рекурсивном решении задачи о ранце при каждом выборе предмета мы предполагаем, что можем (рекурсивно) определить оптимальный способ заполнения остающегося пространства в ранце. Для ранца размера cap, для каждого доступного типа элемента i определяется общая стоимость элементов, которые можно было бы унести, укладывая i-ый элемент в ранец при оптимальной упаковке остальных элементов. Этот оптимальный способ упаковки — просто способ упаковки, определенный (или который будет определен) для меньшего ранца размера
cap-items[i].size. В этом решении используется следующий принцип: оптимальные принятые решения в дальнейшем не требуют пересмотра. Как только установлено, как оптимально упаковать ранцы меньших размеров, эти задачи не требуют повторного исследования независимо от следующих элементов.

Рисунок 5.12 - Пример задачи о ранце

Входными данными примера задачи о ранце (вверху) являются емкость ранца и набор предметов различных размеров (которые представлены значениями на горизонтальной оси) и стоимости (значения на вертикальной оси). На этом рисунке показаны четыре различных способа заполнения ранца, размер которого равен 17; два из этих способов ведут к получению максимальной суммарной стоимости, равной 24.

Программа 5.11— прямое рекурсивное решение, основывающееся на приведенных рассуждениях. Эта программа также неприменима для решения встречающихся на практике задач, поскольку из-за большого объема повторных вычислений (см. рис. 5.13) время решения связано с количеством элементов экспоненциально. Но для решения проблемы можно автоматически задействовать нисходящее динамическое программирование, как показано в программе 5.12. Как и ранее, эта методика исключает все повторные вычисления.

Программа 5.11 Задача о ранце (рекурсивная реализация)

Аналогично тому, как мы предостерегали в отношении рекурсивного решения задачи вычисления чисел Фибоначчи, не следует использовать эту программу, поскольку для ее выполнения потребуется время, экспоненциально связанное с количеством элементов, и поэтому, возможно, даже небольшой задачи решение получить не удастся.

Тем не менее, программа представляет компактное решение, которое легко можно усовершенствовать (см. программу 5.13). В ней предполагается, что элементы являются структурами с размером и стоимостью, которые определены следующим образом

typedef struct { int size; int val; } Item;

кроме того, в нашем распоряжении имеется массив N элементов типа Item. Для каждого возможного элемента мы вычисляем (рекурсивно) максимальную стоимость, которую можно было бы получить, включив этот элемент в выборку, а затем выбираем максимальную из всех стоимостей.

int knap(int cap)

{

int i, space, max, t;

for (i = 0, max = 0; i < N; i++)

if ((space = cap-items[i].size) >= 0)

if ((t = knap(space) + items[i].val) > max)

max = t;

return max;

}

Рисунок 5.13 - рекурсивная структура алгоритма решения задачи о ранце.

Это дерево представляет структуру рекурсивных вызовов простого рекурсивного алгоритма решения задачи о ранце, реализованного в программе 5.11. Число в каждом узле представляет остающееся свободным пространство ранца. Недостатком алгоритма является то же экспоненциальное снижение производительности вследствие большого объема повторных вычислений, требуемых для решения перекрывающихся подзадач, которое рассматривалось при вычислении чисел Фибоначчи.

Программа 5.12 Задача о ранце (динамическое программирование)

Эта программа, которая представляет собой механически измененную программу 5.11, снижает с экспоненциальной до линейной зависимость времени выполнения от количества элементов. Мы просто сохраняем любые вычисленные значения функции, а затем вместо выполнения рекурсивных вызовов получаем любые сохраненные значения, когда они требуются (используя зарезервированное значение для представления неизвестных значений). Индекс элемента сохраняется, поэтому при желании всегда можно восстановить содержимое ранца после вычисления: itemKnown[M] находится в ранце, остальное содержимое совпадает с оптимальной упаковкой ранца размера M-itemKnown[M].size, следовательно, itemKnown[M-items[M].size] находится в ранце и т.д.

int knap(int M)

{

int i, space, max, maxi = 0, t;

if (maxKnown[M]!= unknown) return maxKnown[M];

for (i = 0, max = 0; i < N; i++)

if ((space = M-items[i].size) >= 0)

if ((t = knap (space) + items [i].val) > max)

{ max = t; maxi = i; }

maxKnown[M] = max; itemKnown[M] = items[maxi];

return max;

}

Рисунок 5.14 - применение метода нисходящего динамического программирования для реализации алгоритма решения задачи о ранце

Подобно тому, как это было сделано для вычисления чисел Фибоначчи, методика с сохранением известных значений уменьшает нарастание затрат времени на выполнение алгоритма с экспоненциального до линейного.

 

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

Динамическое программирование уменьшает время выполнения рекурсивной функции до максимального значения, которое потребуется на вычисление функции для всех аргументов, которые меньше или равны данному аргументу, при условии, что стоимость рекурсивного вызова остается постоянной.

Применительно к задаче о ранце из этого следует, что время выполнения пропорционально произведению NM. Таким образом, задача о ранце легко поддается решению, когда емкость ранца не очень велика; для очень больших емкостей время и требуемый объем памяти могут оказаться недопустимо большими.

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

При использовании нисходящего динамического программирования известные значения сохраняются; при использовании восходящего динамического программирования они вычисляются заранее. В общем случае нисходящее динамическое программирование предпочтительней восходящего, поскольку

· оно представляет собой механическую трансформацию естественного решения задачи;

· порядок решения подзадач определяется сам собой;

· решение всех подзадач может не потребоваться.

Приложения, в которых применяется динамическое программирование, различаются по сущности подзадач и объему сохраняемой для них информации. Важный момент, которым нельзя пренебрегать, заключается в том, что динамическое программирование становится неэффективным, когда количество возможных значений функции, которые могут потребоваться, столь велико, что мы не можем себе позволить их сохранять (при нисходящем программировании) или вычислять предварительно (при восходящем программировании). Например, если в задаче о ранце М и размеры элементов — 64-разрядные величины или числа с плавающей точкой, мы не сможем сохранять значения путем их индексирования в массиве. Это несоответствие — не просто небольшое неудобство — оно создает принципиальные трудности. Для подобных задач пока не известно ни одного достаточно эффективного решения; имеются веские причины считать, что эффективного решения вообще не существует.

Динамическое программирование — это методика разработка алгоритмов, которая рассчитана в первую очередь для решения сложных задач того типа, который будет рассмотрен в следующих лабораторных работах.

Задания.

1. Напишите рекурсивную программу:

1) для чётных вариантов: вычисляющую значение постфиксного выражения;

2) для нечётных вариантов: вычисляющую значение инфиксного выражения, операнды всегда заключаются в круглые скобки.

2. Напишите рекурсивную программу:

1) для чётных вариантов: решающую задачу Иосифа;

2) для нечётных вариантов: удаляющую конечный узел из связного списка.

3. Напишите рекурсивную программу:

1) для чётных вариантов: вычисляющую длину i-ой метки на линейке с 2ⁿ-1 метками;

2) для нечётных вариантов: заполняющую массив размера n x 2ⁿ нулями и единицами таким образом, чтобы массив представлял все n-разрядные числа.

4. Напишите программу, которая использует:

1) для вариантов 3, 6, 9, …: восходящее динамическое программирование и вычисляет значение P_N:

,для N ≥ 1, P₀ = 0.

2) для вариантов2, 5, 8,…: восходящее динамическое программирование и вычисляет значение C_N:

, для N ≥ 1, C₀ = 1.

3) для вариантов1, 4, 7,…: нисходящее динамическое программирование и вычисляет значение биномиального коэффициента , исходя из рекурсивного соотношения

 

Содержание отчёта.

1. Цель работы.

2. Индивидуальное задание.

3. Описание структур данных и алгоритмов, используемых при выполнении индивидуального задания, для рекурсивных программ – примеры стека вызовов при небольших аргументах, как на рис.5.1.

4. Текст программы с комментариями – краткими описаниями функций, больших блоков кода, объявляемых данных. Как минимум, должно присутствовать описание действия, которое выполняет функция. Пример:

// АТД стека на базе массива

template <class Item>

class STACK

{

// указатель на буфер, в котором размещаются элементы

Item *s;

 

// указатель стека

int N;

public:

// конструктор - создание нового объекта типа STACK

STACK(int maxN = 1000)

{

s = new Item[maxN]; N = 0;

}

 

// проверка стека на пустоту

int empty() const

{

return N == 0;

}

}

5. Выводы по работе.