Лекции - Структуры и алгоритмы компьютерной обработки данных / 15.Динамическое программирование

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

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

Задача о черепашке

Задача о кратчайшем пути. Дана матрица MxN, в каждой клеточке - число очков. Из левого верхнего угла черепашка должна прийти в правый нижний. Перемещается черепашка только вниз и вправо. Найти путь с минимальной суммой очков.

12	9	4	14	8
7	12	10	7	15
11	13	14	18	5
19	8	7	15	12
3	16	3	9	19

Решение задачи

12	9		4		14		8
7	12		10		7		15
11	13		14		18		5
19	8		7		15		12
3	16		3		9		19

12	21	25	39	47
19	31	35	42	57
30	43	49	60	62
49	51	56	71	74
52	67	59	68	87

Dij= min{D(i-1)j,Di(j-1)}+Aij Ө(n2)

Рекурсивное восстановление пути

procedure Path(x,y:integer);

begin

if (x>1) or (y>1) then

begin

if (x=1) or ((y>1) and

(D[x,y-1]<D[x-1,y]))

then Path(x,y-1)

else Path(x-1,y);

end;

Writeln(x,’ ’,y);

end;

Ступеньки.

Дана лестница, состоящая из N ступенек. Мальчик может за один раз перепрыгнуть максимум М ступенек. Подсчитать количество способов спуска.

Решение задачи

Пусть s(n) – количество способов схода с лестницы.

s(n) = s(n-1)+s(n-2)+…+s(n-m-1) =

s(0)=1. θ(n2)

Пример. N=10, M=2.

0	1	2	3	4	5	6	7	8	9	10
1	1	2	4	7	13	24	44	81	149	274

Задача о наибольшей общей подпоследовательности (lcs)

Заданы два cлова A и B. Подпоследова-тельностью называется слово, которое получается из данного вычеркиванием одной или нескольких букв.

Найти подпоследовательность наибольшей длины, входящую и в то, и в другое слово.

Задача возникла в молекулярной биологии при анализе цепочек ДНК.

Алгоритм Нудельмана-Вунша

Пусть L[i,j] – длина НОП строк A[1..i] и B[1..j]. Тогда

Целочисленная задача о рюкзаке

Задан набор n предметов с целыми массами mi и стоимостями ci. Максимальная масса рюкзака – целое M. Выбрать подмножество предметов так, чтобы Σ mi ≤ M и Σ сi → max.

Динамическое программирование можно применять если в памяти можно разместить массив S[NxM]

Решение задачи

S[i,k] – максимальная стоимость набора из первых I предметов суммарной массой <=k