Dette webprogram giver dig mulighed for at se en grafisk repræsentation af en række forskellige algoritmer til grafsøgning, mens du løser et udvalg af 8 puslespilsproblemer.
Kom i gang
I venstre side af programmet kan du se kontrolpanelet. Ved hjælp af kontrolpanelet kan du konfigurere følgende aspekter af programmet:
- Initial State og Goal State
- Hvilken søgealgoritme der skal bruges
- Hvilken heuristisk funktion der skal bruges, hvis du bruger en informeret søgealgoritme
- Og om du vil bruge single-step eller burst-tilstand
Hver af disse muligheder vil blive beskrevet mere detaljeret nedenfor.
Initial- og måltilstand
For at indstille Initial- eller måltilstandene kan du klikke på enten knappen ‘Rediger tilstand’ eller på den grafiske repræsentation af tilstanden.
Du bør se en popup som følgende:
For at ændre en flise skal du blot klikke på den flise, som du vil udskifte, og derefter indtaste den nye værdi på dit tastatur. Dette vil bytte flisen med den flise, der tidligere havde denne værdi.
Søgealgoritme
N-Puzzle understøtter fem forskellige grafbaserede søgealgoritmer. De tre første er uinformerede søgealgoritmer:
- Breadth-first Search
- Depth-first Search
- Iterativ uddybende søgning
De to andre er informerede søgealgoritmer:
- A* Search
- Greedy Search
Hvis du vælger en informeret søgealgoritme, skal du også vælge en heuristisk funktion.
Heuristisk funktion
N-Puzzle understøtter tre forskellige heuristiske funktioner:
- Euklidisk afstand
- Manhattan-afstand (afstand mellem by og blokke)
- Fliser ude af sted
Enkeltrins- eller bursttilstand
N-Puzzle kan bruges i to tilstande. Standardtilstanden er Single-Step-tilstand, som giver dig mulighed for at “spole” en søgning tilbage, et trin ad gangen. Dette er nyttigt for at få en bedre forståelse af, hvordan en søgealgoritme fungerer.
Den anden tilstand er Burst-tilstand. Når den er startet, fortsætter Burst Mode med at køre en søgning, indtil måltilstanden er fundet. En søgning i Burst Mode kan sættes på pause, men kan ikke “spoles tilbage”.
Søgetræet
Statusrepræsentation
Medens en søgning er aktiv, vil du kunne se en visuel repræsentation af søgetræet. Hver knude i dette søgetræ repræsenterer et arrangement af brikker (eller tilstand) og er tegnet som en boks, der er opdelt i 4 sektioner.
Det følgende diagram viser en knude taget fra en Greedy-søgning:
Den største sektion er puslespilstilstanden. Under den ser du to mindre sektioner.
Under puslespilstilstanden er der to sektioner. Afsnittet til venstre er dybden af knuden. Afsnittet til højre er den heuristiske score. Den heuristiske score bruges kun med informerede søgealgoritmer, så hvis du bruger Breadth-first, Depth-first eller Iterative Deepening Search, vil den heuristiske score blive udeladt.
Den sidste sektion registrerer den rækkefølge, i hvilken knuderne blev udvidet. F.eks. vil rodknuden altid være “#1”, og den næste knude, der udvides, vil blive markeret som “#2”.
Nodefarver
For at gøre søgetræet mere “læsbart” er grænsen for hver knude farvekodet baseret på dens aktuelle tilstand.
Det følgende diagram viser A*-algoritmen (med den euklidiske afstandsheuristik) anvendt på et problem, der kan løses på kun to træk:
Farverne kan fortolkes på følgende måde:
Farverne kan fortolkes som følger:
| Farve | Betydning | |
|---|---|---|
| Blå | Hvis en node er i den åbne liste, vil den blive fremhævet med blå farve. | |
| Rød | Efter hver iteration af en søgealgoritme vil det knudepunkt, der skal udvides næste gang, blive fremhævet med rødt. Dette gælder også, selv om målknuden er fundet. | |
| Grå | Hvis en tilstand er blevet udforsket, vil den blive gråtonet. I trin 2) i diagrammet ovenfor er den indledende tilstand f.eks. blevet farvet grå for at angive, at den er blevet udforsket. I trin 3) genopdages en knude, der repræsenterer den indledende tilstand, men den vil ikke blive udvidet, da den indledende tilstand er blevet udvidet via rodknuden. | |
| Grøn | Når måltilstanden er fundet, vil den blive fremhævet med grøn farve. | |
| Guld | Når en knude, der repræsenterer måltilstanden, er fundet, vil alle knuder på vejen tilbage til rodknuden blive fremhævet med guld. | |
| Lilla | Ved brug af Iterativ uddybningssøgning vil uudforskede knuder, der overstiger den maksimale dybde, ikke blive føjet til den åbne liste. Disse knuder vil blive farvet lilla. |
Opne og lukkede lister
Mens søgealgoritmerne kører, vedligeholdes der to lister. Den første er Open List – den bruges til at holde styr på knuder, der er blevet opdaget, men endnu ikke udforsket.
Den anden er Closed List – den bruges til at holde styr på knuder, der er blevet udforsket, eller knuder, der ikke vil blive udforsket, fordi de repræsenterer tilstande, der allerede er blevet udforsket via andre knuder.
Når en søgning er aktiv, vil antallet af knuder i de åbne og lukkede lister være synligt i øverste venstre hjørne:
