Co to je, jak to funguje a výukové zdroje

Dynamické programování je koncept vyvinutý Richardem Bellmanem, matematikem a ekonomem.

Bellman v té době hledal způsob, jak vyřešit složité optimalizační problémy. Problémy s optimalizací vyžadují, abyste ze sady možností vybrali nejlepší řešení.

Příkladem optimalizačního problému je problém cestujícího obchodníka. Cílem je najít nejkratší cestu, která umožní prodejci navštívit každé město přesně jednou a vrátit se do výchozího města.

Bellmanův přístup k těmto problémům byl rozdělit je na menší dílčí problémy a vyřešit dílčí problémy od nejmenšího po největší. Výsledky dílčích problémů pak uložil a znovu je použil k řešení větších dílčích problémů. To je hlavní myšlenka dynamického programování.

Co je dynamické programování?

Dynamické programování řeší optimalizační problémy tak, že je rozdělí na menší dílčí problémy, každý dílčí problém vyřeší jednou a jejich řešení uloží, aby je bylo možné znovu použít a zkombinovat k řešení většího problému. Problémy jsou řešeny od nejmenších po největší, což umožňuje opětovné použití řešení.

Jak funguje dynamické programování?

Řešení problému pomocí dynamického programování zahrnuje následující kroky:

Definujte dílčí problémy: Velký problém je rozdělen na malé dílčí problémy.

Řešení dílčích problémů: Jedná se o řešení identifikovaných dílčích problémů, které lze provést pomocí rekurze nebo iterace.

Uložte řešení: Řešení dílčích problémů jsou uložena tak, aby je bylo možné znovu použít.

Sestavte řešení původního problému: Řešení velkého problému je sestaveno z dílčích problémů, které již byly vypočteny.

Abychom to viděli v akci, vypočítáme pomocí tohoto procesu 6. Fibonacciho číslo, F(6).

Nejprve definujte dílčí problémy, které je třeba vyřešit.

F(n) = F(n-1) + F(n-2) pro n > 1

Proto: F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

Druhý krok zahrnuje řešení každého dílčího problému pomocí rekurzivní funkce nebo iteračního procesu. Řešíme dílčí problémy od nejmenšího po největší, znovu využíváme výsledky menších dílčích problémů. To nám dává následující:

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

F(5) = F(4) + F(3) = 3 + 2 = 5

F(6) = F(5) + F(4) = 5 + 3 = 8

Když řešíme každý z dílčích problémů, ukládáme řešení do pole nebo tabulky, takže je lze znovu použít při řešení větších dílčích problémů, jako je například:

Jakmile jsou všechny dílčí problémy vyřešeny, použijeme řešení k vytvoření řešení původního problému.

V tomto případě je řešením původního problému 6. Fibonacciho číslo, které se najde sečtením výsledků F(5) a F(4), dílčích problémů identifikovaných z největšího problému. Výsledek nám dává 8.

Kde a proč se používá dynamické programování?

Dynamické programování se používá v oblastech, kde máme problémy, které lze rozdělit na menší dílčí problémy, a jejich řešení slouží k řešení větších problémů.

Tyto oblasti zahrnují informatiku, ekonomii, matematiku a inženýrství. V informatice se používá k řešení problémů zahrnujících sekvence, grafy a celočíselné hodnoty a v konkurenčním programování.

V ekonomii se používá k řešení optimalizačních problémů ve financích, výrobě a alokaci zdrojů. V matematice se dynamické programování používá v teorii her, statistice a pravděpodobnosti, kde se používá k řešení optimalizačních problémů.

Ve strojírenství se používá k řešení problémů v alokaci zdrojů, plánování, výrobě, komunikaci a řídicích systémech.

Použití dynamického programování k řešení optimalizačních problémů má několik výhod:

Efektivita: Dynamické programování může být efektivnější než jiné optimalizační algoritmy, protože se vyhne opakovanému přepočítávání podobných problémů.

Řešení velkých problémů: Dynamické programování je ideální pro velké optimalizační problémy, které by nebylo možné řešit jinými metodami. Je to proto, že rozděluje problém na menší problémy, které snižují jejich složitost.

Optimální řešení: Algoritmy dynamického programování mohou najít optimální řešení problému, pokud jsou dílčí problémy a cíle správně definovány.

Jednoduchost: Algoritmy dynamického programování lze snadno implementovat a pochopit, zvláště pokud lze problém definovat v určitém pořadí.

Rozšiřitelnost: Algoritmy dynamického programování lze snadno rozšířit pro řešení složitějších problémů přidáním dalších dílčích problémů a úpravou cílů problému.

Pokud jde o řešení optimalizačních problémů, dynamické programování je velmi užitečným nástrojem k zajištění efektivity řešení.

