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

Dynamic Programming, Part I

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

Запознайте се с техниката "Динамично Оптимиране"!

?

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

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

Нека разгледаме следния пример:
Този пример илюстрира директно каква е идеята за решение на дадена задача: ако сме достигнали състояние (state), до което сме стигали и преди, и нещо повече, знаем, че отговорът от този state ще е винаги един и същ, можем директно да върнем намерения резултат, вместо да го изчисляваме отново.

!	Техниката "динамично оптимиране" е приложима само ако отговорът на дадена подзадача не зависи от външни (неконстантни) променливи!

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

State

Страхотно! Значи ще се опитваме да научим компютъра (по-точно програмата ни) да запомня някакви неща. За да можем да направим това, трябва да измислим начин, по който да представим въпросите в удобен за компютъра формат.

Всъщност това обикновено е най-трудната част при решаването на динамични задачи - как точно да кодираме въпроса? Очевидно "Къде е Ели?" ("Къде е батко!?") не е въпрос, който лесно може да бъде разбран от компютър. В най-най-честия случай той ще бъде зададен чрез числа - а какво точно означават числата ще зависи силно от задачата. Типичен стейт би бил едно единствено цяло число X, което ще бъде разбрано от програмата ни като "Какъв е отговорът за X?". Стойностите на аргументите в момента, в който ни е зададен въпроса, ние наричаме "състояние" (state). Интуитивно би било "Какъв е отговорът за 13?" да има един отговор, докато "Какъв е отговорът за 42?" да има друг. Съответно 13 и 42 са различни "стейтове" на въпросната задача.

Понякога въпросът може да е по-сложен, например "Колко е била средната заплата в държава X през година Y?". Забележете, че тук имаме два аргумента на въпроса - държава и година.

?	Терминът "измерение" на динамичното идва от нуждата за лесен начин за описване на естествен език от колко аргумента зависи то. Например такова с един аргумент е "едномерно", такова с два аргумента е "двумерно" и т.н.

Това не е голям проблем (даже е много типично стейтът ни да се състои от повече от едно "измерение"). Тук два различни стейта биха били "България, през 1987 година", "Германия, през 2012 година". Нещо повече, стейтовете са различни дори ако всички аргументи с изключение на един съвпадат. Например "България, през 1987 година" е различно от "България, през 2012 година".

Забележете също така, че докато годината (Y) е цяло число, то държавата със сигурност не е.

?	Често няма да се налага изобщо да "подреждаме" обектите, които искаме да индексираме. Обикновено ние ги получаваме като входни данни, като вместо да ги преподреждаме (примерно сортираме), ние просто ползваме реда, в който са ни дадени на входа.

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

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

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

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

В миналия параграф видяхме как да формулираме въпроси към компютъра. Също така е важно да видим как компютърът ще пази отговорите за тях. Нека се запитаме, как бихме пазили отговора, ако имахме само един въпрос? Логично - в променлива. Сега, как бихме пазили отговорите, ако имахме 1000 въпроса? Отново отговорът е логичен - в масив. Как бихме могли да пазим отговора, ако въпросът ни зависи от два аргумента? Ами отново просто - в двумерен масив. Масива, в който пазим вече изчислените отговори, наричаме "динамична таблица".

Нека отново разгледаме хипотетичното динамично, което би отговаряло на въпроса "Колко е била средната заплата в държава X през година Y?". Първо, трябва да видим какви са границите на въпросните аргументи. Това много зависи от самата задача - например светът съществува от стотици хиляди години, но в реална задача Y би имал стойности между (примерно) 1800 и 2012, тъй като едва ли бихме имали статистика за по-предни години. Така де факто имаме само 213 различни стойности, тоест само 213 клетки в едното измерение на динамичната таблица, вместо стотиците хиляди, които бихме могли да имаме в други задачи, в които отново единият ни аргумент е "година".

?

Редовна грешка при писането на динамично е да се обяви таблица с първо измерение за аргумента X, второ измерение за аргумента Y, но в кода да се индексира Y в първото измерение, а X във второто. Освен ако таблицата не е с еднакви размери, това най-вероятно би довело до излизане извън масива и crash на програмата ни, или, в по-гадния за дебъгване случай, печатане на грешни отговори, въпреки привидно правилен код.

Различните стойности на X също могат сравнително лесно да бъдат определени. Например, повечето статистики сочат, че в света има 196 държави - тоест валидни стойности на X биха били между 0 и 195, включително. Какво става обаче, ако считаме само държави в европейския съюз? Тогава този брой би бил значително по-малък. Ами ако включим измислени държави (например Byteland, Нарния, Македония...)? Тогава този брой може да надхвърли 196. Отново - това число трябва да определим за конкретната задача и дадените ограничения. Да приемем, че ограниченията наистина са 196 държави и 213 години. Тогава двумерен масив (динамична таблица) с размери [196][213] би ни свършила работа да пазим отговорите на въпроса "Колко е била средната заплата в държава X през година Y". От какъв тип да е въпросният масив? Ами, зависи от въпроса, на който искаме да отговорим. В случая средна заплата би ни навело на мисълта, че отговорът ще е число с плаваща запетая, тоест double dyn[196][213].

Макар и най-често отговорът да е някой от вградените типове (примерно int или double), не е невъзможно връщаният отговор да съдържа повече от една променлива (примерно string или struct), а понякога цяла структура данни (примерно vector или set).

!

Изключително честа грешка при този тип задачи е да се декларира динамична таблица, която е по-малка, отколкото трябва. Често състезателите не изчисляват съвсем вярно колко различни стойности може да приеме някой от аргументите. Това понякога води до брой, който е с 1 по-малко или повече от необходимото, което е познато като off-by-one error. И докато декларирането на по-голям масив не е проблем, то по-малък такъв води до грешки в индексацията и почти винаги - до грешни отговори (ако не crash в самата програма). Лесно решение на проблема е просто да заделяте масиви с по няколко елемента по-големи от нужното във всяко измерение. Например горният масив би било по-добре да бъде заделен като [200][220], вместо [196][213].

?	Нелоша практика е (когато имаме достатъчно памет) да се ползват размери на измеренията, които са степен на двойката, която е по-голяма или равна на нужния размер. Например вместо [196][213] бихме ползвали [256][256].

!

Жизнено важно е ако ползваме подхода с един масив да го инициализираме със стойност, която е наистина невалидна. Какво би станало, ако -1 беше валиден резултат? Интересното е, че функцията би продължила да връща верните отговори. Но бихме "изгубили" свойството на динамичното за клетки, чиито резултат е -1 - попадайки в такава клетка ние бихме я изчислявали отново и отново, независимо, че вече сме намерили нейния резултат. Това би могло да доведе до time limit, който е изключително труден за намиране (тестовете, на които се чупи, са сравнително специфични).

?

Често състезателите ползват функцията memset() за инициализация на динамичната таблица с невалидни стойности. Понякога, обаче, те забравят, че memset(array, val, sizeof(array)) има по-различно действие от очакваното "инициализирай всяка клетка от масива array със стойност val". Освен ако не сте много наясно какво правите, считайте, че memset() работи за инициализация само със стойностите 0 и -1 и то само при целочислени масиви. За повече информация как и кога точно работи функцията memset(), погледнете тази лекция.

Тук възниква важен въпрос: как знаем кои отговори са вече изчислени и кои не? Най-лесният начин за спряване с това е да ползваме втори масив (от тип bool), който пази тази информация. Това, обаче, не винаги е удобно, тъй като трябва да го поддържаме аткуален през цялото време (тоест при всяко бъркане в динамичната таблица, трябва да бъркаме и в този масив). Това води до малко повече код и нужна памет, което, макар и не особено голям проблем, много състезатели предпочитат да избегнат (когато това е възможно). Нека например динамичната таблица е от тип int, а връщаните стойности са естествени числа. Тъй като знаем, че числото -1 се поддържа от типа (цяло число), а също така е невалиден отговор (не е естествено число), можем предварително да запълним целия масив с минус единици, и когато се питаме дали вече сме изчислили даден резултат:

1. проверяваме каква е стойността в масива за въпросния стейт
2. ако стойността е различна от -1, значи въпросният резултат вече е изчислен и връщаме директно тази стойност (тя е резултата от изчисленията)
3. ако стойността е -1, значи въпросният резултат още не е сметнат и продължаваме с изчисленията

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

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

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

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

Условия

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

Търсен отговор

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

Тип задача

