Демистифициране на динамичното програмиране

Как да изградим и кодираме алгоритми за динамично програмиране

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

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

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

Но преди да споделя процеса си, нека започнем с основните положения. Какво е динамично програмиране, така или иначе?

Дефинирано е динамично програмиране

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

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

Това, което се надявам да предам е, че DP е полезна техника за проблеми с оптимизацията, онези проблеми, които търсят максимално или минимално решение при определени ограничения, защото разглежда всички възможни подпроблеми и никога не преизчислява решението на всеки подпроблем. Това гарантира коректност и ефективност, което не можем да кажем за повечето техники, използвани за решаване или приближаване на алгоритми. Само това прави DP специално.

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

Подпроблеми на Подпроблеми на Подпроблеми

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

За да ви дадем по-добра представа за това как работи, нека намерим подпроблема в пример за проблем с динамично програмиране.

Преструвайте се, че сте се върнали през 50-те години, работещи на компютър IBM-650. Знаеш какво означава това - ударни карти! Вашата работа е на мъж или жена, IBM-650 за един ден. Дават ви естествен брой n перфоратори за пускане. Всяка ударна карта i трябва да се стартира в предварително зададено начално време s_i и да спре да се изпълнява в някакво предварително определено време на финиш f_i. Само една ударна карта може да работи на IBM-650 наведнъж. Всяка ударна карта има и свързана стойност v_i въз основа на това колко е важна за вашата компания.

Проблем: Като човек, отговарящ за IBM-650, трябва да определите оптималния график на перфоратите, който максимизира общата стойност на всички изпълнени пънккартове.

Тъй като ще разгледам подробно този пример в тази статия, засега ще ви дразня само с неговия подпроблем:

Подпроблем: Графикът на максималната стойност за пунктограмите от i до n, така че перфокартите са сортирани по време на стартиране.

Забележете как подпроблемът разгражда оригиналния проблем на компоненти, които изграждат решението. С помощта на подпроблема можете да намерите графика с максимална стойност за пунктограмите n-1 до n, а след това за punchcards n-2 до n и т.н. Намирайки решенията за всеки отделен под-проблем, след това можете да се справите със самия първоначален проблем: графикът на максималната стойност за перфокарти 1 до n. Тъй като подпроблемът изглежда като първоначалния проблем, подпроблемите могат да се използват за решаване на първоначалния проблем.

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

Мотивиране на паметта с числата на Фибоначи

Когато ви кажат да внедрите алгоритъм, който изчислява стойността на Фибоначи за всяко число, какво бихте направили? Повечето хора, които познавам, биха избрали рекурсивен алгоритъм, който изглежда нещо подобно в Python:

defolfVal (n):
  ако n == 0:
    върнете 0
  elif n == 1:
    връщане 1
  друго:
    връщане на ниво VV (n-1) + FVV (n-2)

Този алгоритъм постига целта си, но с огромна цена. Например, нека разгледаме какво трябва да изчисли този алгоритъм, за да се реши за n = 5 (съкратено като F (5)):

F (5)
                    / \
                   / \
                  / \
               F (4) F (3)
            / \ / \
          F (3) F (2) F (2) F (1)
         / \ / \ / \
       F (2) F (1) F (1) F (0) F (1) F (0)
       / \
     F (1) F (0)

Дървото по-горе представлява всяко изчисление, което трябва да се направи, за да се намери стойността на Фибоначи за n = 5. Забележете как подпроблемът за n = 2 се решава три пъти. За сравнително малък пример (n = 5), това е много повтарящо се и пропиляно изчисление!

Какво става, ако вместо да изчислим стойността на Фибоначи за n = 2 три пъти, създадохме алгоритъм, който го изчислява веднъж, съхранява неговата стойност и получава достъп до съхранената стойност на Фибоначи за всяко следващо възникване на n = 2? Точно това прави запомнянето.

Имайки това предвид, написах решение за динамично програмиране на проблема със стойността на Фибоначи:

defolfVal (n):
  бележка = [0] * (n + 1)
  бележка [0], бележка [1] = 0, 1
  за i в диапазон (2, n + 1):
    бележка [i] = бележка [i-1] + бележка [i-2]
  връщане на бележката [n]

Забележете как решението на връщащата се стойност идва от меморизационния масив memoation [], който итеративно се попълва от цикъла for. Под „итеративно“ имам предвид, че бележката [2] се изчислява и съхранява преди бележка [3], бележка [4],… и бележка [n]. Тъй като memo [] е попълнен в този ред, решението за всеки подпроблем (n = 3) може да бъде решено чрез решенията на предходните му подпроблеми (n = 2 и n = 1), защото тези стойности вече бяха запазени в бележка [] по-рано.

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

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

Моят процес на динамично програмиране

Стъпка 1: Идентифицирайте подпроблема с думи.

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

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

Например, в проблема с punchcard, аз заявих, че подпроблемът може да бъде написан като „графикът на максималната стойност за punchcards от i до n, така че ударните карти са сортирани по време на стартиране.“ Открих този подпроблем, като разбрах, че, за да определя графика на максималната стойност за пунктограмите от 1 до n, така че перфораторите да бъдат сортирани по време на стартиране, ще трябва да намеря отговора на следните подпроблеми:

  • Графикът на максималната стойност за перфокарти от n-1 до n, така че перфораторите са сортирани по време на стартиране
  • Графикът на максималната стойност за перфокарти от n-2 до n, така че перфораторите са сортирани по време на стартиране
  • Графикът на максималната стойност за перфокарти n-3 до n, така че перфораторите са сортирани по време на стартиране
  • (И така нататък)
  • Графикът на максималната стойност за перфокарти от 2 до n, така че перфоратите са сортирани по време на стартиране

Ако можете да идентифицирате подпроблем, който се основава на предишни подпроблеми, за да разрешите проблема, който сте в състояние, тогава сте на правилния път

Стъпка 2: Изпишете подпроблема като повтарящо се математическо решение.

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

Има два въпроса, които си задавам всеки път, когато се опитвам да намеря рецидив:

  • Какво решение вземам на всяка стъпка?
  • Ако алгоритъмът ми е на стъпка i, каква информация ще му е необходима, за да реши какво да правя в стъпка i + 1? (И понякога: Ако алгоритъмът ми е на стъпка i, каква информация е необходима, за да реши какво да правите в стъпка i-1?)

Да се ​​върнем към проблема с пънккарда и да зададем тези въпроси.

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

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

Ако алгоритъмът ми е на стъпка i, каква информация ще му е необходима, за да реши какво да правя в стъпка i + 1? За да вземе решение между двете опции, алгоритъмът трябва да знае следващия съвместим пънккард в реда. Следващият съвместим перфокарт за даден пънккард p е ударната карта q такава, че s_q (предварително определеното начално време за punchcard q) се случва след f_p (предварително определеното време за завършване на punchcard p) и разликата между s_q и f_p е сведена до минимум. Изоставяйки говоренето на математици, следващият съвместим пънккард е този с най-ранното време за стартиране след приключване на текущата пънккард.

Ако алгоритъмът ми е на стъпка i, каква информация му беше необходима, за да реши какво да правя в стъпка i-1? Алгоритъмът трябва да знае за бъдещите решения: тези, направени за пънккард i през n, за да решат да стартират или да не стартират punchcard i-1.

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

Без допълнително обожание, ето ни повторение:

OPT (i) = max (v_i + OPT (следващ [i]), OPT (i + 1))

Този математически рецидив изисква известно обяснение, особено за тези, които не са го писали преди. Използвам OPT (i), за да представя графика на максималната стойност за пунктограмите от i до n, така че перфораторите са сортирани по време на стартиране. Звучи познато, нали? OPT (•) е нашият подпроблем от стъпка 1.