Přístupy používané v dynamickém programování

V dynamickém programování se k řešení optimalizačních problémů používají dva přístupy. Jedná se o přístup shora dolů a přístup zdola nahoru.

Přístup shora dolů

Tento přístup je také známý jako memoizace. Memoizace je optimalizační technika, která se primárně používá ke zrychlení počítačových programů ukládáním výsledků volání funkcí do mezipaměti a vrácením výsledků uložených v mezipaměti, až budou příště potřeba, místo jejich opětovného výpočtu.

Přístup shora dolů zahrnuje rekurzi a ukládání do mezipaměti. Rekurze zahrnuje funkci, která se sama volá s jednoduššími verzemi problému jako argumentem. Rekurze se používá k rozdělení problému na menší dílčí problémy a řešení dílčích problémů.

Jakmile je dílčí problém vyřešen, jeho výsledek je uložen do mezipaměti a znovu použit, kdykoli se vyskytne podobný problém. Postup shora dolů je snadno pochopitelný a implementovatelný a dílčí problém řeší pouze jednou. Nevýhodou však je, že zabírá mnoho paměti kvůli rekurzi. To může vést k chybě přetečení zásobníku.

Přístup zdola nahoru

Přístup zdola nahoru, známý také jako tabelování, odstraňuje rekurzi a nahrazuje ji iterací, čímž se vyhne chybám při přetečení zásobníku.

V tomto přístupu je velký problém rozdělen na menší dílčí problémy a řešení dílčích problémů se používají k řešení většího problému.

Menší dílčí problémy se nejprve řeší od největšího po nejmenší a jejich výsledky se ukládají do matice, pole nebo tabulky, odtud název tabelování.

Uložené výsledky řeší větší problémy, které závisí na dílčích problémech. Výsledek původního problému je pak nalezen řešením největšího dílčího problému pomocí dříve vypočítaných hodnot.

Tento přístup má tu výhodu, že je efektivní z hlediska paměti a času, protože odstraňuje rekurzi.

Příklady problémů, které lze řešit dynamickým programováním

Níže jsou uvedeny některé problémy s programováním, které lze vyřešit pomocí dynamického programování:

#1. Problém s batohem

Zdroj: Wikipedie

Batoh je taška vyrobená z plátna, nylonu nebo kůže, obvykle připevněná na zádech a používaná vojáky a turisty k přenášení zásob.

V problému s batohem je vám předložen batoh a vzhledem k jeho nosnosti musíte vybrat položky, z nichž každá má svou hodnotu. Váš výběr by měl být takový, abyste získali maximální celkovou hodnotu vybraných položek a váha položek byla menší nebo rovna kapacitě batohu.

Příklad problému s batohem je uveden níže:

Představte si, že jedete na pěší výlet a máte batoh s nosností 15 kilogramů. Máte seznam položek, které si můžete vzít s sebou, spolu s jejich hodnotami a hmotnostmi, jak je uvedeno v tabulce níže:

PoložkaHodnotaHmotnostStan2003Spací pytel1502Vařič501Jídlo1002Lahev na vodu100,5Lékárnička251

Vyberte si podmnožinu položek, které chcete přinést, tak, aby celková hodnota položek byla maximalizována, zatímco celková hmotnost byla menší nebo rovna kapacitě batohu, což je 15 kilogramů.

Reálné aplikace problému s batohem zahrnují výběr cenných papírů, které se mají přidat do portfolia, aby se minimalizovalo riziko a maximalizoval zisk, a hledání nejméně plýtvavých způsobů, jak snížit suroviny.

#2. Problém s plánováním

Problém plánování je problém optimalizace, ve kterém je cílem optimálně přiřadit úkoly množině zdrojů. Zdroji mohou být stroje, personál nebo jiné zdroje používané k dokončení úkolů.

Příklad problému s plánováním je uveden níže:

Představte si, že jste projektový manažer odpovědný za plánování sady úkolů, které musí splnit tým zaměstnanců. Každý úkol má čas zahájení, čas ukončení a seznam zaměstnanců, kteří jsou kvalifikováni k jeho dokončení.

Zde je tabulka, která popisuje úkoly a jejich vlastnosti:

Úkol Čas zahájeníKonecKvalifikovaní zaměstnanciT1911A, B, CT21012A, CT31113B, CT41214A, B

Přidělte každý úkol zaměstnanci, abyste minimalizovali celkový čas dokončení.

S problémem plánování se můžeme setkat ve zpracovatelském průmyslu, když se snažíme optimalizovat alokaci zdrojů, jako jsou stroje, materiály, nástroje a pracovní síla.

Lze se s ním setkat i ve zdravotnictví při optimalizaci využití lůžek, personálu a zdravotnického materiálu. Další průmyslová odvětví, kde se tento problém může vyskytnout, jsou projektové řízení, řízení dodavatelského řetězce a vzdělávání.

#3. Problém obchodního cestujícího

Zdroj: Wikipedie

Toto je jeden z nejvíce studovaných optimalizačních problémů, které lze vyřešit pomocí dynamického programování.

Problém cestujícího prodejce poskytuje seznam měst a vzdálenosti mezi každou dvojicí měst. Musíte najít nejkratší možnou trasu, která navštíví každé město přesně jednou a vrátí se do původního města.

Příklad problému cestujícího prodejce je uveden níže:

Představte si, že jste prodejce, který potřebuje v co nejkratším čase navštívit řadu měst. Máte seznam měst, která musíte navštívit, a vzdálenosti mezi každou dvojicí měst, jak je uvedeno v tabulce níže:

MěstoABCDEA010152030B100352515C153503020D202530010E301520100

S problémem cestujících obchodníků se můžeme setkat mimo jiné v odvětví volného času při plánování tras pro turisty, logistice při plánování přepravy zboží, přepravě při plánování autobusových tras a v odvětví prodeje.

Je zřejmé, že dynamické programování má mnoho aplikací v reálném světě, což pomáhá dozvědět se o něm více.

Zvažte následující zdroje, abyste odhalili své znalosti dynamického programování.

Zdroje

Dynamické programování od Richarda Bellmana

Dynamické programování je kniha od Richarda Bellmana, který přišel s dynamickým programováním a vyvinul ho v jeho raných fázích.

Kniha je napsána snadno srozumitelným způsobem, který vyžaduje pouze základní znalosti matematiky a kalkulu k porozumění textu. Bellman v knize představuje matematickou teorii vícestupňového rozhodovacího procesu, který je klíčový v dynamickém programování.

Kniha poté zkoumá problémy s úzkými hrdly ve vícestupňových výrobních procesech, teorémy o existenci a jedinečnosti a rovnici optimálních zásob.

Nejlepší na knize je, že Bellman nabízí příklady mnoha složitých problémů v oblastech, jako je logistika, teorie plánování, teorie komunikace, matematická ekonomie a řídicí procesy, a ukazuje, jak může dynamické programování problémy vyřešit.

Kniha je k dispozici ve verzi Kindle, vázané a brožované.

Magisterský kurz Algoritmy dynamického programování

Tento Master Course Dynamic Programming Algorithms od Udemy nabízí Apaar Kamal, softwarový inženýr ve společnosti Google, a Prateek Narang, který také spolupracoval se společností Google.

Kurz je optimalizován tak, aby pomohl studentům vyniknout v programátorské soutěži, která obsahuje mnoho problémů, které vyžadují dynamické programování.

Kromě programátorských konkurentů je kurz ideální pro programátory, kteří chtějí zlepšit své porozumění algoritmům, a lidi, kteří se připravují na programovací pohovory a online kola kódování.

Kurz, který trvá přes 40 hodin, pokrývá do hloubky dynamické programování. Kurz nejprve nabízí opakování pojmů, jako je rekurze a backtracking.

Dále zahrnuje dynamické programování v teorii her, řetězce, stromy a grafy, umocňování matic, bitové masky, kombinatoriku a podsekvence, problémy s oddíly a vícerozměrné dynamické programování a mnoho dalších konceptů.

Základy konkurenčního programování, mistrovské algoritmy

Udemy nabízí kurz Základy konkurenčního programování od Prateeka Naranga a Amal Kamaarové, který pokrývá dynamické programování, matematiku, teorii čísel a pokročilé datové struktury a algoritmy způsobem, který je užitečný a relevantní pro konkurenční programátory.

Kurz nabízí opakování datových struktur a algoritmů, než se ponoříte do složitějších algoritmů a technik, které se hodí v konkurenčním programování.

Kurz pokrývá dynamické programování, matematiku, teorii her, porovnávání vzorů, Bitmasking a nesčetné množství pokročilých algoritmů používaných a testovaných v programovacích soutěžích.

Kurz Udemy je rozdělen do 10 modulů a 42 sekcí a po každé sekci poskytuje spoustu praktických otázek. Tento bestsellerový kurz je nutností pro každého, kdo se zajímá o konkurenční programování.

Závěrečná slova

Dynamické programování je užitečná dovednost pro každého programátora, který se naučí zlepšit své řešení problémů v reálném světě. Programátoři by proto měli zvážit procházení navrhovaných zdrojů, aby tento zásadní nástroj přidali do své sady nástrojů.

Dále se můžete podívat na programovací jazyky pro použití v datové vědě.