Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет

им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Курсовая работа

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

Исполнитель:

Студентка группы М-31

Лубавина А.Ю.

Гомель 2007

Содержание

• Введение
• 1. Задача о Черепашке
• 2. Треугольник
• 3 Степень числа
• 4. Автозаправка
• 5. Алгоритм Нудельмана-Вунша
• 6. Разбиение выпуклого N-угольника
• 7. Задача о рюкзаке (динамическая схема)
• 8. Задача о паркете
• Заключение
• Литература

Введение

Динамическое программирование - один из методов решения задач оптимизации. Слово “программирование” здесь не имеет того значения, которое используется в информатике. В данном случае оно является производным от термина programme mathematique, обозначающего систему неравенств, которые надо решить.

1. Задача о Черепашке

Черепашке необходимо попасть из пункта А в пункт В. На каждом углу она может поворачивать только на север или только на восток. Время движения по каждой улице указано на рисунке. Требуется найти минимальное время, за которое Черепашка может попасть из пункта А в пункт В.

Путь, показанный на рисунке линиями со стрелкой, требует 21 единицу времени. Отметим, что каждый путь состоит из 6 шагов: трех на север и трех на восток. Количество возможных путей Черепашки 20 (С₆³ ). Мы можем перебрать все пути и выбрать самый быстрый. Это метод полного перебора (ответ - 21). Для вычисления каждого времени требуется пять операций сложения, а для нахождения ответа 100 операций сложения и 19 операций сравнения. Задача решается вручную. Однако при N, равном 8, у Черепашки уже 12870 путей. Подсчет времени для каждого пути требует 15 операций сложения, а в целом - 193050 сложений и 12869 сравнений, то есть порядка 200000 операций. Компьютер при быстродействии 1000000 операций в секунду найдет решение за 0.2 секунды, а человек? Предположим, что N равно 30, тогда количество различных путей 60!*(30!*30!). Это очень большое число, его порядок 10¹⁷. Количество операций, необходимых для поиска решения, равно 60*10¹⁷. Компьютер с быстродействием 1000000 операций в секунду выполнит за год порядка 3.2*10¹³ операций (подсчитайте). А сейчас не трудно прикинуть количество лет, требуемых для решения задачи.

Вернемся к исходной задаче. Начнем строить путь Черепашки от пункта В. Каждому углу присвоим вес, равный минимальному времени движения Черепашки от этого угла до пункта В. Как его находить? От углов X, Y очевидно. Для угла Z время движения Черепашки в пункт В через угол X 15 единиц, а через угол Y 11 единиц. Берем минимальный, то есть вес угла будет равен 11. Продолжим вычисления. Их результаты приведены на рисунке. Путь, отмеченный стрелками, является ответом задачи. Оценим количество вычислений. Для каждого угла необходимо выполнить не более двух операций сложения и одной операции сравнения, то есть три операции. При N, равном 300, количество операций - 3*301*301, это меньше 1000000, и компьютеру потребуется меньше одной секунды. Итак, много лет при N=30 и 1 секунда при N=300.

Идея второго способа решения задачи основана на методе динамического программирования. Заслуга его открытия принадлежит американскому математику Ричарду Беллману. Выделим особенность задачи, которая позволяет решить ее описанным способом. Мы начинаем с угла В, и для каждого угла найденное число является решением задачи меньшей размерности. Поясним эту мысль. Если бы мы решали задачу поиска пути Черепашки из пункта Т в пункт В, то найденное число 17 - решение задачи. Для каждого угла найденное значение времени не изменяется и может быть использовано на следующих этапах.

2. Треугольник

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

				7
			3		8
		8		1		0
	2		7		4		4
4		5		2		6		5

Каждый шаг на пути может осуществляться вниз по диагонали влево

7 0 0 0 0

3 8 0 0 0

8 1 0 0 0

2 7 4 4 0

4 5 2 6 5

или вниз по диагонали вправо.

Число строк в треугольнике > 1 и <100.

Треугольник составлен из целых чисел от 0 до 99.

Рассмотрим идею решения на примере, приведенном в тексте задачи. Входные данные запишем в матрицу D. Она, для примера, имеет вид:

Будем вычислять матрицу R:array[1..MaxN,0..MaxN+1] следующим образом, предварительно обнулив ее элементы:

R[1,1]=D[1,1]

R[i,j]=max(D[i,j]+R[i-1,j],D[i,j]+R[i-1,j-1])

для i=2..N; j=1..i.

Ее вид:

0 7

0 10 15

0 18 16 15

0 20 25 20 19

0 24 30 27 26 24

Осталось найти наибольшее значение в последней строке матрицы R. Итак, в решении задачи используются идеи метода динамического программирования.

3. Степень числа

Даны два натуральных числа n и k. Требуется определить выражение, которое вычисляет kⁿ . Разрешается использовать операции умножения и возведения в степень, круглыми скобками и переменной с именем k.Умножение считается одной операцией, возведению в степень q соответствует q-1 операция. Найти минимальное количество операций, необходимое для возведения в степень n. Желательно сделать это для как можно больших значений n.

Пример. При n=5 необходимо три операции - (k*k)²*k.

Определим массив Op, его элемент Op[i] предназначен для хранения минимального количества операции при возведении в степень i (Op[1]=0). Для вычисления выражения, дающего n-ю степень числа k, арифметические операции применяют в некоторой последовательности, согласно приоритетам и расставленным скобкам. Рассмотрим последнюю примененную операцию. Если это было умножение, тогда сомножителями являются натуральные степени числа k, которые в сумме дают n. Степень каждого из сомножителей меньше n, и ранее вычислено, за какое минимальное число операций ее можно получить. Итак:

opn1:=min{по всем p:1p<n, Op[p]+Op[n-p]+1}.

Если это возведение в степень:

opn2:=min{ для всех p (1) - делителей n, Op[n div p]+p-1}.

Результат - Op[n]=min(opn1,opn2). Фрагмент реализации:

......

Op[1]:=0;

for n:=2 to ???? do begin

opn:=n;{opn - рабочая переменная}

for p:=1 to n-1 do begin

opn:=Min(opn,Op[p]+Op[n-p]+1);{Min - функция поиска минимума двух чисел}

if (n mod p=0) and (p<>1) then opn:=Min(opn,Op[n div p]+p-1);

end;

Op[n]:=opn;

end;

4. Автозаправка

Вдоль кольцевой дороги расположено m городов, в каждом из которых есть автозаправочная станция. Известна стоимость Z[i] заправки в городе с номером i и стоимость C[i] проезда по дороге, соединяющей i - й и (i+1)-й города, C[m] - стоимость проезда между первым и m-м городами. Для жителей каждого города определить город, в который им необходимо съездить, чтобы заправиться самым дешевым образом, и направление - «по часовой стрелке» или «против часовой стрелки», города пронумерованы по часовой стрелке. Не будем рассматривать переборный вариант решения задачи, суть которого в проверке всех 2*m вариантов для жителей каждого города, итого - 2*m*m проверок. Введем два дополнительных массива

On, Ag: array[1..m] of record wh, qh:integer; end; .

On[i] означает, где следует заправляться (wh) и стоимость заправки (qh) жителям i-го города, если движение разрешено только по часовой стрелке. В этом случае жители города i имеют две альтернативы: либо заправляться у себя в городе, либо ехать по часовой стрелке. Во втором случае жителям города i надо заправляться там же, где и жителям города i+1, или в первом, если i=m. Итак, On[i]=min{Z[i],C[i]+On[i+1].qh}. Откуда известно значение On[i+1].qh? Необходимо найти город j с минимальной стоимостью заправки - On[j]:=(j,Z[j]). После этого можно последовательно вычислять значения On[j-1], On[j-2], ..., On[j+1]. Аналогичные действия необходимо выполнить при формировании массива Ag[i], после этого для жителей каждого города i следует выбрать лучший из On[i].qh и Ag[i].qh вариант заправки.

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

Пример из молекулярной биологии. Молекулы ДНК, содержащие генетическую информацию - это длинные слова из четырех букв (А, Г, Ц, Т). В процессе эволюции, в результате мутаций, последовательности меняются, одна буква может замениться на другую, выпасть, а может добавиться новая. Насколько похожи два фрагмента, каким наименьшим числом превращений можно один из них получить из другого? Формулировка задачи. Даны два слова (длины M и N), состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово.

Пример. Слова ГЦАТАГГТЦ и АГЦААТГГТ. Схема решения иллюстрируется следующим рисунком.

На рисунке закрашены клетки, в строке и в столбце которых находятся одинаковые буквы. Принцип заполнения таблицы W следующий: элемент W[i,j] равен наибольшему из чисел W[i-1,j], W[i,j-1], а если клетка <i,j> закрашена, то и W[i-1,j-1]+1. Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,1] - первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. Путь - это клетки с метками, отличающимися на единицу, буквы из закрашенных клеток выписываются. Последовательность этих букв - ответ задачи. Для нашего примера две подпоследовательности: ГЦААГГТ и ГЦАТГГТ.

Фрагмент основной логики.

...

for i:=1 to Length(S1) do

for j:=1 to Length(S2) do begin

A[i,j]:=Max(A[i-1,j],A[i,j-1]);

if S1[i]=S2[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1);

end;

