Denna webbapplikation ger dig möjlighet att se en grafisk representation av en rad olika algoritmer för grafisk sökning, samtidigt som du löser ett urval av 8 pusselproblem.
Komma igång
På den vänstra sidan av den här applikationen ser du kontrollpanelen. Med hjälp av kontrollpanelen kan du konfigurera följande aspekter av programmet:
- Initial State och Goal State
- Vilken sökalgoritm som ska användas
- Vilken heuristisk funktion som ska användas, om du använder en informerad sökalgoritm
- Och om du ska använda single-step- eller burst-läge
Varje av dessa alternativ kommer att beskrivas mer ingående nedan.
Initial- och måltillstånd
För att ställa in initial- eller måltillståndet kan du klicka antingen på knappen ”Redigera tillstånd” eller på den grafiska representationen av tillståndet.
Du bör få se en popupruta som följande:
För att ändra en bricka klickar du helt enkelt på den bricka du vill byta ut, och skriver sedan in det nya värdet på ditt tangentbord. Detta kommer att byta ut brickan mot den som tidigare innehöll det värdet.
Sökalgoritm
N-Puzzle har stöd för fem olika grafbaserade sökalgoritmer. De tre första är oinformerade sökalgoritmer:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
Den andra två är informerade sökalgoritmer:
- A* Search
- Greedy Search
Om du väljer en informerad sökalgoritm måste du också välja en heuristisk funktion.
Heuristisk funktion
N-Puzzle har stöd för tre olika heuristiska funktioner:
- Euklidisk distans
- Manhattan-distans (avstånd mellan stad och kvarter)
- Fliser som inte är på rätt plats
Single-Step eller Burst Mode
N-Puzzle kan användas i två lägen. Standardläget är Single-Step-läge, vilket gör att du kan ”spola tillbaka” en sökning, ett steg i taget. Detta är användbart för att få en bättre förståelse för hur en sökalgoritm fungerar.
Det andra läget är Burst-läget. När det väl har startats fortsätter Burst Mode att köra en sökning tills måltillståndet har hittats. En sökning i Burst Mode kan pausas, men kan inte ”spolas tillbaka”.
Sökträdet
State Representation
Medans en sökning är aktiv kommer du att kunna se en visuell representation av sökträdet. Varje nod i detta sökträd representerar ett arrangemang av brickor (eller tillstånd) och ritas som en ruta som är uppdelad i fyra sektioner.
Följande diagram visar en nod hämtad från en Greedy-sökning:
Den största sektionen är pusseltillståndet. Under den ser du två mindre sektioner.
Under pusseltillståndet finns två sektioner. Avsnittet till vänster är nodens djup. Avsnittet till höger är den heuristiska poängen. Den heuristiska poängen används endast med informerade sökalgoritmer, så om du använder Breadth-first, Depth-first eller Iterative Deepening Search kommer den heuristiska poängen att utelämnas.
Den sista sektionen registrerar i vilken ordning noderna expanderades. Till exempel kommer rotnoden alltid att vara ”#1” och nästa nod som expanderas markeras som ”#2”.
Node Colours
För att göra sökträdet mer ”läsbart” är gränsen för varje nod färgkodad baserat på dess aktuella tillstånd.
Följande diagram visar A*-algoritmen (med den euklidiska avståndsheuristiken) tillämpad på ett problem som kan lösas på bara två drag:
Färgerna kan tolkas på följande sätt:
| Färg | Betydelse |
|---|---|
| Blå | Om en nod finns i den öppna listan kommer den att markeras med blå färg. |
| Röd | Efter varje iteration av en sökalgoritm markeras den nod som expanderas nästa gång med rött. Detta gäller även när målnoden har hittats. |
| Grå | Om ett tillstånd har utforskats kommer det att vara grått. I steg 2) i diagrammet ovan har till exempel det inledande tillståndet färgats grått för att visa att det har utforskats. I steg 3) återupptäcks en nod som representerar initialtillståndet, men den kommer inte att expanderas eftersom initialtillståndet har expanderats via rotnoden. |
| Grönt | När måltillståndet har hittats kommer det att markeras med grön färg. |
| Guld | När en nod som representerar måltillståndet har hittats kommer alla noder på vägen tillbaka till rotnoden att markeras med guld. |
| Lila | När man använder Iterativ fördjupningssökning kommer outforskade noder som överskrider det maximala djupet inte att läggas till i den öppna listan. Dessa noder kommer att färgas lila. |
Öppna och stängda listor
Under tiden som sökalgoritmerna körs upprätthålls två listor. Den första är Open List – den används för att hålla reda på noder som har upptäckts, men ännu inte utforskats.
Den andra är Closed List – den används för att hålla reda på noder som har utforskats, eller noder som inte kommer att utforskas eftersom de representerar tillstånd som redan har utforskats via andra noder.
När en sökning är aktiv kommer antalet noder i Open och Closed Lists att vara synligt i det övre vänstra hörnet:
