{{indexmenu_n>7}}
<timer 2000-01-01 00:00:01=2017-04-03 00:00:01>
Obsah této stránky bude přístupný od 3. 4. 2017.
</timer>

<timer 2017-04-03 00:00:01=->
====== 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 <wrap round download>{{:courses:a3b33kui:cviceni:07_prohledavani_nastroj.zip?nocache|SW nástroj pro studenty}}</wrap>. 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:
<code java>
try {
    Thread.sleep(10); // 10 ms
}
catch (InterruptedException ex) {
    ex.printStackTrace();
}
</code>

==== 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**  |||
</timer>