За да определим стойността на OPT (i), ние разглеждаме две опции и искаме да вземем максимума от тези опции, за да постигнем целта си: графикът на максималната стойност за всички пънккартове. След като изберем опцията, която дава максимален резултат на стъпка i, запомняме нейната стойност като OPT (i).

Двете опции - да стартирате или да не стартирате punchcard i - са представени математически, както следва:

v_i + OPT (следващ [i])

Тази клауза представлява решението за стартиране на punchcard i. Той добавя стойността, получена от пускането на punchcard i към OPT (следващо [i]), където next [i] представлява следващия съвместим пънккард след punchcard i. OPT (следващ [i]) дава графика на максималната стойност за пунктограмите следващи [i] до n, така че перфораторите са сортирани по време на стартиране. Добавянето на тези две стойности заедно произвежда график на максимална стойност за punchcards i до n, така че ударните карти са сортирани по време на стартиране, ако punchcard i е изпълнен.

OPT (I + 1)

Обратно, тази клауза представлява решението да не стартирате punchcard i. Ако ударната карта i не е стартирана, нейната стойност не се получава. OPT (i + 1) дава графика на максималната стойност за пунктограмите i + 1 до n, така че перфораторите са сортирани по време на стартиране. И така, OPT (i + 1) дава графика на максималната стойност за пунктограмите i до n, така че ударните карти се сортират по време на стартиране, ако punchcard i не е стартиран.

По този начин, решението, взето на всяка стъпка от проблемите с punchcard, се кодира математически, за да отразява подпроблема в стъпка 1.

Стъпка 3: Решете първоначалния проблем, като използвате стъпки 1 и 2.

В стъпка 1 записахме подпроблема за проблема с punchcard с думи. В стъпка 2 записахме повтарящо се математическо решение, което съответства на тези подпроблеми. Как можем да разрешим първоначалния проблем с тази информация?

OPT (1)

Това е толкова просто. Тъй като подпроблемът, който открихме в Стъпка 1, е графикът на максималната стойност за пънккардите i до n, така че перфораторите са сортирани по време на стартиране, можем да изпишем решението на първоначалния проблем като графика с максимална стойност за пунктограмите от 1 до n така че ударните карти са сортирани по време на стартиране. Тъй като стъпки 1 и 2 вървят ръка за ръка, първоначалният проблем може да бъде написан и като OPT (1).

Стъпка 4: Определете размерите на запомнящия масив и посоката, в която той трябва да бъде попълнен.

Намерихте ли стъпка 3 измамно проста? Сигурно изглежда така. Може би си мислите, как OPT (1) може да бъде решението на нашата динамична програма, ако разчита на OPT (2), OPT (следващ [1]) и т.н.?

Правилно сте забелязали, че OPT (1) разчита на решението на OPT (2). Това следва директно от стъпка 2:

OPT (1) = max (v_1 + OPT (следващ [1]), OPT (2))

Но това не е смазващ въпрос. Помислете за примера за мемонизиране на Фибоначи. За да намери стойността на Фибоначи за n = 5, алгоритъмът разчита на факта, че стойностите на Фибоначи за n = 4, n = 3, n = 2, n = 1 и n = 0 вече са запомнени. Ако попълним таблицата си за запомняне в правилния ред, разчитането на OPT (1) на други подпроблеми не е голяма работа.

Как можем да определим правилната посока за попълване на таблицата за запомняне? В проблема с punchcard, тъй като знаем, че OPT (1) разчита на решенията на OPT (2) и OPT (следващ [1]), и че ударните карти 2 и next [1] имат начални времена след punchcard 1 поради сортирането, ние можем да заключим, че трябва да попълним таблицата си за запомняне от OPT (n) до OPT (1).

Как да определим размерите на този масив за запомняне? Ето един трик: размерите на масива са равни на броя и размера на променливите, на които разчита OPT (•). В проблема с punchcard имаме OPT (i), което означава, че OPT (•) разчита само на променлива i, която представлява номера на punchcard. Това предполага, че нашият масив за запомняне ще бъде едномерен и че размерът му ще бъде n, тъй като има n общо пънчкарти.

