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.

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.

1. Stáhněte si ze stránky předmětu SW nástroj pro studenty. V NetBeans IDE otevřete projekt z místa, kam jste jej rozbalili.
2. V Netbeans IDE otevřete zdrojový soubor BFS.java. Tento soubor modifikujte.
3. 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 ř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í.

• 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();
}

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.

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.

1. 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.
2. Přepněte spouštěcí konfiguraci na astar (klikněte na šipečku combo boxu pro výběr konfigurace a vyberte astar).

Nevytvářejte žádné další soubory, všechen potřebný kód umístěte do AStar.java.

• 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í?

1. Všechny tři úlohy (BFS, DFS, A*) se odevzdávají na příštím laboratorním cvičení.
2. 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.
3. 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é.
4. Ve Vašich třídách nesmí být žádný kód pro zpomalení.
5. Zip archiv vložte do Upload systému CourseWare. Na jménu zip archivu nezáleží.
6. Bude proveden automatický test (test může trvat maximálně asi 30 s, výsledky si můžete prohlédnout).
7. Zip archiv můžete nahrávat do upload systému kolikrát chcete.