Динамично оптимиране, част II

Dynamic Programming, Part II

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

В предишната тема за динамично оптимиране (или динамично програмиране) се запознахме с основната идея на тази техника, как да "надушваме" такива задачи, как да смятаме сложността на решението ни, а също така и един лесен начин, по който да я прилагаме. Това е достатъчно за над половината задачи (може би дори в порядъка на 60-70%) от този тип, които ще срещнете, но все пак не покрива някои често-срещани разновидности.

В тази тема ще се запознаем с няколко по-сложни конструкции, които ще ви подготвят за голяма част от останалите възможни динамични. В следващата тема пък ще разгледаме по-интересни конструкции на стейта, като например битова маска и шаблон.

Итеративно динамично

В първата част споменахме, че има два основни начина, по които да се направи строенето на динамичната таблица. Единият от тях вече разгледахме - рекурсия, която мемоизираме. При него коментирахме, че едно от основните изисквания е стейтовете да не са циклични (тоест да не можем да стигнем от едно състояние до същото), тъй като това би могло да доведе до безкрайна рекурсия.
?Понякога ще видите итеративно динамично да бъде наричано "динамично програмиране", докато рекурсивното такова "динамично оптимиране". Да се прави такова разграничаване не е особено правилно, тъй като рекурсията също е вид програмиране, а итеративният вариант също оптимизира кода ни. Все пак имайте предвид, че някои автори ползват тази терминология.
Всъщност се оказва, че можем да използваме това свойство на стейтовете за да изградим изцяло итеративно решение. Казано в графови термини, можем да използваме ацикличността на графа на състоянията, за да направим тяхно топологично сортиране и да ги обходим в този ред, като така си гарантираме, че винаги ще сме изчислили нужните за текущия резултат други състояния. Това, макар формално и вярно, е по-сложно, отколкото какво се прави на практика. Реално не са ни нужни никакви графи или топология, за да направим динамичното си итеративно. Просто трябва по такъв начин да въртим няколко цикъла, че винаги вече да сме изчислили нужната информация за текущия стейт.

Итеративното динамично има няколко предимства. Първо, не е нужно да пишем рекурсия (за много хора тя е по-сложна от итерацията). Второ, можем съвсем точно да изчислим колко операции ще ни трябват и така да знаем (или засечем) точно колко бързо ще върви решението ни в най-лошия случай. Трето, в някои случаи (ако всички, или почти всички клетки от таблицата биват запълнени и при ползване на мемоизация) това решение би било малко по-бързо. Четвърто, в някои случаи при правилна имплементация това решение може да изисква по-малко памет.

Конструкция на итеративно динамично

За да направим решение, базирано на итеративно динамично, ще ни трябват няколко неща, доста от тях подобни, ако не еднакви, с тези, които ни трябваха и при рекурсивното такова.

Динамична таблица

Тук няма разлика - можем да ползваме същата динамична таблица, каквато ползвахме и при рекурсивния вариант.

Инициализация

Готиното е, че не е нужна предварителна инициализация на цялата таблица - нея можем да си я правим и вътре в циклите. Не е нужен и допълнителен масив, в който да пазим кои клетки вече сме пресметнали - начинът на обхождане ни гарантира, че клетката, която гледаме в момента, е "нова" (неизчислена).

Обхождащи цикли

Ще ни трябват един или няколко цикъла, с които да обходим стейтовете на динамичната таблица. Целта ни е да попълним цялата таблица, следователно е логично да имаме толкова цикъла, колкото е размерността й. Примерно за тримерно динамично ще ни трябват три цикъла.

Друг начин да си представите това е, че ще имаме толкова цикъла, колкото участващи в стейта аргумента бихме имали в рекурсивния вариант. Променливата във всеки от тези цикли е един от тези аргументи.
!Препоръчваме ви да кръщавате променливите, с които итерирате в обхождащите цикли, с нееднобуквени или достатъчно знаещи имена - примерно тези имена, които бихте ползвали в рекурсивния вариант. От една страна това ще направи много по-лесно ориентирането кое какво обхожда, а от друга ще си запазите кратките променливи от типа на i, c, j, или k за тялото на динамичното - тоест за цикли в най-вътрешния от обхождащите.
Обхождащите цикли са нещо като обвивка на същинското тяло на динамичното. Единственото, което правят те, е да определят какъв е текущият стейт. Така в най-вътрешния от тях все едно току-що сме влезли в тялото на рекурсията от мемоизирания вариант. Забележете, че това не ни гарантира, че това ще са единствените цикли, които имаме. Ако в рекурсивния вариант сме имали цикли, тях ще трябва да сложим допълнително в най-вътрешния от обхождащите такива. В следващата секция ще разгледаме по-подробно това.

Същинско тяло

Вече сме в най-вътрешния от обхождащите цикли. В този момент се намираме точно там, където бихме били в самото начало на рекурсията в мемоизирания вариант. Аргументите на функцията (поне значещите за стейта) са променливите от обхождащите цикли.

Всъщност, същинското тяло на динамичното е доста сходно на тялото на рекурсията. Все пак и двете вършат една и съща работа, логично е да са подобни. И тук трябва да се справим с:
  1. Частните случаи;
  2. Изчисляването на текущата клетка;
  3. Попълването на намерената стойност в динамичната таблица.

Тук, обаче, разграничаваме два вида частни случаи. Едните от тях са тривиални състояния на динамичното, за които знаем отговора и директно можем да попълним в таблицата. Другите са състояния, които са невалидни и в общия случай излизат извън таблицата (примерно отрицателни, или пък твърде големи индекси).
?Друг вариант е да изнесем първия тип частни случаи преди обхождащите цикли, като директно попълним съответните клетки в динамичната таблица. Така няма да се налага да ги разглеждаме вътре в циклите, което би забързало леко програмата ни. Това, обаче, все още не решава проблема с частните случаи от втория тип (тоест тези, които излизат извън таблицата).
Първите частни случаи са много лесни - просто проверяваме дали сме в тях, и ако да, попълваме клетката от таблицата и даваме continue; (тоест продължаваме със следващата стойност от най-вътрешния обхождащ цикъл).

Ако сме направили обхождащите цикли като хората, вторият тип частни случаи не може да се случи съвсем в началото на същинското тяло. Ако не сме, можем просто да проверяваме и за тях, и ако сме в такова състояние също да продължаваме с continue;.
?Забележете, че при итеративното динамично не е нуждно да проверяваме дали вече не сме изчислили съответната клетка. Както казахме, тъй като ползваме цикли, които обхождат всяка клетка най-много по веднъж, то със сигурност не сме.

Остава да правим същинската работа - сиреч самите изчисления. Те могат да са много различни, в зависимост от задачата, която решаваме, но това не бива да ни касае особено. Ако по някое време ни се наложи да решаваме подзадача от същия тип, вместо да викаме функция (както бихме направили при рекурсивния вариант) то можем директно да вземем вече изчислената стойност от таблицата! При правилно обхождане всяка стойност, която ни е нужна, вече ще бъде сметната.

Тук, обаче, има едно изключение (и нещо, за което трябва да внимавате, а не трябваше в рекурсивния вариант). Ако случайно трябва да вземете резултата за невалидна клетка (тоест клетка, която не помните в таблицата), трябва да не индексирате в таблицата, ами да ползвате директно стойността за невалидната клетка. В мемоизирания вариант това би било изведено като частен случай съвсем в началото на рекурсията, но тук това няма как да бъде направено.

Пример: имате динамично с кон върху шахматна дъска, като правите ход с него. Трябва първо да проверите дали новата позиция излиза извън дъската (в който случай да ползвате стойност 0, -1, -безкрайност или каквато друга стойност би била подходяща), и чак ако това не е така да ползвате запаметената стойност от динамичната таблица.

Запомняне на резултата

Тук също няма разлика с мемоизирания вариант - просто трябва да направим клетката от динамичната таблица, която отговаря за съответното състояние, да е равна на намерения отговор. Ако ползваме референция към клетката (трика от началото на темата) не трябва да правим нищо.

Готово!

След като всички обхождащи цикли завършат, цялата таблица (или поне валидните състояния в нея) ще бъде изчислена. Резултатът на задачата ще се намира в клетката, която отговаря за състоянието, с което бихме викнали рекурсията. В редки случаи може да се наложи да сумирате повече от една клетка (примерно цял ред, или цяла подматрица) за да получите целия резултат, но това, отново, би се наложило да правите и в рекурсивния вариант.

Примерна имплементация

За да станат нещата по-ясни ще имплементираме двете примерни задачи от първа част чрез итеративно динамично.

Първа примерна задача

Дадено ви е поле с 1 ≤ N ≤ 30 реда и 1 ≤ M ≤ 30 колони. Започвайки от горния ляв ъгъл, по колко начина можете да стигнете до долния десен такъв, движейки се само надолу или надясно?

Например при поле с три реда и три колони има шест такива пътя: { (надясно, надясно, надолу, надолу), (надясно, надолу, надясно, надолу), (надясно, надолу, надолу, надясно), (надолу, надясно, надясно, надолу), (надолу, надясно, надолу, надясно), (надолу, надолу, надясно, надясно) }.
Ако помните, в рекурсивната ни имплементация подавахме два аргумента - колко реда и колко колони са ни останали. Тук ще превърнем тези аргументи в цикли, като трябва да ги въртим по такъв начин, че да не ни трябват състояния, които все още не сме изчислили. В мемоизирания вариант викахме рекурсията с броя редове минус едно като първи аргумент и броя колони минус едно - като втори. Какво би станало тук, ако въртим циклите пак в този ред (намаляващ)? Първо би се наложило да изчислим клетката dyn[numRows - 1][numCols - 1]. За нея ще са ни нужни (до) две други клетки: dyn[numRows - 2][numCols - 1] и dyn[numRows - 1][numCols - 2]. Обаче тях все още не сме изчислили! Проблем. Затова тук правилният ред на изчисления би бил в нарастващ ред на аргументите. Всъщност, като rule of thumb можете да ползвате, че ако в рекурсивния вариант даден аргумент намалява при по-нататъшни викания, то в итеративния вариант трябва да се увеличава, и обратно.
long
long
numberOfWays(
int
n
,
int
m) {
static
long
long
dp[MAX][MAX]
;
for
(
int
row
=
n
-
1
;
row
>
=
0
;
row
-
-
) {
for
(
int
col
=
m
-
1
;
col
>
=
0
;
col
-
-
) {
long
long
&
ans
=
dp[row][col]
;
// Единица ако сме в крайната клетка; иначе нула.
ans
=
(row
=
=
n
-
1
&
&
col
=
=
m
-
1
)
;
if
(row
+
1
<
n) ans
+
=
dp[row
+
1
][col]
;
if
(col
+
1
<
m) ans
+
=
dp[row][col
+
1
]
;
} }
return
dp[
0
][
0
]
;
}
След завършване на циклите, отговорът на задачата наистина се намира точно в клетката, с която бихме започнали рекурсията в мемоизирания вариант - а именно dyn[0][0]. Aко забелязахте, тук използвахме трикът с референцията от началото на темата.

Забележете, че вътре в двата обхождащи цикъла, които ни определят стейта, тялото е почти същото, каквото беше и в рекурсивния вариант. Тук, обаче, трябва да се подсигурим, че не излизаме от дъската преди да вземем стойността от таблицата (затова и имаме if() преди всяко индексиране), докато в рекурсивния вариант викахме смело нататък, като се справяхме с тези частни случаи в нейното начало.

Втора примерна задача

Ели е наследила от баба си (Нора) винарска изба. В нея има N ≤ 200 бутилки вино, наредени в редица. За простота ще ги номерираме с числата от 0 до N-1, включително. Техните начални цени са неотрицателни цели числа, които са ни дадени в масива P[]. Цената на i-тата бутилка е дадена в Pi. Колкото повече отлежават бутилките, толкова по-скъпи стават те. Ако бутилка k е отлежала Х години, нейната цена става X*Pk.

В завещанието си бабата на Ели е поискала всяка година внучката ѝ да продава по една от тях, като избира или най-лявата или най-дясната останала. Каква е максималната сума пари, която Ели може да спечели, ако продава бутилките в най-добрия за нея ред? Считаме, че бутилките са отлежавали 1 година, когато бива продадена първата от тях.

Например ако имаме 4 бутилки с цени {P0 = 1, P1 = 4, P2 = 2, P3 = 3}, оптималното решение би било да продаде бутилките в реда {0, 3, 2, 1} за печалба 1*1 + 2*3 + 3*2 + 4*4 = 29.
Преди да видите нашата имплементация, помислете как вие бихте подредили циклите и как бихте ги въртяли - дали в нарастващ или намаляващ ред (и кои в нарастващ, кои в намаляващ)? С кои частни случаи трябва да се справите в началото на същинското тяло и с кои - при индексирането на таблицата?
int
winesIterative() {
static
int
dp[MAX][MAX]
;
for
(
int
right
=
0
;
right
<
n
;
right
+
+
) {
for
(
int
left
=
n
-
1
;
left
>
=
0
;
left
-
-
) {
if
(left
>
right) { dp[left][right]
=
0
;
}
else
{
int
year
=
left
+
n
-
right
;
dp[left][right]
=
max( year
*
price[left]
+
(left
<
right
?
dp[left
+
1
][right]
:
0
)
,
year
*
price[right]
+
(left
<
right
?
dp[left][right
-
1
]
:
0
) )
;
} } }
return
dp[
0
][n
-
1
]
;
}
Нашата имплементация беше нарочно глупава, като въртяхме циклите в целите им възможни интервали. Това, обаче, обхожда дори невалидни клетки (където left > right), което трябваше експлицитно да хендълваме същинското тяло. Много по-лесно можеше да се справим с това, ако бяхме започвали цикъла по right от left нататък. Така винаги щяхме да сме във валиден стейт, като нямаше да се налага да правим тези проверки. Тоест обхождащите ни цикли биха били:
int
winesIterative() {
static
int
dp[MAX][MAX]
;
for
(
int
left
=
n
-
1
;
left
>
=
0
;
left
-
-
) {
for
(
int
right
=
left
;
right
<
n
;
right
+
+
) {
int
year
=
left
+
n
-
right
;
dp[left][right]
=
max( year
*
price[left]
+
(left
<
right
?
dp[left
+
1
][right]
:
0
)
,
year
*
price[right]
+
(left
<
right
?
dp[left][right
-
1
]
:
0
) )
;
} }
return
dp[
0
][n
-
1
]
;
}
След завършването на всичко, отговорът би се намирал в dyn[0][N - 1], тъй като в началото най-лявата бутилка е 0, а най-дясната е N - 1.

Оптимизация на паметта чрез итерация

Едно от най-големите предимства на итеративното динамично пред рекурсивното такова е, че в част от задачите е възможно с него да направим голяма оптимизация на паметта (почти изцяло да премахнем едно от измеренията на таблицата).

Това е възможно когато някой от аргументите на динамичното се променя с най-много някакво малко число (обикновено 1) при промяна на стейта. За да можем да приложим оптимизацията трябва цикълът по този аргумент да може да бъде изведен като най-външен. Интересен факт е, че това е така и при двете примерни задачи, които дадохме в първата тема за динамично (което не беше нарочно). Сега ще покажем как можем да намалим драстично размера на едно от измеренията при тях. И при двете получаваме решение с O(N) вместо O(N2) памет.

Идеята е, че ако аргументът от най-външния цикъл или не се променя или се променя само с 1, то можем да не пазим размерност [SIZE], а само [2] за този аргумент. Реално тези два "реда" ще са текущият, който попълваме, и "предходният", откъдето взимаме вече изчислени стойности. В началото на всяка итерация на най-външния цикъл ще прехвърляме изчислените стойности във втория ред, а после ще попълваме новоизчислените стойности в първия.
!Тази оптимизация работи когато най-външният аргумент се променя с някакво относително малко число K, което не е задължително да е 1. Но тъй като най-често това е 1, а и идеята за повече не се променя, ще покажем само този вариант.
Друг вариант, който можете да видите често при имплементацията на тази оптимизация на паметта е да се пази двоичен флаг от кой ред взимаме стойностите и в кой записваме новите. Този флаг реално съвпада с четността на аргумента от най-външния цикъл, така че трети вариант е да се ползва тя.

Първа примерна задача (оптимизация на паметта)

Забелязваме, че от всеки стейт ни интересуват единствено клетката "отдолу" и клетката "отдясно". В тази задача и двата аргумента (и row и col) са валидни кандидати за оптимизация - просто ако изберем col трябва да го преместим да бъде външен цикъл. За простота ще запазим нещата както са сега.
long
long
numberOfWaysOptimized(
int
n
,
int
m) {
static
long
long
dp[
2
][MAX]
;
for
(
int
row
=
n
-
1
;
row
>
=
0
;
row
-
-
) { memcpy(dp[
1
]
,
dp[
0
]
,
sizeof
(dp[
1
]))
;
for
(
int
col
=
m
-
1
;
col
>
=
0
;
col
-
-
) {
long
long
&
ans
=
dp[
0
][col]
;
// One if at end cell, zero otherwise.
ans
=
(row
=
=
n
-
1
&
&
col
=
=
m
-
1
)
;
if
(row
+
1
<
n) ans
+
=
dp[
1
][col]
;
if
(col
+
1
<
m) ans
+
=
dp[
0
][col
+
1
]
;
} }
return
dp[
0
][
0
]
;
}
Ако забелязвате, има няколко разлики с предходната версия:
  1. Първата (и основна) разлика е, че големината на таблицата е значително по-малка - сега първото измерение е 2 вместо MAX.
  2. Втората е, че в началото на най-външния цикъл копираме всички клетки от масива dp[1][D1][D2]...[Dk] в dp[0][D1][D2]...[Dk]. Това е за удобство - така винаги попълваме dp[0], а "следващият ред" е dp[1].
  3. Третата е, че вече не индексираме dp[row + 0][...] и dp[row + 1][...] а dp[0][...] и dp[1][...].

Втора примерна задача (оптимизация на паметта)

!Макар и в тези две задачи да можем да оптимизираме който и да е аргумент, в много други ще можем да направим това само по един. В случаите, в които можем да направим това по няколко има смисъл да го направим по този, чиято размерност е най-голяма (така си спестяваме най-много памет).
Втората примерна задача не е много по-различна. И тук можем да си изберем дали ще оптимизираме по left или по right, като ще направим това отново без да променяме реда на циклите (тоест ще правим оптимизацията по left). Този път, обаче, ще покажем как можем да направим това ползвайки четността на най-външния аргумент вместо да копираме резултатите в началото на най-външния цикъл.
int
winesIterativeOptimized() {
static
int
dp[
2
][MAX]
;
for
(
int
left
=
n
-
1
;
left
>
=
0
;
left
-
-
) {
for
(
int
right
=
left
;
right
<
n
;
right
+
+
) {
int
year
=
left
+
n
-
right
;
dp[left
%
2
][right]
=
max( year
*
price[left]
+
(left
<
right
?
dp[(left
+
1
)
%
2
][right]
:
0
)
,
year
*
price[right]
+
(left
<
right
?
dp[left
%
2
][right
-
1
]
:
0
) )
;
} }
return
dp[
0
][n
-
1
]
;
}

Примерни задачи

Можете да пробвате да напишете задачата Miners, ползвайки итеративно динамично. Колко памет ви трябва? Би трябвало да можете да решите задачата в O(1) памет.

Из специалната секция Итеративно Динамично Оптимиране от системата за подготовка ще ви подскажем, че в задачата Knapsacks трябва да оптимизирате паметта, докато в задачата ThreeSum ще трябва да приложите итеративно динамично.

Допълнителни материали

  1. Динамично оптимиране, част I (www.informatika.bg)
  2. Динамично оптимиране, част III (www.informatika.bg)
  3. Трикове в динамичното оптимиране (www.informatika.bg)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 7750 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: