HW01 Prohledávání do hloubky
Zahradník se stará o zahradní bludiště. Do bludiště přichází mnoho návštěvníků a zahradník nechce chod v bludišti omezovat na dlouhou dobu. Proto potřebuje vyhledat cesty, kterými při průchodu bludištěm musí projít každý návštěvník a pro úpravu kterých tudíž musí být bludiště uzavřené. Pomozte zahradníkovi tyto cesty v bludišti vyhledat.
Na vstupu je dáno obdélníkové bludiště – viz předloha níže. Šířka bludiště je dána počtem znaků na prvním řádku. Délka bludiště je dána počtem načtených řádků. Keře v bludišti, kterými jsou ohraničené cesty, jsou v bludišti označeny znakem #, průchozí místa znakem . (tečka). Do bludiště se vchází vlevo nahoře a vychází se vpravo dole.
Výstupem programu je bludiště, v němž jsou místa, kudy je nevyhnutné projít (dále označeno jako „hledaná místa“) vyznačena znakem ! (vykřičník).
Kontrola vstupu
Bludiště na vstupu kompletně načtěte. Zkontrolujte, zda je bludiště korektně zadané. Kontrola vstupu a případné vypsání chyby musí být provedeno v následujícím pořadí:
Error: Bludiste neni obdelnikove! – některý z řádků má jinou délku než první řádek
Error: Vstup neni vlevo nahore! – druhý znak v prvním řádku není .
Error: Vystup neni vpravo dole! – předposlední znak v posledním korektně načteném řádku není .
Error: Sirka bludiste je mimo rozsah! – šířka bludiště (počet znaků na řádku) musí být v rozmezí 5 až 100 znaků
Error: Delka bludiste je mimo rozsah! – délka bludiště musí být v rozmezí 5 až 50 řádků
Error: Bludiste obsahuje nezname znaky! – znak na vstupu není # nebo .
Error: Bludiste neni oplocene! – neplatí, že kromě vstupu a výstupu z bludiště jsou všechny znaky po obvodu bludiště #
Error: Cesta neexistuje! - neexistuje ani jedna cesta bludištěm
Detekovanou chybu na chybovém výstupu vypište a program ukončete. Vypsané chybové hlášení je ukončeno koncem řádku (znakem \n).
Algoritmus řešení úlohy
Cesty procházení bludištěm lze získat metodou prohledávání do hloubky s možností opravy, pokud vejdeme do „slepé“ uličky (backtracking). Tímto algoritmem dokážeme poměrně jednoduše najít jednu cestu bludištěm. Úloha požaduje prohledání stavového prostoru problému a vyhledání všech možných cest v bludišti tak, abychom dokázali vyhledat místa, kudy všechny cesty bludištěm prochází. Právě tato místa potřebuje zahradník znát, aby věděl, kdy má bludiště uzavřít.
Vzhledem k exponenciální časové složitosti tohoto postupu řešení problému je vhodné se zamyslet nad optimalizací řešení. Při hledání optimálního řešení mohou napomoci následující úvahy:
Všechna hledaná místa se nachází již na první nalezené cestě bludištěm
Hledanými místy jsou vstup do bludiště a výstup z bludiště
Části první nalezené cesty, které tvoří cyklus s některou z dalších možných cest bludištěm nejsou hledanými místy – dají se obejít po druhé části cyklu
Když hledané místo zahradíme (například znakem #), cesta bludištěm nebude existovat. Naopak, když zahradíme místa, která nejsou takto exponovaná, cestu bludištěm najdeme snadno.
Vhodným zahrazením cest v bludišti fiktivními „keři“ lze značně omezit počet možných cest a značně urychlit nalezení řešení
Při procházení bludištěm se v každém kroku lze (s ohledem na rozmístění keřů) rozhodnout, zda další cesta půjde vlevo nebo vpravo, nahoru nebo dolů. Zvažte, zda vhodná posloupnost prohledání těchto možností (například vlevo, nahoru, vpravo, dolů nebo dolů, nahoru, vlevo, vpravo) nedokáže ovlivnit efektivnost řešení. Uvažujeme cesty bludištěm z levého horního do pravého dolního rohu. Posloužit může i myšlenka topologického uspořádání vrcholů v grafu.
Časově nejefektivnější řešení budou bodově ohodnocena.
Kontrolní testy
Testovací soubory najdete zde.
Příklad 1 – blud_1_01
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
#.#####
#.....#
#####.#
| #!#####
#!#####
#!#####
#!!!!!#
#####!#
| žádný | 0 |
Příklad 2 – blud_1_02
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
##.###
#.####
..#####
#..$$$.#
#.##.##
| žádný | Error: Bludiste neni obdelnikove!
| 1 |
Příklad 3 – blud_1_03
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
##.###
#.####
#.####
#..$$$
#.##.#
| žádný | Error: Vstup neni vlevo nahore!
| 1 |
Příklad 4 – blud_1_04
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
..#####
#..$$.#
#.#####
| žádný | Error: Vystup neni vpravo dole!
| 1 |
Příklad 5 – blud_1_05
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.##
#.##
..##
#..$
#..#
| žádný | Error: Sirka bludiste je mimo rozsah!
| 1 |
Příklad 6 – blud_1_06
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
..#####
#..$$.#
| žádný | Error: Delka bludiste je mimo rozsah!
| 1 |
Příklad 7 – blud_1_07
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
..#####
#..$$.#
#.###.#
| žádný | Error: Bludiste obsahuje nezname znaky!
| 1 |
Příklad 8 – blud_1_08
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
..#####
#.....#
#.###.#
| žádný | Error: Bludiste neni oplocene!
| 1 |
Příklad 9 – blud_1_09
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
#.#####
#....##
#####.#
| žádný | Error: Cesta neexistuje!
| 1 |
Příklad 10 – blud_1_10
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
#.#####
#....#
#####.#
| žádný | Error: Bludiste neni obdelnikove!
| 1 |
Správnost výpočtu
Příklad 9 – blud_2_01
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.....#
#.....#
#.....#
#####.#
| #!#####
#!....#
#.....#
#....!#
#####!#
| žádný | 0 |
Příklad 10 – blud_2_02
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#.#####
#...###
#.....#
#####.#
| #!#####
#!#####
#!..###
#..!!!#
#####!#
| žádný | 0 |
Příklad 11 – blud_2_03
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.#####
#....##
#.##.##
#.....#
#####.#
| #!#####
#!...##
#.##.##
#...!!#
#####!#
| žádný | 0 |
Příklad 12 – blud_2_04
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.###############
#...#...........#
#.###.#####.#.#.#
#...........#...#
###############.#
| #!###############
#!..#......!!!..#
#!###.#####.#.#.#
#!!!!!......#..!#
###############!#
| žádný | 0 |
Příklad 13 – blud_2_05
| Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
#.##########
#..........#
#.#.######.#
#.#......#.#
#.#.####.#.#
#.#....#.#.#
#.#.#..#.#.#
#.#.#.##.#.#
#.#......#.#
#.######.#.#
#..........#
##########.#
| #!##########
#!.........#
#.#.######.#
#.#......#.#
#.#.####.#.#
#.#....#.#.#
#.#.#..#.#.#
#.#.#.##.#.#
#.#......#.#
#.######.#.#
#.........!#
##########!#
| žádný | 0 |
Tyto testovací soubory najdete v přiloženém akchivu.
Další testy na správnost výpočtu jsou utajené.
Příklad 14 – Velké bludiště
Na následujícím příkladu lze testovat rychlost výpočtu na velkých bludištích. Bludiště není součástí testovací sady, ale podobá se časové náročným testům.
#.#############################
#..........................#..#
#.#####################.......#
#.............................#
##############.################
#................##..#...#...##
#############...###.##.#...#.##
#...................#..###.#.##
#################.####...#.####
#........................#....#
#.##########################..#
#.............................#
###########.#################.#
#.#.......#.#...#.#...#...#...#
#.#.#####.####..#.#.#.#.#.#.###
#.#.....#.......#.#.#.#.#.....#
#.###.#####.###.#.#.#.#.#.###.#
#.....#...#.#...#...#...#.#...#
#.....#.#...#.#########.#######
#.###.#.#.#.###.........#...#.#
#.....###.#...#.#########.#...#
#####...#####...#.........#...#
#.....###########....########.#
####.....##########.#######...#
########..........#.#.#.....#.#
#...####...########...#.#####.#
#.#.####.#####........#....##.#
#.#......####...###...###.###.#
#...######..#####...#####.###.#
###...............#######...#.#
#############################.#
Rychlost výpočtu
Rychlost je srovnávána v opakovaných testech s rychlostí (časem) výpočtu referenčního řešení. Bodově jsou hodnocena řešení, která potřebují čas menší než je trojnásobek času referenčního řešení.
Odevzdání a hodnocení
Úlohu je možné řešit v programovacím jazyce Java, Python nebo C/C++.
Veřejné testovací soubory - DSA_HW01.
| Název úlohy v BRUTE | HW01 |
| Odevzdávané soubory | maze.py – zdrojový soubor v python3 |
Maze.java – zdrojový soubor v Java, název třídy Maze |
maze.c, resp. maze.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 Maze
|
| Očekávaná složitost | lepší než $\mathcal{O}(n^4)$ |
| Koeficient pro čas výpočtu $3.0$ |
| Procvičované oblasti | prohledávání stavového prostoru do hloubky
backtracking
složitost úlohy a její optimalizace
|
| Bodové hodnocení (celkem 10 bodů) | 2 body | blud_1_01 – blud_1_10 + 5 skrytých testů |
| 3 body | blud_2_01 – blud_2_05 + 3 skryté testy |
| 5 bodů | blud_3_01 – blud_3_20 – ř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 |