Ако знаем, че n = 5, тогава нашият масив за запомняне може да изглежда така:

бележка = [OPT (1), OPT (2), OPT (3), OPT (4), OPT (5)]

Въпреки това, тъй като много езици за програмиране започват да индексират масиви от 0, може да е по-удобно да създадете този масив за запомняне, така че неговите индекси да се изравняват с номерата на перфокартата:

бележка = [0, OPT (1), OPT (2), OPT (3), OPT (4), OPT (5)]

Стъпка 5: Кодирайте го!

За да кодираме нашата динамична програма, ние събрахме стъпки 2–4. Единствената нова информация, която ще ви е необходима, за да напишете динамична програма, е основен случай, който можете да намерите, докато се занимавате с алгоритъма си.

Динамична програма за проблема с punchcard ще изглежда така:

def punchcardSchedule (n, стойности, следващ):
 # Инициализирайте масива за запомняне - Стъпка 4
  бележка = [0] * (n + 1)
  
 # Задайте основен случай
  бележка [n] = стойности [n]
  
 # Изградете таблица за запомняне от n до 1 - Стъпка 2
  за i в обхват (n-1, 0, -1):
    бележка [i] = max (v_i + мемо [следваща [i]], бележка [i + 1])
 
 # Върнете решение към първоначалния проблем OPT (1) - Стъпка 3
  бележка за връщане [1]

Поздравления за написването на първата ви динамична програма! Сега, когато намокрите краката си, ще ви преведа през различен тип динамична програма.

Парадокс на избор: Множество опции DP Пример

Без връзка с DP, но точно изобразяване на това колко вредни могат да бъдат решения с много опции.

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

Време е за нов пример.

Преструвайте се, че продавате гривните за приятелство на n клиенти и стойността на този продукт се увеличава монотонно. Това означава, че продуктът има цени {p_1,…, p_n}, така че p_i ≤ p_j, ако клиент j идва след клиент i. Тези n клиенти имат стойности {v_1,…, v_n}. Даден клиент ще купя гривна за приятелство на цена p_i, ако и само ако p_i ≤ v_i; в противен случай приходите, получени от този клиент, са 0. Да предположим, че цените са естествени числа.

Проблем: Трябва да намерите набор от цени, които ви гарантират максималните възможни приходи от продажба на вашите гривни за приятелство.

Вземете секунда, за да помислите как можете да разрешите този проблем, преди да разгледате моите решения на стъпки 1 и 2.

Стъпка 1: Идентифицирайте подпроблема с думи.

Подпроблем: Максималните приходи, получени от клиенти i до n, така че цената за клиент i-1 е определена на q.

Открих този подпроблем, като разбрах, че за да определям максималните приходи за клиенти от 1 до n, ще трябва да намеря отговора на следните подпроблеми:

  • Максималните приходи, получени от клиенти n-1 до n, така че цената за клиент n-2 е определена на q.
  • Максималните приходи, получени от клиенти n-2 до n, така че цената за клиент n-3 е определена на q.
  • (И така нататък)

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

Стъпка 2: Изпишете подпроблема като повтарящо се математическо решение.

Има два въпроса, които си задавам всеки път, когато се опитвам да намеря рецидив:

  • Какво решение вземам на всяка стъпка?
  • Ако алгоритъмът ми е на стъпка i, каква информация ще му е необходима, за да реши какво да правя в стъпка i + 1? (И понякога: Ако алгоритъмът ми е на стъпка i, каква информация ще му е необходима, за да реши какво да прави в стъпка i-1?)

Да се ​​върнем към проблема с гривната за приятелство и да зададем тези въпроси.

Какво решение вземам на всяка стъпка? Решавам на каква цена да продавам гривната си за приятелство на настоящия клиент. Тъй като цените трябва да са естествени числа, знам, че трябва да определям цената си за клиент i в диапазона от q - цената, определена за клиента i-1 - до v_i - максималната цена, на която клиентът ще си купя гривна за приятелство.

Ако алгоритъмът ми е на стъпка i, каква информация ще му е необходима, за да реши какво да правя в стъпка i + 1? Моят алгоритъм трябва да знае цената, зададена за клиент i и стойността на клиента i + 1, за да се реши на кое естествено число да се зададе цената за клиента i + 1.

С тези знания мога математически да изпиша повторението:

OPT (i, q) = max ~ ([Приход (v_i, a) + OPT (i + 1, a)])
така че max ~ намира максимума за всички a в диапазона q ≤ a ≤ v_i

Отново този математически рецидив изисква известно обяснение. Тъй като цената за клиент i-1 е q, за клиент i, цената a или остава на цяло число q или се променя като цяло число между q + 1 и v_i. За да намерим общите приходи, добавяме приходите от клиент i към максималните приходи, получени от клиенти i + 1 до n, така че цената за клиент i беше определена на a.

С други думи, за да увеличите максимално общите приходи, алгоритъмът трябва да намери оптималната цена за клиента i, като провери всички възможни цени между q и v_i. Ако v_i ≤ q, тогава цената a трябва да остане на q.

Ами другите стъпки?

Работата през стъпки 1 и 2 е най-трудната част от динамичното програмиране. Като упражнение ви предлагам да работите самостоятелно чрез стъпки 3, 4 и 5, за да проверите разбирането си.

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

Сега за забавната част от писането на алгоритми: анализ на време на изпълнение. Ще използвам big-O нотация по време на тази дискусия. Ако все още не сте запознати с big-O, предлагам да го прочетете тук.

Обикновено изпълнението на динамичната програма се състои от следните функции:

  • Предварителна обработка
  • Колко пъти работи цикълът for
  • Колко време отнема повторението, за да се изпълни в един за итерация на цикъл
  • Последваща обработка

Като цяло, времето за изпълнение има следната форма:

Предварителна обработка + Loop * Рецидивиране + Post-обработка

Нека да направим анализ на изпълнението на проблема с пунчкарда, за да се запознаем с big-O за динамични програми. Ето динамичната програма за проблема с punchcard:

def punchcardSchedule (n, стойности, следващ):
 # Инициализирайте масива за запомняне - Стъпка 4
  бележка = [0] * (n + 1)
  
 # Задайте основен случай
  бележка [n] = стойности [n]
  
 # Изградете таблица за запомняне от n до 1 - Стъпка 2
  за i в обхват (n-1, 0, -1):
    бележка [i] = max (v_i + мемо [следваща [i]], бележка [i + 1])
 
 # Върнете решение към първоначалния проблем OPT (1) - Стъпка 3
  бележка за връщане [1]

Нека да прекъснем нейното изпълнение:

  • Предварителна обработка: Тук това означава изграждане на масива за запомняне. О (п).
  • Колко пъти работи цикълът for: O (n).
  • Колко време отнема повторението, за да се изпълни в една за итерация на цикъл: Рецидивът отнема постоянно време за изпълнение, защото взема решение между две опции във всяка итерация. O (1).
  • След обработка: Няма тук! O (1).

Общото време на изпълнение на динамичната програма за проблем с ударната карта е O (n) O (n) * O (1) + O (1) или, в опростен вид, O (n).

Направи го!

Е, това е - вие сте една крачка по-близо до това да станете съветник за динамично програмиране!

Маргарет Хамилтън: един от многото магьосници по програмиране в нашата история!

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

Затова излезте оттам и вземете интервютата, часовете и живота си (разбира се) с новите си познания за динамично програмиране!

Много благодаря на Стивън Бенет, Клеър Дюранд и Притхат Нат за корекцията на този пост. Благодаря на професор Хартлайн, че ме развълнува толкова динамично програмиране, че подробно писах за него.

Наслаждавате се на това, което четете? Разпространете любовта, като харесате и споделите това парче. Имате мисли или въпроси? Достигнете до мен в Twitter или в коментарите по-долу.