Met deze webtoepassing kunt u een grafische weergave bekijken van een reeks verschillende grafische zoekalgoritmen, terwijl u een keuze maakt uit 8 puzzelproblemen.
Start
Aan de linkerkant van deze toepassing ziet u het configuratiescherm. Met behulp van het Configuratiescherm, kunt u de volgende aspecten van de toepassing configureren:
- Initiële staat en doel staat
- Welke zoekalgoritme te gebruiken
- Welke Heuristische functie te gebruiken, indien u een Informed Search Algorithm
- En of u single-step of burst mode wilt gebruiken
Elke van deze opties worden hieronder in meer detail beschreven.
Initiële en Doel staten
Om de Initiële of Doel staten in te stellen, kunt u klikken op ofwel de ‘Bewerk staat’ knop of de grafische representatie van de staat.
U zou een popup als de volgende moeten zien:
Om een tile te veranderen, klik eenvoudig op de tile die u wilt vervangen, voer dan de nieuwe waarde in op uw toetsenbord. De tegel wordt dan verwisseld met de tegel die eerder die waarde had.
Zoekalgoritme
N-Puzzle ondersteunt vijf verschillende op grafieken gebaseerde zoekalgoritmen. De eerste drie zijn niet-geïnformeerde zoekalgoritmen:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
De andere twee zijn geinformeerde zoekalgoritmen:
- A* Zoeken
- Greedy Zoeken
Als u een Informed Search Algorithm kiest, dan moet u ook een Heuristische Functie kiezen.
Heuristische functie
N-Puzzle ondersteunt drie verschillende heuristische functies:
- Euclidische afstand
- Manhattan-afstand (afstand tussen steden en blokken)
- Tiles Out-of-place
Single-Step or Burst Mode
N-Puzzle kan in twee modi worden gebruikt. Standaard is dit de Single-Step modus, waarmee u een zoekopdracht stap voor stap kunt ’terugspoelen’. Dit is handig om een beter begrip te krijgen van hoe een zoekalgoritme werkt.
De andere modus is de Burst-modus. Eenmaal gestart, gaat de Burst-modus door met zoeken totdat de doeltoestand is gevonden. Een zoekopdracht in de Burst-modus kan worden gepauzeerd, maar kan niet worden ’teruggespoeld’.
De zoekboom
Statusweergave
Terwijl een zoekopdracht actief is, kunt u een visuele weergave van de zoekboom zien. Elk knooppunt in deze zoekboom vertegenwoordigt een arrangement van tegels (of toestand), en wordt getekend als een vak dat is verdeeld in 4 secties.
Het volgende diagram toont een knooppunt uit een Greedy zoekactie:
De grootste sectie is de puzzel toestand. Daaronder zie je twee kleinere secties.
Onder de puzzel staat zijn twee secties. De sectie aan de linkerkant is de diepte van de knoop. De rechtse sectie is de heuristische score. De heuristische score wordt alleen gebruikt met Informed Search Algorithms, dus als je Breadth-first, Depth-first of Iterative Deepening Search gebruikt, zal de heuristische score weggelaten worden.
De laatste sectie registreert de volgorde waarin de knopen zijn uitgebreid. Bijvoorbeeld, de root node zal altijd ‘#1’ zijn, en de volgende node zal worden gemarkeerd als ‘#2’.
Node kleuren
Om de zoekboom meer ‘leesbaar’ te maken, is de rand van elke node gekleurd op basis van zijn huidige status.
Het volgende diagram toont het A* algoritme (met de Euclidische afstand heuristiek) toegepast op een probleem dat in slechts twee zetten kan worden opgelost:
De kleuren kunnen als volgt worden geïnterpreteerd:
| Kleur | Betekenis |
|---|---|
| Blauw | Als een knooppunt in de Open Lijst staat, wordt het blauw gemarkeerd. |
| Rood | Na elke iteratie van een zoekalgoritme wordt het knooppunt dat als volgende zal worden uitgebreid rood gemarkeerd. Dit geldt zelfs als het doel-knooppunt al gevonden is. |
| Grijs | Als een toestand al verkend is, wordt deze grijs weergegeven. Bijvoorbeeld, in stap 2) van het diagram hierboven, is de begintoestand grijs gekleurd om aan te geven dat deze is verkend. In stap 3) wordt een knoop die de begintoestand voorstelt opnieuw ontdekt, maar hij wordt niet uitgebreid omdat de begintoestand is uitgebreid via de wortelknoop. |
| Groen | Als de doeltoestand eenmaal is gevonden, wordt hij groen gemarkeerd. |
| Goud | Als een knoop die de doeltoestand vertegenwoordigt is gevonden, zullen alle knooppunten op het pad terug naar de hoofdknoop in goud worden gemarkeerd. |
| Paars | Als Iterative Deepening Search wordt gebruikt, zullen niet-ontdekte knooppunten die de maximale diepte overschrijden niet aan de open lijst worden toegevoegd. Deze knooppunten worden paars gekleurd. |
Open en gesloten lijsten
Terwijl de zoekalgoritmen worden uitgevoerd, worden twee lijsten bijgehouden. De eerste is de Open Lijst – deze wordt gebruikt om knooppunten bij te houden die ontdekt zijn, maar nog niet verkend.
De tweede is de Gesloten Lijst – deze wordt gebruikt om knooppunten bij te houden die verkend zijn, of knooppunten die niet verkend zullen worden omdat ze toestanden vertegenwoordigen die al verkend zijn via andere knooppunten.
Wanneer een zoekactie actief is, zal het aantal knooppunten in de Open en Gesloten Lijsten zichtbaar zijn in de linker bovenhoek:
