Hoppa till huvudinnehåll

Vad är en sökalgoritm?

En sökalgoritm är ett smart sätt för datorn att ta reda på hur man går från ett startläge till ett mål , t.ex. att hitta den bästa vägen i en labyrint eller spelet Pac-Man!

Sökalgoritmer används i allt från spel, robotar och navigation till problem-lösning och pussel.

Ett sökproblem består av:​

  • Tillståndsrum: Alla möjliga lägen (states) du kan befinna dig i
  • Starttillstånd: Där sökningen börjar
  • Måltillstånd: Det du vill nå , t.ex. målet i en labyrint
  • Operatorer: Regler som beskriver hur du kan röra dig eller förändra tillståndet
  • Lösning: En sekvens av drag från start till mål

Varför är sökalgoritmer viktiga?​

Sökalgoritmer är grunden för intelligent beteende i datorprogram.
De gör det möjligt för en dator att:

  • Ta beslut
  • Lösa problem steg för steg
  • Navigera i komplexa miljöer
  • Hitta optimal eller tillräckligt bra lösning utan att prova allt

Två typer av sökalgoritmer​

Det finns många olika sökalgoritmer, men de delas oftast in i två huvudkategorier:

  • Vet ingenting om var målet finns
  • Utforskar alla vägar systematiskt
  • Exempel:

BFS , Bredden Först-Sökning​

  • Går igenom alla alternativ på samma nivå innan den går djupare
  • Hittar alltid den kortaste vägen (om kostnaderna är lika)

DFS , Djupet Först-Sökning​

  • Går så djupt som möjligt innan den backar
  • Effektiv men kan hamna fel (t.ex. i en återvändsgränd)
  • Använder extra information (heuristik) för att fatta smartare beslut
  • Kan hitta lösningen snabbare
  • Exempel:

A* (A-stjärna)​

  • Kombinerar faktiskt avstånd + uppskattat avstånd till målet
  • Mycket effektiv i spel och navigation
  • Väljer alltid det alternativ som ser bäst ut just nu
  • Snabb, men inte alltid optimal

Var används sökalgoritmer?​

Du hittar sökalgoritmer i många sammanhang:

  • Spel (t.ex. Pac-Man, schack, Zelda)
  • Pussel (t.ex. 8-pussel, Sudoku)
  • Robotnavigering
  • GPS och karttjänster
  • Planering och problemlösning
  • AI-karaktärer som ska hitta vägen

Sammanfattning​

  • AI = artificiell intelligens = få datorer att bete sig intelligent
  • Det finns regelbaserad AI (som sökalgoritmer) och lärande AI (ML)
  • Sökalgoritmer är en viktig del av AI , de används för att hitta lösningar på problem
  • De delas in i oinformerade (BFS, DFS) och informerade (A*, Greedy)
  • Du ser dem i spel, appar, robotar och mycket mer!

I nästa avsnitt kommer vi dyka djupare in i DFS , Djupet Först-Sökning
och se hur vi kan implementera det i Python för att styra Pac-Man!

Let’s go!