Writeln(`Ответ: ',A[Length(S1),Length(S2)]);

....

6. Разбиение выпуклого N-угольника

Дан выпуклый N-угольник, заданный координатами своих вершин в порядке обхода. Он разрезается N-2 диагоналями на треугольники. Стоимость разрезания определяется суммой длин всех использованных диагоналей. Найти разрез минимальной стоимости.

Идея решения разбирается с использованием следующего рисунка.

Обозначим через S[k,l] стоимость разрезания многоугольника A[k,l] диагоналями на треугольники. При l=k+1 или k+2 S[k,l]=0, следовательно, l>k+2. Вершина с номером i, i изменяется от k+1 до l-1, определяет какое-то разрезание многоугольника A[k,l]. Cтоимость разрезания определим как:

S[k,l]=min{длина диагонали <k,i>+длина диагонали <i,l>+S[k,i]+S[i,l]}. При этом следует учитывать, что при i=k+1 диагональ <k,i> является стороной многоугольника и ее длина считается равной нулю.

Пример(N=6).



7. Задача о рюкзаке (динамическая схема)

Рассмотрим задачу из пункта 1.1.6. Напомним ее формулировку. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака не превышает W.

Каждый предмет типа i имеет вес w_i и стоимость v_i (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k_i, тогда требуется максимизировать v₁*k₁+v₂*k₂+...+v_n*k_n при ограничениях w₁*k₁+w₂*k₂+...+w_n*k_nW, где k_i - целые (0k_i[W/w_i]), квадратные скобки означают целую часть числа.

Пусть вес рюкзака должен быть равен W. Формализуем задачу следующим образом.

Шаг i ставится в соответствие типу предмета i=1,2,...,n.

Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах 0,1,...,i. При этом y_n=W, y_i=0,1,...,W при i=1,2,...,n-1.

Варианты решения k_i на шаге i описываются количеством предметов типа i, 0k_iW/w_i.

Рассмотрим пример. W=6, и дано четыре предмета

i	wi	vi
1	2	50
2	3	90
3	1	30
4	4	140

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

Текст решения.

Const MaxN=???;

MaxK=???;

Type Thing=Record W,V:Word; end;

Var A:array[1..MaxN,0..MaxK] of word;

P:array[1..MaxN] of Thing;

Old,NewA:array[0..MaxK] of longint;

N,W:integer;

...

procedure Solve;

var k,i,j:integer;

begin

fillchar(Old,sizeof(Old),0);

for k:=1 to N do begin{цикл по шагам}

fillchar(NewA,sizeof(NewA),0);

for i:=0 to W do {цикл по состояниям шага}

for j:=0 to i div P[k].W do {цикл по вариантам решения - количеству предметов каждого вида}

if j*P[k].V+Old[i-j*P[k].W]>=NewA[i] then begin

NewA[i]:=j*P[k].V+Old[i-j*P[k].W];

A[k,i]:=j;{здесь j количество предметов?}

end;

Old:=NewA;

end;

end;

Вывод наилучшего решения.

procedure OutWay(k,l:integer);

begin

if k=0 then exit

else begin

OutWay(k-1,l-A[k,l]*P[k].V);{а здесь вес}

Write(A[k,l],' `);

end;

end;

Первый вызов - OutWay(N,W). Эту схему реализации принято называть «прямой прогонкой». Ее можно изменить. Пусть пункт два формализации задачи звучит следующим образом. Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах i, i+1, ..., N при этом y₁=W y_i=0,1,...,W при i=2,3, ...,N. В этой формулировке схему реализации называют «обратной прогонкой».

8. Задача о паркете

Комнату размером n*m единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (m20, n8, m,n -целые). Пол можно покрыть паркетом различными способоми. Например, для m=2, n=3 все возможные способы укладки приведены на рисунке.

Требуется определить количество всех возможных способов укладки паркета для конкретных значений m20, n8. Результатом задачи является таблица, содержащая 20 строк и 8 столбцов.

Элементом таблицы является число, являющееся решением задачи для соответствующих n и m. На месте ненайденных результатов должен стоять символ «*».

Решение. Пусть i - длина комнаты (1i8), j - ширина комнаты (1j20). «Разрежем» комнату на части. Разрез проводится по вертикали. Плитки, встречающиеся на пути разреза, обходим справа, т.е. при движении сверху вниз на каждом шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсутствие обхода - 0. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число 00100011 (35). Количество различных сечений 2ⁱ (пронумеруем их от 0 до 2ⁱ-1), где i -длина комнаты.

Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой (k,j) комнату с фиксированной длиной i, правый край которой не ровный, а представляет собой сечение с номером k. B[k,j] - количество вариантов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению B[0,j] - количество укладок паркета в комнате размером (i,j) с ровным правым краем. Считаем, что B[0,0]=1 при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается паркетом, при этом не используется ни одной плитки. Кроме этого считаем B[k,0]=0 для всех сечений с номерами k<>0, так как ненулевые сечения при нулевой ширине нельзя реализовать.