Често задачи, свързани с "оптимална стратегия", биха могли да бъдат решени с динамично оптимиране (просто разглеждаме всички възможни стратегии и взимаме "оптималната"). Задачи за вероятности също понякога се решават с динамично. Нещо повече, някои състезатели ползват динамично дори когато съществува директна формула - просто за тях писането на динамичното е по-просто (и бързо) от стигането до формулата. Такива задачи са особено често срещани в TopCoder.

Стейт и ограничения

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

Структура

Основната сила на динамичното оптимиране идва от това, че отговаряме много бързо на въпроси, които вече сме срещали. Следователно е логично то да е приложимо само на места, където мнозинството от въпросите се повтарят отново и отново. Наистина, какво би ни помогнало това, че след първото питане сме научили отговора на даден въпрос, ако този въпрос ще бъде зададен само веднъж? За тези проблеми (в които всеки въпрос се среща само веднъж, тоест проблемите са незастъпващи се) обикновено се използва техниката разделяй и владей. При динамичното оптимиране искаме точно обратното - подзадачите да са застъпващи се, като застъпената част също е въпрос, чиито отговор трябва да намерим. Затова най-важното изискване, за да може дадена задача да се реши с динамично оптимиране, е нейните подзадачи да имат застъпващи се части. С други думи, ако просто правим бектрек да можем да стигнем по повече от един начин до мнозинството от стейтовете (това ще са застъпващите се части).

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

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

Наистина, учудващо е как толкова кратък и прост код може да бъде толкова неефективен. Още при сравнително малки аргументи (към N = M = 18) тя става бавна, а към N = M = 20 вече много бавна. Защо? Нали дъската тогава има едва 400 клетки? Това означава, че трябва да изчислим само 361 стойности. Защо се бави толкова?

Защото изчисляваме някои стоиности отново и отново и отново. За проста илюстрация колко повтаряща се работа извършваме, ще погледнем колко пъти функцията изчислява remRows = 5, remCols = 5 при дъска с размери N = M = 18. Някакви предположения? 2,704,156 пъти. Но по-лошото, обаче, е експоненциалността на "влошаването". По-малки стойности се изчисляват дори повече пъти. Например remRows = 3, remCols = 3 бива изчислено 40,116,600 пъти, а remRows = 2, remCols = 2 - 155,117,520 пъти.

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

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

Ако някое от тези две неща не е изпълнено, то най-вероятно динамично оптимиране не е приложимо за въпросната задача.

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

От бектрек към динамично

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

Макар и в повечето случаи да можем да направим проверката дали вече сме изчислили даден отговор съвсем в началото на рекурсията, е много по-сигурно (нашият код да не крашне) ако първо се справим с частните случаи, и едва после направим проверката. Защо е така?

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

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

Готово!

Това беше всичко, което трябваше да направим! Остава да инициализираме динамичната таблица, след това да извикаме рекурсията и няколко стотни по-късно бихме разполагали с отговора!

Memoization

?	Много хора (както в България, така и в международни форуми) наричат метода "меморизация", което всъщност звучи логично, тъй като думата "memorize" на английски означава "уча наизуст". Все пак правилният термин е "memoization", който произлиза от латински и има специфична употреба в информатиката.

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

Решение

Сега да приложим наученото в дадената примерна задача!

Първо - има ли шанс тя да се решава с динамично оптимиране? Казахме, че структурата е от желания тип - има много припокриващи се подзадачи, които са от типа на началната задача. Имаме две измерения, ограничени до 30, което чудесно би се събрало в паметта в двумерна таблица с размери, примерно, [32][32]. Искаме да отговорим на въпрос "по колко начина", което, както казахме, е един от най-силните индикатори за динамично.

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

Трябва да забележим, че броят начини да завършим пътя до крайната клетка не зависи от това как сме стигнали до текущата такава. Следователно ще се опитваме да запомним отговорите на въпроса: "По колко начина можем да стигнем до края, ако можем да мърдаме надолу още remRows пъти и надясно още remCols пъти?".

Обявяваме динамичната таблица, инициализираме я преди да извикаме рекурсията, добавяме проверка дали вече сме намерили отговора на даден въпрос веднага след частните случаи, и последно запомняме новите отговори веднага преди да ги върнем от рекурсията. Това изглежда по следния начин: Не беше толкова трудно, нали? Това решение работи за части от секундата дори при максималния вход N = M = 30.

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

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

Задачата не прилича на никой от стандартните алгоритми, които знаем. Ограниченията пък са твърде големи за да може бектрек да мине за разумно време. На всяка стъпка имаме по 2 избора (ляво или дясно), като имаме до 200 стъпки, което прави 2²⁰⁰ възможности - което е страшно много.

Можем да пробваме алчен алгоритъм. В интерес на истината, изглежда че винаги е хубаво да взимаме по-евтината бутилка, като така оставяме по-скъпите да се умножават по по-големи числа. Както се оказва, обаче, това не винаги е оптимална стратегия. Например нека вземем {P₀ = 2, P₁ = 3, P₂ = 5, P₃ = 1, P₄=4}. Нашата стратегия би взела бутилките в ред {0, 1, 4, 3, 2} за печалба 1*2 + 2*3 + 3*4 + 4*1 + 5*5 = 49. Оптималният отговор, обаче, се постига при реда {0, 4, 3, 1, 2} и има печалба 1*2 + 2*4 + 3*1 + 4*3 + 5*5 = 50. Този контрапример ни убеждава, че (дори на пръв поглед добро) алчно решение в случая не е приложимо.

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

Нека напишем бектрек решението, което би намерило верния отговор (макар и много бавно). То не е никак дълго и не би трябвало да ни създаде особени проблеми. В него подаваме три агрумента - коя година е станало, до коя бутилка сме стигнали от лявата страна и до коя бутилка сме стигнали от дясната страна. Очевидно граничният случай е когато не са останали бутилки, в който случай трябва да върнем 0. В общия случай пробваме да вземем лявата бутилка (и пускаме рекурсията нататък), а после дясната (и отново пускаме рекурсията нататък).
Структурата на задачата е точно такава, каквато искаме - имаме рекурсия (подзадачите са от същия тип), а също така стейтовете са ациклични (тъй като след като вземем бутилка няма как да я "върнем"). Функцията ни, обаче, зависи от външни фактори - глобалния масив с цените на бутилките. Това не е ли лош индикатор? В случая не - както казахме, проблемни са само неконстантни външни променливи - а първоначалните цени на вината (масивът price[], в нашия код) не се променят през цялата задача.

След като не срещнахме някакви явни индикатори, че не е динамично, защо не се опитаме да го направим такова? Въпросът, който ще формулираме е "Колко максимално може да спечели Ели, ако годината е year, най-лявата непродадена бутилка е left, а най-дясната непродадена бутилка е right?". Първото число е между 1 и 200, включително, а следващите две са между 0 и 199, включително. Реално можем да "намалим" year с единица, като при умножението ползваме year+1, постигайки три числа между 0 и 199. Дори по-просто би било да обявим динамичната таблица с размери [210][210][210] и да ги ползваме както са си. Забележете, че в стейта включваме всички аргументи на бектрека, тоест със сигурност го определяме правилно. Сега да добавим мемоизацията в началото и края на кода... … и сме готови! Тъй като цените на бутилките са неотрицателни, то очевидно не можем да имаме отговор -1. Затова можем да инициализираме динамичната таблица с memset(dyn, -1, sizeof(dyn); и после да извикаме рекурсията с int ans = recurse(1, 0, N - 1);. В ans получаваме оптималният отговор за всички бутилки.

Сложност

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

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

!

Някои от вас е възможно да са забелязали, че броя извършени операции в задачата, която решихме, всъщност е O(N2), вместо O(N3). Това, обаче, не значи, че сме направили грешка - ние намерихме "по-разпусната" горна граница, която също е вярна (недостатъците на Big-O нотацията...). Защо това е така и как да намираме по-точни граници ще разгледаме в продължението на темата.

Тъй като това не беше особено хубав пример как точно да смятаме сложността, нека си представим, че сме написали динамична задача, чиято таблица е с размер [N][M], а вътре в рекурсивната фукнция извършваме (освен константните операции) двоично търсене по някакво трето нещо с размер K. Тъй като сложността, идваща от броя клетки, е O(N∙M), а тази в тялото на рекурсията е O(log(K)), то (правилно) бихме заключили, че сложността на цялото решение е O(N∙M∙log(K)).

Възстановяване на ходовете

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

?

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

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

Нека отново разглеждаме задачата с бутилките вино. Има два пътя, по които можем да тръгнем.

По-универсалният (но по-трудният) от тях би бил да запомняме "от текущия стейт (year, left, right) оптималният преход е в стейт (year’, left’, right’)". За задачата с виното, това би означавало, че сме в година year, най-лява бутилка left и най-дясна бутилка right. Правим структура State с която пазим следващия стейт, и има променливи nextYear, nextLeft, nextRight. В допълнителен масив State trans[N][N][N] записваме информация за оптималния преход от всеки стейт. Например, от (year, left, right) бихме отишли в (trans[year][left][right].nextYear, trans[year][left][right].nextLeft, trans[year][left][right].nextRight). На базата на този масив можем да възстановим отговора. Така ако trans[year][left][right].nextLeft == left + 1, то знаем, че сме продали лявата бутилка, а ако trans[year][left][right].nextRight == right - 1, то явно сме продали дясната.

По-краткият, но понякога неприложим метод е да пазим "от текущия стейт (year, left, right) сме направили действие A", където A ни е число, което показва какво точно сме направили. Например, ако имаме K възможни продължения, число от 0 до K-1 би показало точно кое от тях сме избрали. В случая със задачата с вината имаме само две възможни действия - да вземем лявата или дясната бутилка. Така A може да приеме стойност 0 или 1, като на базата на това можем да определим кое е оптималното действие. Отново трябва да ползваме допълнителен масив, но този път той ще съдържа само едно число, затова не ни трябва допълнителна структура. В int action[N][N][N] записваме оптималните решения, които сме взели за всеки стейт. Ако action[year][left][right] == 0, то в year-тата година сме продали бутилка left (лявата такава). Ако пък action[year][left][right] == 1, то в year-тата година сме продали бутилка right (дясната такава). Забележете, че този подход би работил дори ако имахме повече от две възможни продължения (например цикъл в който викаме рекурсията нататък - можем да запаметим индекса от цикъла, при който сме постигнали оптимален резултат).

?	Ако не сте се досетили защо сложността на алгоритъма е O(N2) вместо O(N3), хубав хинт би било да помислите каква е стойността на trans[year][left][right].nextYear за всеки от стейтовете. Помага ли ни това?

Така след като сме пуснали рекурсията, освен отговора на задачата (който тя е върнала), във вече попълнените масиви trans или action (в зависимост кой от двата подхода сме ползвали) ще имаме информация за оптималните ходове от всеки стейт. Тук идва допълнителния код, който споменахме по-рано. За да възстановим точните стъпки, които сме избрали в рекурсията, в началото обявяваме променливи, отговарящи на аргументите на рекурсията, инициализирани с тези стойности, с които сме я извикали. В нашия пример това биха били int year = 1;, int left = 0;, и int right = N - 1;. Това ни определя първия стейт, в който е била рекурсията. От него, обаче, вече знаем кой е оптималният ход (пазим го в trans или action). Записваме, че сме направили съответния ход (в случая, че сме взели лявата или дясната бутилка), и го "изпълняваме" - тоест променяме променливите, които замениха аргументите, със съответните им стойности, които биха приели в рекурсията след изпълнението на въпросното действие. Например ако знаем, че сме взели лявата бутилка, то бихме направили year = year + 1; left = left + 1;, а в противен случай year = year + 1; right = right - 1;. Така стъпка по стъпка намираме оптималните ходове, докато не стигнем до терминиращите случаи (при нас - когато left > right). Дадения подход можем да си представим като връщане на свръзан списък с резултата - от един стейт пазим линк към следващото звено на отговора.

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

Популярност

Преди да завършим първата от темите за динамично оптимиране, искаме да натъртим колко важна за състезателното програмиране е тази техника. Затова и сме се опитали да я преподадем колкото се може по-подробно (както може би сте забелязали, тази тема е по-дълга от почти всички останали - а още дори не сме стигнали до половината!).

Защо правим това? Най-вече поради особената популярност на динамични задачи. Без значение от типа на състезанието (национално, международно, студентско или ученическо, и особено TopCoder), тези задачи просто доминират който и да е друг тип (може би с изключение на Графовите - които са единствените, които могат да се мерят на динамичните). Причини за това има много. Може би най-основната е, че задачите са сравнително лесни за формулиране и не изискват сложен код - в повечето случаи изискват хубава идея (което е най-цененото нещо в състезателна задача в днешно време). Друга причина е, че тези задачи са сравнително по-лесни за създаване - тестове за тях се пишат лесно, рядко изискват чекери, авторските им решения също не са толкова сложни. Има лесен начин да се провери дали дадено решение е вярно (пускат се много на брой, сравнително малки тестове, които се тестват срещу пълно изчерпване). Това е добре както за автора на задачата, така и за състезателите, тъй като и двете страни могат да проверят решението си по този начин. Съвет от нас - научете го. Тренирайте го. То е може би най-важното в състезателната информатика.

Задачи

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

Известни задачи

Задача за Раницата

Knapsack ProblemНа пръв поглед Greedy стратегия тук би била удачна. Но, както при повечето динамични задачи, това е подвеждащо - всъщност тя не би била вярна. Което трябва да направим е да пробваме всички (валидни) подмножества на предметите и да изберем най-доброто от тях.

!	Съществува по-ефективно откъм памет решение (но със същата сложност откъм време), което ще разгледаме във втората част за Динамично Оптимиране.

Забележете, че тук state-ът не е толкова тривиален. Един от възможните варианти би бил да пазим две неща - до кой предмет сме стигнали (всички преди него вече сме решили дали да вземем или не в текущата проба) и колко място ни е останало в раницата. Така за всеки предмет пробваме две неща - дали да го вземем или да не го вземем (тоест O(1) операции на стейт), а динамичната ни таблица е с размери [C][N].

Братска Подялба

Subset Sum ProblemТази задача до голяма степен прилича на тази за раницата в решението си. Отново стейтът ни е двуизмерен, и отново едното измерение пази до коя монета сме стигнали.

!	И тази задача (подобно на раницата) може да се реши с O(C * N) време и само O(C) памет. Това е показано в продължението на темата.

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

Най-дълга Нарастваща Подредица

Longest Increasing Subsequence

?	Тази задача пък има решение със сложност O(N∙log(N)), което ще разгледаме в продължението на темата.

Стейтът тук е тривиален - само кое е последното число от оригиналната редица, което сме взели в нашата подредица. Нека това е i-тото число. Следователно трябва да пробваме всички възможни валидни продължения - а те са именно числата с индекси i+1, i+2, …, N, за които е изпълнено, че A_i < A_i+k (за да може да е нарастваща). Забележете, че за разлика от останалите задачи, които разгледахме в темата, този път нямаме константен брой операции за всеки стейт, ами линеен такъв. Следователно сложността на алгоритъма, който ще направим, е O(N) за всяка от O(N) на брой възможни стейта. Следователно общата сложност е O(N2).

Най-Дълга Обща Подредица

Longest Common SubsequenceДвумерно динамично с размер [N][M], като стейтът ви е кой е индексът на последния взет елемент от първата редица и кой е индексът на последния взет елемент от втората редица. Първо пробвайте сравнително простото O(N∙M∙min(N, M)) решение, a после помислете как да го направите O(N∙M).

Задачи за тренировка

Подходяща задачка, с която можете да започнете, е Design Patterns. Ако забелязвате, основните "хинтове", че задачата се решава с Динамично Оптимиране, са налице: пита се по колко начина може да се случи нещо ("колко стринга има" реално е същото), и отговорът е достатъчно голям, за да се иска по модул. В случая стейтът е двумерен: в едното измерение може да пазите колко символа остава да "напишете", а в другото - предните колко са били гласни. Например ако ви интересува стринг с дължина 20, като не можете да имате повече от 5 последователни гласни, ако рекурсията ви е "написала" стринга "voulezvou" стейтът ще е [11][2] - остава да сложим 11 символа (за да станат 20), като последните 2 от вече сложените са гласни.

Друго двумерно динамично, подходящо за започване, е Try On. Тук е удачно да пазите кой е индексът на последния (за сега) елемент, който сте взели, и дали разликата с елемента преди него е положителна или отрицателна. Тоест би ви свършила работа таблица с размер [1000][2].

Няколко задачи с малки подсказки за стейта:

• Едномернo динамичнo: Ribbons
• Двумернo динамичнo: Triplets, като трябва да сортирате елементите, преди да направите динамичното по тях
• Тримернo динамичнo: Caribbean

Можете да порешавате още доста задачки в секцията за Динамично Оптимиране, която сме дали на тренировъчната система.

Референции

1. Трикове в динамичното оптимиране (www.informatika.bg)
2. Динамично Оптимиране, Част II (www.informatika.bg)
3. Динамично Оптимиране, Част III (www.informatika.bg)
4. Dynamic Programming (en.wikipedia.org)
5. Туториал в TopCoder (www.topcoder.com)

предишна тема

версия за печат

следваща тема