Summor Logo

3. Sökalgoritmer och agenter

Från modell till strategi

Alla AI-problem kräver inte maskininlärning. Sökalgoritmer låter oss utforska möjliga tillstånd steg för steg tills vi hittar en lösning. I den här lektionen jämför vi bredden-först-sökning (BFS), djupet-först-sökning (DFS) och heuristiska varianter som *A (A-stjärna)**.

Tillstånd kan du tänka på som “var du står just nu” – ett rum i skolan, en ruta i ett spel eller en plats på kartan. Handling är dörren du går genom eller draget du gör som tar dig till nästa läge. När vi beskriver ett problem som tillstånd och handlingar kan algoritmen testa ett steg i taget utan att behöva förstå hela världen på en gång.

När är sök bättre?

  • Problemet kan beskrivas som tillstånd och handlingar (spel, pussel, rutter).
  • Det finns tydligt mål och vi kan utvärdera hur nära målet vi är.
  • Vi behöver lösning nu, inte en modell för framtida data.

Så arbetar BFS och DFS

Tänk att du letar efter sal F3 i skolans huvudbyggnad:

  1. Entrén (Start) har två korridorer: vänster mot A-klassrum och höger mot B-klassrum.
  2. Varje korridor delar sig vidare i mindre gångar (A1, A2 … resp. B1, B2 …).

BFS i samma scenario

  • Du besöker först båda huvudkorridorerna för att se vad de leder till.
  • Därefter går du ett steg längre ned i varje korridor och kartlägger alla rum på nästa nivå innan du går vidare.
  • Fördel: du hittar den kortaste vägen till F3 om alla korridorer är lika långa.

DFS i samma scenario

  • Du väljer en korridor (säg A) och följer den hela vägen tills det tar stopp eller du hittar F3.
  • Om du misslyckas går du tillbaka till senaste vägskäl och provar nästa gren.
  • Fördel: du behöver bara hålla koll på den aktuella vägen (lite minne), men riskerar att lägga lång tid på fel gren.

Vilken beskrivning stämmer bäst in på hur DFS söker efter sal F3 i exemplet?

graph TD S([Start]) --> A1[Steg 1] S --> B1[Steg 2] A1 --> A2[Steg 1a] A1 --> A3[Steg 1b] B1 --> B2[Steg 2a] B1 --> B3[Steg 2b]
  • BFS utforskar nivå för nivå (radvis). Alla steg som ligger lika långt bort besöks innan vi går vidare. Resultat: hittar kortaste väg när varje steg kostar lika mycket men kräver mer minne.
  • DFS följer en gren tills den tar slut. Resultat: kräver lite minne men riskerar att fastna långt bort innan den hittar målet.

Tänk på BFS som att läsa sida för sida i en bok, medan DFS är att följa en berättelsegren hela vägen till slutet innan du går tillbaka och testar nästa.

Vilken egenskap har BFS men inte DFS om alla bågar har samma kostnad?

Heuristik och A*

  • Heuristik är en snabb tumregel som uppskattar hur långt det är kvar till målet. Exempel: i en stad kan fågelvägen ge en grov uppskattning av gångavståndet.
  • A* kombinerar faktiska kostnader (hur långt vi gått hittills) med heuristiken (hur långt vi tror det är kvar). Summan styr vilken nod som utforskas först.
  • Om heuristiken aldrig överskattar (är admissibel) garanterar A* fortfarande den kortaste vägen, men använder mindre tid än BFS.

Mini-exempel: kostnader i A*

Föreställ dig tre rum på rad: Start → Bibliotek → Laboratorium (målet). Varje gång har en faktisk kostnad (hur långt vi redan gått) och en heuristik (uppskattning av avståndet till labbet):

NodFaktisk kostnad g(n)Heuristik h(n)Summa f(n) = g+h
Start066
Bibliotek426
Laboratorium606

A* väljer alltid den nod med lägst f. Start och Bibliotek är lika lovande (6), men när vi expanderar Bibliotek ser vi att Laboratorium också har f = 6 och är målet. Heuristiken guidar oss genom att säga “det är bara två minuter kvar” så vi prioriterar rätt korridor utan att prova alla andra rum först.

Vad innebär det att heuristiken i A* är admissibel?

Ge ett exempel på en enkel heuristik för att hitta rätt rum i en skola och förklara varför den kan vara hjälpsam.

Jämförelse mot ML

Reflektera i loggen:

  • Vilka problem löser sökalgoritmer bättre än ML?
  • När är ML överlägset?
  • Hur skulle du kombinera sök och ML (t.ex. spel-AI med heuristisk beräkning)?

Exempel

Ett spel som schack använder ofta sökträd (för att utforska drag) men kompletterar med ML för att bedöma ställningar snabbare.

📚 Viktiga begrepp

Se till att du kan förklara dessa begrepp med egna ord:

  • • Tillståndsrum
  • • BFS
  • • DFS
  • • A*
  • • Heuristik

Framsteg

0/0