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.
BFS.java
. Tento soubor modifikujte.
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í.
BFS.java
.
node.isTarget()
vrací true
, pokud se jedná o cílový uzel.
expand()
.
kui.Node
, mají korektně naimplementované metody hashCode()
a equals()
. Vytvořit třídu tak, že ji oddědíte od rozhraní (Node), nelze.
findWay()
.
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
.
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.
AStar.java
. Tato třída implementuje rozhraní InformedSearchingAlgorithm
. Oproti předchozí úloze metoda findWay()
obdrží jak startovní, tak i koncový uzel.
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
.
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é.
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 |