Попытаемся найти B[k,j] для фиксированного i. Предположим, что нам известны значения B[l,j-1] для всех сечений с номерами l (0l2ⁱ-1). Сечение l считаем совместимым с сечением k, если путем добавления целого числа плиток паркета из первого можно получить второе. Тогда B[k,j]=B[l,j-1], суммирование ведется по всем сечениям l, совместимым с сечением k. Налицо динамическая схема решения задачи. Оставляя пока в стороне вопрос совместимости сечений, «набросаем» логику решения.

Данные.

var B:array[0..255,0..20] of Comp;

A:array[1..8,1..20] of Comp;{Результирующая таблица}

function St2(k:integer):integer;{Вычисляем k - ю степень 2}

begin

if k<=0 then St2:=1 else St2:=2*St2(k-1);

end;

procedure Solve;{Основная логика}

var i,j,k,l,max:integer;

begin

for i:=1 to 8 do begin {Цикл по значению длины комнаты}

max:=St2(i)-1;

fillchar(B,sizeof(B),0);

B[0,0]:=1;

for j:=1 to 20 do begin {Цикл по значению ширины комнаты}

for k:=0 to max do {Сечение с номером k}

for l:=0 to max do{Сечение с номером l}

if Can(k,l,i) then B[k,j]:=B[k,j]+B[l,j-1];{Совместимость сечений «зарыта» в функции Can(k,l,i)}

A[i,j]:=B[0,j];

end;

end;

end;

Остался открытым вопрос о совместимости сечений. В этом случае необходимо различать понятия совместимость сечений в целом и совместимость в отдельном разряде. При анализе последнего входными данными являются значения разрядов сечений и информация о предыстории процесса (до текущего разряда) - целое или нецелое количество плиток уложено (значение переменной b). Выходными данными - признак - целое, нецелое количество плиток, требуемых для перевода сечения l в сечение k, или решение о том, что анализ продолжать не следует - сечения несовместимы. В данном случае этапу написания логики предшествует анализ на бумаге. Пример этой работы приведен в таблице.

Таблица

l	k	Значе-ние b	Новое значе- ние b или резуль- тат	Примечания
1	0	false	false	До данного разряда уложено целое число плиток. Для перехода от l к k не надо ничего укладывать. Переходим к следующему разряду.
1	0	true	несовмести-мы	До этого разряда уложено нецелое число плиток, а на этом «закрываем доступ». Сечения несовместимы.
0	1	false	false	Укладываем целую плитку, количество уложенных плиток остается целым.
0	1	true	несовмести-мы	Для перехода к новому сечению в этом разряде необходимо уложить целую плитку. Однако, укладывая её мы «перекрываем» доступ к нецелой плитке, уложенной до этого.
0	0	false	true	До этого разряда между сечениями было уложено целое число плиток, а на этом можно уложить только полплитки.
0	0	true	false	Нецелую плитку дополняем до целой.
1	1	false	несовмести-мы	В этом разряде l лежит целая плитка. Необходимо уложить целую плитку для того, чтобы была 1 в этом разряде сечения k, но сделать этого мы не можем. Аналогично и для случая, когда b=true.

Данный анализ совместимости сечений реализован в функции Can.

function Can(k,l,pi:byte):boolean;{k,l -номера сечений, pi - количество анализируемых разрядов сечений}

var i,d:integer;b:boolean;

begin

Can:=false;b:=false;

for i:=1 to pi do begin

d:=St2(i);

if k and d =0 then{определяется значение разряда с номером d для сечения k}

if l and d =0 then b:=not(b)

else begin if b then exit end

else if (l and d<>0) or b then exit

end;

Can:=not(b);

end;

Осталось сделать еще несколько замечаний. Во-первых, если произведение n на m нечетно (размеры комнаты), то количество укладок паркетом такой комнаты равно 0. Во-вторых, при m=1 и четном n ответ равен 1. В-третьих, результирующая таблица симметрична относительно главной диагонали. В-четвертых, для комнат размером 2*t достаточно просто выводится следующая рекуррентная формула: A[2,t]=A[2,t-1]+A[2,t-2] (ряд Фибоначчи). Эти замечания реализуются на этапе предварительной обработки и приводят к незначительной модификации логики процедуры Solve. Еще одно замечание касается точности результата. Для больших значений n и m необходимо организовать вычисления с использованием длинной арифметики. Мы ограничимся маленькой хитростью - просто выпишем результат при выводе результирующей матрицы.

...

for i:=1 to 20 do begin

for j:=1 to 8 do

if (i=8) and (j=20) then write(`3547073578562247994':20)

else write(A[j,i]:20);

writeln;

end;

Заключение

Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.

Литература

Ахо А.,Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов.-М.:Мир,1979.

Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи.-М.:Мир, 1982.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика.-М.:Мир,1980.

4. Суханов А.А. Олимпиадные задачи. Неопубликованный материал. - СПб.: 1996.