======== HW04 Dynamické programování ======== {{:courses:b6b36dsa:ukoly:dprg.png?300 |}} Stavební firma projektuje a staví lanovky v horách. Lanovky jsou určené převážně na zimní provoz, vozí lyžaře. Ti se pak spouští z kopců po sjezdovkách nebo i volně terénem. Stavební firma dostane od zadavatele mapu kopce, na kterém má být lanovka postavena. Mapa je dána jako dvourozměrná matice velikosti $n \times m$ nadmořských výšek $a_{ij}, 1 ≤ i ≤ n, 1 ≤ j ≤ m$ jednotlivých bodů v terénu. Zadání je naprojektovat **lanovku** vedoucí přes kopec tak, aby její provoz byl minimální, tj. aby po své trase zbytečně neztrácela nadmořskou výšku a aby její celková délka byla minimální. Současně má firma navrhnout optimální **trasy sjezdovek**, které vzniknou na cestách vybudovaných pro výstavbu lanovek. Po cestách se bude vozit těžká technika, proto trasa opět nesmí zbytečně ztrácet výšku a vede delšími cestami v serpentinách. Tyto vlastnosti uvítají i lyžaři, kteří budou cesty využívat pro sjezd. Po mapě se lze pohybovat pouze vlevo, vpravo, nahoru nebo dolů, vždy na následující prvek pole. Pohyb po diagonále možný není. **Cesta přes kopec** je definována jako posloupnost nadmořských výšek bodů $v_1,v_2,…,v_k$, kde $v_1 = a_{1, 1}$ a $v_k = a_{n, m}$. Současně existuje index $z$, $1 ≤ z ≤ k$ takový, že platí $v_1<⋯⋯>v_k$. Snahou je, aby hodnota nadmořské výšky $v_z$ byla maximální možná. Nejvyšší bod mapy může být umístěn v kráteru a nemusí být proto podle definice dosažitelný. Maximalizace výšky má při řešení úlohy nejvyšší prioritu - viz [[courses:b6b36dsa:ukoly:hw04#priklad_7_kopec_1_07|příklad 7]]. **Stoupání**, resp. **klesání** cesty je definováno jako $S_u = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, 1 < i ≤ z \}$, resp. $S_d = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, z < i ≤ k \}$. Sklon cesty přes kopec definujeme jako maximum stoupání a klesání cesty - $S = \mathop{\text{max}} \left( S_u, S_d \right)$. **Lanovka** (lift) vyžaduje nejkratší cestu přes kopec, která má maximální sklon, tj. ze všech nejkratších cest hledáme tu, která má maximální sklon. Délka cesty je dána rozměry matice a je rovna $n - 1 + m - 1 = n + m - 2$. **Sjezdovka** (piste) jsou vedeny nejdelšími cestami přes kopec s minimalizací sklonu cesty (s minimalizací maximálního sklonu svahu), tj. ze všech nejdelších cest hledáme tu, která má minimální sklon. Na úvodním obrázku je vidět cestu pro lanovku (znázorněno hnědě) a cestu vedoucí v serpentinách pro sjezdovku (znázorněno oranžově). Pokud existují dvě různé cesty, vybíráme tu, která: - je nejkratší (lanovka), resp. nejdelší (sjezdovka), - vede nejvýš, - sklon cesty je maximální (lanovka), resp. minimální (sjezdovka), současně se snažíme o maximalizaci/minimalizaci stoupání i klesání cesty, - ve směru do kopce vede nejvíc vpravo - viz [[courses:b6b36dsa:ukoly:hw04#priklad_3_kopec_1_03|příklad 3 (lift)]]. **Co si představit pod "ve směru do kopce vpravo"?** Řeka teče z kopce a každý vodák ví, že její levý břeh je ten, který je vlevo, když se díváme po proudu řeky, směrem z kopce. Když se otočíme proti proudu řeky, stane se tento břeh z našeho pohledu pravým. Pokud tedy kráčíme do kopce, volíme cestu vpravo. Tato cesta leží ve směru do kopce vpravo. Lanovka i sjezdovka může částečně nebo i úplně vést po stejných cestách. ====== Vstup a výstup programu ====== Na vstupu (čteme ze standardního vstupu) je dvourozměrná matice nadmořských výšek jednotlivých bodů v terénu. Na prvním řádku vstupu jsou dvě čísla ''n'' a ''m'' – rozměry matice. Následuje ''n'' řádků s ''m'' hodnotami – jednotlivé prvky matice. Pokud při čtení vstupu zjistíte chybu, vypište na standardní chybový výstup zprávu ''Error: Chybny vstup!'' a program ukončete s návratovou hodnotou ''1''. Program může mít jeden z argumentů: * ''lift'' – pro vyhledání cesty pro lanovku, * ''piste'' – pro vyhledání cesty pro sjezdovku. Pokud program argument nemá, vyhledá cestu pro lanovku i sjezdovku, postupně za sebou. Pro každou nalezenou cestu je výsledek vypsán na dvou řádcích: * délka cesty $k$, * posloupnost $v_1,v_2,…,v_k$ nadmořských výšek bodů cesty. ====== Algoritmus řešení úlohy ====== Je zřejmé, že pro řešení úlohy je potřeba prohledat mapu do šířky. S využitím rekurze to může být s ohledem na hloubku rekurze problém. Proto se zde uplatní dynamické programování a princip memoizace, kdy si jednou vypočtené údaje pamatujeme a nepočítáme je opakovaně. V úloze je zadána matice nadmořských výšek. Pokud vypočteme cestu pro lanovku (sjezdovku) do nějakého bodu, tuto informaci je dobré si pamatovat. K tomu využijeme dvourozměrné pole. Přemýšlejme nejprve, jaké údaje je nutné si pamatovat: * délku cesty do daného bodu, * maximální/minimální sklon cesty do daného bodu, * předchůdce daného bodu - cestu budeme muset zpětně rekonstruovat. Podle postupu řešení může být dobré si pamatovat i více údajů. **Jakým způsobem budeme jednotlivé prvky matice počítat?** Zde je dobré si uvědomit, která "políčka" dvourozměrného pole mohou ovlivnit výsledek na místě (indexu) $[i][j]$ (i je číslo řádku, j číslo sloupce). Při hledání cesty **pro lanovku** lze zjistit, že pro výpočet hodnot na místě $[i][j]$ v dvourozměrném poli je potřeba znát hodnoty na indexech $[i - 1][j]$ a $[i][j - 1]$. Situaci si nakreslete a přemýšlejte, jak to ideálně zařídit, abychom při výpočtu hodnoty $[i][j]$ znali hodnoty, které potřebujeme. Při hledání cesty **pro sjezdovku** je situace obtížnější. Výpočet hodnoty na místě $[i][j]$ se může měnit až do doby, dokud nejsou vypočteny všechny okolní hodnoty $[i - 1][j]$, $[i + 1][j]$, $[i][j - 1]$, $[i][j + 1]$. Tak by ale výpočet mohl běžet do nekonečna. Je proto dobré si uvědomit několik skutečností: * Nemusíme nutně prohledávat všechny čtyři směry, stačí prohledávat ty, z nichž se do bodu $[i][j]$ dostaneme z bodu s nižší nadmořskou výškou. * Body, které se mohou průběžně měnit, je vhodné si pamatovat, například ve frontě. **Jak ovlivní přechozí "políčka" dvourozměrného pole hodnotu na místě (indexu) $[i][j]$?** Při hledání cesty **pro lanovku** leží je mezi políčky $[i][j]$ a $[i - 1][j]$ vztah ''ve směru do kopce víc vpravo'', tj. toto políčko $[i - 1][j]$ má na hodnotu údajů pro $[i][j]$ větší vliv. Délka cesty se při přechodu z políčka $[i - 1][j]$, resp. $[i][j - 1]$ na políčko $[i][j]$ zvýší o jedničku. Sklon cesty upravíme podle aktuální hodnoty sklonu na políčkách $[i - 1][j]$ a $[i][j - 1]$ a sklonů mezi body $[i - 1][j]$, resp. $[i][j - 1]$ a $[i][j]$. Při výpočtu respektujeme hlavní princip dynamického programování - dílčí problémy řešíme samostatně (lokálně) podle aktuální situace. Požadavek zadání na délku cesty a její sklon nelze proto řešit globálně - nad celou mapou. Požadavky zahrneme pouze do lokálních rozhodnutí o dalším postupu v cestě. Při hledání cesty **pro sjezdovku** je obtížnější definovat vztah ''ve směru do kopce víc vpravo''. Okolní body lze například prohledat v pořadí $[i - 1][j]$, $[i][j - 1]$, $[i + 1][j]$ a $[i][j + 1]$. Dá se předpokládat, že první dva body budou ležet níž, než bod $[i][j]$ a zbývající body procházíme ve směru zprava vlevo. Ohledně délky a sklonu cesty platí stejná pravidla jako pro cestu lanovkou. Hledání cesty z kopce je problém obdobný problému hledání cesty do kopce - po prohození počátečního a koncového bodu cesty. Výslednou délku cesty a nejvyšší bod zahrneme do výpočtu až po vyřešení problému hledání cesty do a z kopce. ====== Kontrolní testy ====== Testovací soubory najdete {{ :courses:b6b36dsa:ukoly:dsa_hw04.zip |zde}}. ===== Miniaturní kopce velikosti $3 \times 3$ ===== ==== Příklad 1 – kopec_1_01 ==== Jediná neustále stoupající cesta na kopec. Všechny ostatní cesty vedou po rovině (1 1 nebo 2 2). ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 1 2 4 1 2 5 | 5 1 2 3 4 5 | 5 1 2 3 4 5 | žádný | 0 | ==== Příklad 2 – kopec_1_02 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 3 4 3 4 5 | 5 1 2 3 4 5 | 5 1 2 3 4 5 | žádný | 0 | ==== Příklad 3 – kopec_1_03 ==== Pro lanovku má uvedená cesta stoupání 5 a vede nejvíc vpravo. Cesta 1 2 3 4 9 má také stupání 5, ale vede více vlevo. Pro sjezdovku je má cesta stoupání 1 a je nejdelší možná. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 4 7 8 9 | 5 1 6 7 8 9 | 9 1 2 3 4 5 6 7 8 9 | žádný | 0 | ==== Příklad 4 – kopec_1_04 ==== ^ Vstup (stdin) ^ Výstup - lift ^ Výstup - piste ^ Chybový výstup (stderr) ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 7 8 9 | žádný | žádný | Error: Chybny vstup! | 1 | ==== Příklad 5 – kopec_1_05 ==== ^ Vstup (stdin) ^ Výstup - lift ^ Výstup - piste ^ Chybový výstup (stderr) ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 5 5 5 7 8 9 | žádný | žádný | Error: Chybny vstup! | 1 | ==== Příklad 6 – kopec_1_06 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 3 2 3 2 1 | 5 1 2 3 2 1 | 5 1 2 3 2 1 | žádný | 0 | ==== Příklad 7 – kopec_1_07 ==== Cesta je v obou případech vybrána proto, že vede nejvýš, do nejvyššího bodu. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 4 2 3 2 1 | 5 1 2 4 2 1 | 5 1 2 4 2 1 | žádný | 0 | ==== Příklad 8 – kopec_1_08 ==== Cesta pro lanovku má nejvyšší stoupání i klesání ( 5 - 2 = 3). Naopak cesta pro sjezdovku stoupání i klesání minimalizuje (stoupání i klesání je 2). ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 3 5 2 5 3 4 2 1 | 5 1 2 5 2 1 | 5 1 3 5 3 1 | žádný | 0 | ===== Středně velké a velké kopce ===== ==== Příklad 9 – kopec_2_01 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 4 1 2 3 3 2 6 3 2 3 4 2 1 | 6 1 2 6 3 2 1 | 8 1 2 3 4 6 4 2 1 | žádný | 0 | ==== Příklad 10 – kopec_2_02 ==== Cesta pro lanovku maximalizuje stoupání a navíc vede víc vpravo. Cesta 2 3 4 5 7 9 10 13 14 by měla stejné stoupání ale vede více vlevo. Naopak cesta pro sjezdovku minimalizuje stoupání, které je nakonec 2. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 3 4 6 10 3 4 5 6 11 4 5 7 9 12 7 8 9 10 12 10 9 8 13 14 | 9 2 3 4 7 8 9 10 13 14 | 9 2 3 4 5 7 9 10 12 14 | žádný | 0 | ==== Příklad 11 – kopec_2_03 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 4 15 8 10 7 8 14 18 20 9 6 13 21 24 10 11 12 15 17 28 7 8 10 12 | 9 2 7 8 14 18 21 24 17 12 | 13 2 7 9 10 11 12 13 14 18 21 24 17 12 | žádný | 0 | ==== Příklad 12 – kopec_2_04 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 4 6 8 10 12 14 16 14 12 23 24 25 11 19 21 22 24 17 15 1 3 5 7 9 | 9 2 12 23 24 25 24 17 15 9 | 13 2 4 6 8 10 12 14 16 25 24 17 15 9 | žádný | 0 | ==== Příklad 13 – kopec_2_05 ==== ^ Vstup (stdin) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 10 10 45684 45693 45716 45716 45697 45689 45696 45705 45711 45690 46016 46005 45988 46013 46027 45989 45995 46004 46001 45984 46319 46285 46298 46327 46297 46323 46316 46317 46292 46287 46294 46617 46632 46633 46614 46626 46633 46599 46608 46603 46322 46609 46895 46897 46931 46914 46898 46930 46931 46615 46306 46624 46903 47222 47227 47219 47211 47232 46897 46615 46310 46606 46892 47201 47488 47519 47516 47206 46931 46633 46305 46605 46929 47202 47527 47814 47517 47185 46913 46594 46329 46588 46910 47216 47519 47534 47525 47228 46913 46597 46285 46623 46932 47195 47188 47186 47184 47184 46926 46609 | žádný | 0 | ^ Výstup (stdout) lift | 19 45684 45693 46005 46285 46298 46632 46895 46903 47222 47227 47488 47527 47814 47534 47525 47228 47184 46926 46609 | ^ Výstup (stdout) piste | 23 45684 45693 45716 45988 46013 46027 46297 46323 46626 46633 46898 46914 46931 47227 47488 47527 47814 47534 47525 47228 47184 46926 46609 | ==== Další testy ==== **Příklad 14 - kopec_2_06** Vstup: Kopec velikosti 15x20. **Příklad 15 - kopec_2_07** Vstup: Kopec velikosti 20x30. **Příklad 16 - kopec_2_08** Vstup: Kopec velikosti 20x30. Dále je řešení testováno na datech větších velikostí - kopce velikosti až $ 200 \times 300$ bodů. ====== Dodatek k postupu řešení ====== Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_1_kopec_1_01|příklad 1 (lift)]] lze **pro cestu nahoru** získat například (viz popis [[courses:b6b36dsa:ukoly:hw04#algoritmus_reseni_ulohy|algoritmu]]): {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1[], [0, 0, [0, 0]], [1, 1, [1, 0]], [3, 1, [0, 2]], [0, 0, [0, 0]], [1, 1, [2, 0]], [4, 1, [1, 2]]} Odpovídající matice pro cestu dolů obsahuje v tomto případě samé nuly. Z matice je zřejmé, že délka maximální cesty je 4. Z odpovídajícího prvku matice na indexu [2, 2] lze dále zjistit, že maximální sklon cesty je 1 a předchozím bodem cesty je bod [1, 2]. Cesta pro lanovku do bodu [1, 2] má délku 3 (logicky o jedničku menší), sklon je stejný a předchozím bodem je bod [0, 2]. Takto pokračujeme při rekonstrukci cesty až do bodu [0, 0]. Matici konstruujeme postupně z bodu [0, 0] pro cestu nahoru a z bodu [n - 1, m - 1] pro cestu dolů. Stanovíme podmínky pro konstrukci "následujících" bodů matice. Hlavní podmínkou je neustále stoupající nadmořská výška a pak sklon svahu podle zadání úlohy. Při konstrukci cesty pro lanovku je z bodu na souřadnicích ''[x, y]'' nutné prohledat body vpravo (souřadnice ''[x + 1, y]'') a dole (souřadnice ''[x, y + 1]''). Při konstrukci cesty pro sjezdovku je nutné prohledat pro každý bod všechny směry. Hodnoty pro jednotlivé body (délka a sklon cesty) se mohou průběžně zlepšovat, a proto je potřeba body průběžně ukládat do fronty, která určí postup zpracování jednotlivých bodů. Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_9_kopec_2_01|příklad 9 (lift)]] lze **pro cestu nahoru** získat například následující matici: {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [2, 4, [1, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]} Odpovídající matice **pro cestu dolů** vypadá pak následovně: {[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2 1 [1, 3]], [0, 0, [0, 0]], [3, 3, [1, 2]], [2, 1, [1, 3]], [1 1 [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0 0 [0, 0]]} Vidíme, že vrcholem cesty je bod [1, 1] a celková délka cesty je 5 (cesta prochází přes 6 bodů). Stejnou délku cesty lze získat i v bodě [2, 1], tam je ale menší sklon cesty - ve směru nahoru i ve směru dolů. Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_9_kopec_2_01|příklad 9 (piste)]] lze **pro cestu nahoru** získat například následující matici: {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [4, 2, [2, 1]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]} Odpovídající matice **pro cestu dolů** vypadá pak následovně: {[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 3]], [0, 0, [0, 0]], [3, 2, [2, 1]], [2, 1, [1, 3]], [1, 1, [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0, 0, [0, 0]]} Vrcholem cesty je opět bod [1, 1]. ====== Odevzdání a hodnocení ====== Úlohu je možné řešit v programovacím jazyce ''Java'', ''Python'' nebo ''C/C++''. Veřejné testovací soubory - {{:courses:b6b36dsa:ukoly:DSA_HW04.zip?400|DSA_HW04}}. ^ Název úlohy v BRUTE | **HW04** || ^ Odevzdávané soubory | ''hill.py'' – zdrojový soubor v python3 || | ::: | ''Hill.java'' – zdrojový soubor v Java, název třídy Hill || | ::: | ''hill.c'', resp. ''hill.cpp'' – zdrojový soubor v C/Cpp || ^ Argumenty programu | žádné || ^ Kompilace pro jazyk C | clang -Wall -Werror -pedantic -std=c99 clang -Wall -Werror -pedantic -std=c+ +17 || ^ Kompilace a spuštění \\ pro jazyk Java | javac *.java java -classpath Hill || ^ Očekávaná složitost | Výpočet pomocných tabulek v čase cca $\mathcal{O}(n^2)$ || | ::: | Nalezení cesty v čase cca $\mathcal{O}(n)$ || ^ Procvičované oblasti | dynamické programování memoizace || ^ Bodové hodnocení (celkem 6 bodů) | 1 bod | parametr ''lift'' - kopec_1_01 – kopec_1_08 + 4 skryté testy | | ::: | 1 bod | parametr ''piste'' - kopec_1_01 – kopec_1_08 + 4 skryté testy | | ::: | 2 body | parametr ''lift'' - kopec_2_01 – kopec_2_08 + 8 skrytých testů \\ řešení časově stejné nebo lepší než referenční řešení | | ::: | 2 body | parametr ''piste'' - kopec_2_01 – kopec_2_08 + 8 skrytých testů \\ řešení časově stejné nebo lepší než referenční řešení | ^ Maximální počet uploadů | ''20'' Více uploadů je možných s odpovídající bodovou ztrátou ||