Utforska BFS, DFS, Girig bäst-först och A* – se hur de hittar vägen genom en labyrint steg för steg.
Kostnadsfunktion: (håll musen över en cell för att se f(n))
Förklaringar
Vit (vanlig väg, kostnad 1) – Skapas genom att vänsterklicka på en svart ruta.
Svart (vägg) – Skapas genom att vänsterklicka på en vit ruta.
Brun (kostnad 3) – Skapas genom att högerklicka 2 gånger.
Blå (kostnad 5) – Skapas genom att högerklicka 3 gånger.
Röd (mål) – Skapas genom att högerklicka en gång.
Ljusblå (genomsökt) – Visas automatiskt av algoritmen för rutor som sökts igenom.
Orange (Kö) – Markering av algoritmens kö, alltså de rutor som ligger på tur att utforskas.
Grön (start) – Anger startposition för sökningen. Klicka och dra för att flytta.
Vänsterklick cyklar bara mellan svart och vit på en cell. Högerklick cyklar mellan röd → brun → blå → svart → röd.
Tips: Vid A*-sökning kan du hålla muspekaren över en ruta för att se f(n)-värdet (kostnadsfunktionen).
Sökalgoritmer i labyrint
Hur hittar en algoritm vägen genom en labyrint? Här kan du se fyra olika sökalgoritmer in action och jämföra hur de fungerar.
1
Välj en labyrint – Ladda en av de fördefinierade labyrinterna, eller bygg en egen genom att klicka på rutnätet. Vänsterklick skapar/tar bort väggar, högerklick sätter mål och kostnadsrutor.
2
Välj algoritm och sök – Testa BFS (bredden först), DFS (djupet först), Girig bäst-först eller A*. Tryck Starta sökning och se hur algoritmen utforskar labyrinten steg för steg.
3
Jämför algoritmerna – Kör samma labyrint med olika algoritmer. Vilken hittar kortaste vägen? Vilken utforskar minst rutor? Aktivera Stegvis för att följa sökningen ett steg i taget.
💡 Tips: Med A* kan du hålla musen över en ruta under sökningen för att se kostnadsfunktionen f(n) = g(n) + h(n) – den kombination av faktisk kostnad och uppskattad återstående kostnad som gör A* så effektiv.