{{indexmenu_n>7}}
Obsah této stránky bude přístupný od 3. 4. 2017.
====== Prohledávání stavového prostoru ======
//Autor textu: Petr Benda// \\ //Úprava: Tibor Strašrybka//
Toto cvičení předpokládá základní znalost Javy a NetBeans IDE.
===== Část A =====
==== Zadání ====
Implementujte algoritmy prohledávání stavového prostoru do šířky a do hloubky. Implementujte je pomocí seznamů //OPEN// a //CLOSED//, pak se oba algoritmy liší minimálně. \\ Výstupem algoritmu bude první nalezená cesta mezi počátečním a koncovým uzlem, které zadá uživatel. Použijte připravené knihovny uživatelského rozhraní. Prohledávaný prostor je definován planárním grafem.
==== Pokyny k vypracování ====
- Stáhněte si ze stránky předmětu {{:courses:a3b33kui:cviceni:07_prohledavani_nastroj.zip?nocache|SW nástroj pro studenty}}. V [[http://netbeans.org/downloads|NetBeans IDE]] otevřete projekt z místa, kam jste jej rozbalili.
- V Netbeans IDE otevřete zdrojový soubor ''BFS.java''. Tento soubor modifikujte.
- Váš Program spustíte např. pomocí předpřipravené konfigurace ''bfs''. V případě, že máte potíže s používáním projektu na svém domácím počítači, následujte instrukce na stránce [[courses:a3b33kui:cviceni:07_nastaveni_java|řešení problémů s nastavením]], která bude průběžně aktualizována. Systém **lze také spustit v konzoli** za použití parametru ''noVisio'' (viz soubor ''runBFS_noviso.bat''), což může být vhodné pro ladění.
==== Poznámky k implementaci ====
* Nevytvářejte žádné další soubory, všechen potřebný kód umístěte do ''BFS.java''.
* Projděte si javadoc.
* Metoda ''node.isTarget()'' vrací ''true'', pokud se jedná o cílový uzel.
* K vykreslování nově expandovaných hran dochází automaticky při spuštění metody ''expand()''.
* Měli byste vědět, že uzly, na které přistupujete přes rozhraní ''kui.Node'', mají korektně naimplementované metody ''hashCode()'' a ''equals()''. **Vytvořit __třídu__ tak, že ji oddědíte od __rozhraní__ (Node), nelze.**
* Aby došlo k vykreslení nalezené cesty, je třeba výslednou cestu (resp. seznam po sobě jdoucích uzlů) vrátit z metody ''findWay()''.
* Váš algoritmus můžete spustit i bez NetBeans IDE tak, že spustíte ''Application.main'' s parametrem. Parametrem je jméno Vaší třídy včetně balíčků. Tento způsob spuštění používá ''runBFS.bat''.
* Pro zpomalení výpočtu můžete použít následující kód:
try {
Thread.sleep(10); // 10 ms
}
catch (InterruptedException ex) {
ex.printStackTrace();
}
==== Ovládání vizualizačního nástroje ====
Nastavení počátečního a koncového uzlu v grafu provedete kliknutím levého tlačítka myši, přiblížení a oddálení kolečkem myši. Pokud držíte pravé tlačítko myši, můžete pohybovat s mapou. Barva expandované hrany určuje dobu, kdy byla expandována. Nejstarší expandované hrany jsou zelené, následují modré, fialové, červené a nejmladší jsou žluté. \\ **Zadání nového hledání cesty je možné po stisknutí klávesy ''r''.**
===== Část B =====
==== Zadání ====
Implementujte algoritmus A*. Výstupem algoritmu bude nejkratší cesta mezi počátečním a koncovým uzlem, které zadá uživatel. Navrhněte a použijte heuristickou funkci. Použijte připravené knihovny uživatelského rozhraní. Prohledávaný prostor je definován planárním grafem.
==== Pokyny k vypracování ====
- V projektu si otevřete soubor ''AStar.java''. Tato třída implementuje rozhraní ''InformedSearchingAlgorithm''. Oproti předchozí úloze metoda ''findWay()'' obdrží jak startovní, tak i koncový uzel.
- Přepněte spouštěcí konfiguraci na ''astar'' (klikněte na šipečku combo boxu pro výběr konfigurace a vyberte ''astar'').
==== Poznámky k implementaci ====
Nevytvářejte žádné další soubory, všechen potřebný kód umístěte do ''AStar.java''.
==== Otázky ====
* Který z algoritmů obvykle vrací (v našem případě) kratší cestu?
* Kolik stavů „projde“ algoritmus BFS či DFS v nejhorším případě?
* V jakém smyslu je nalezená cesta algoritmem BFS nejkratší?
* Jaké podmínky musí splňovat heuristická funkce, aby byla zaručena správná funkce algoritmu A*?
* Co je to monotónní heuristická funkce?
* Jakou heuristickou funkci jste zvolili?
* Je ve Vašem případě potřeba implementovat algoritmus v plné obecnosti, či je možno provést nějaká zjednodušení?
===== Jak odevzdávat? =====
- Všechny tři úlohy (BFS, DFS, A*) se odevzdávají na příštím laboratorním cvičení.
- Do systému se odevzdávají dvě úlohy. Prohledávání do šířky a prohledávání pomocí A*. Vyučujícímu se odevzdává navíc prohledávání do hloubky.
- Vytvořte zip archiv, který bude obsahovat __adresář__ ''kui'' __a v něm__ budou __soubory__ ''BFS.java'' a ''AStar.java'' (v archivu může být i jen jeden soubor, automatický test se provede. Nicméně je potřeba, abyste nakonec odevzdali oba soubory!). Vkládání jiných souborů a souborů s jinými jmény není přípustné.
- Ve Vašich třídách nesmí být žádný kód pro zpomalení.
- Zip archiv vložte do [[https://cw.felk.cvut.cz/upload/secure/index.phtml|Upload systému CourseWare]]. Na jménu zip archivu nezáleží.
- Bude proveden automatický test (test může trvat maximálně asi 30 s, výsledky si můžete prohlédnout).
- Zip archiv můžete nahrávat do upload systému kolikrát chcete.
===== Bodování úlohy =====
^ algoritmus ^ prezentace kódu ^ automatické vyhodnocení na serveru ^ bonus ^
^ BFS/DFS | 2 b | 2 b | 1 b |
^ A* | 4 b | 2 b | 1 b |
^ Celkem: | **12 b** |||