sökmetod

En sökmetod är en systematisk metod för att utforska ett problemrum eller en datamängd i syfte att hitta en lösning, ett mål eller en relevant resurs. Sökmetoder används inom artificiell intelligens, datorvetenskap och informationssökning samt vid algoritmdesign där problemet kan beskrivas som en sökprocess mellan tillstånd.

Sökmetoder kan delas in i uninformerade (blind) och informerande (heuristiska) sökningar. Blinda metoder som BFS (breadth-first search) och DFS (depth-first search) utforskar utan att bedöma vilka tillstånd som verkar lovande. Andra exempel är iterativ fördjupning och uniform kostnadssökning. Informerade metoder använder heuristik för att styra sökandet, exempelvis best-first-sökning och A*-sökning. En bra heuristik är oftast admissibel (den överskattar inte kostnaden) och kan vara konsekvent.

Viktiga egenskaper hos sökmetoder är fullständighet (om metoden hittar en lösning när den finns), optimalitet (om den hittar den bästa lösningen) samt tids- och minneskomplexitet. Valet av metod beror på problemet: BFS garanterar fullständighet men kan vara mycket minneskrävande; DFS är minnesvänlig men kan sakna fullständighet och optimalitet i vissa fall. A*-sökning återger ofta god prestanda om heuristiken är bra.

Användningsområden inkluderar vägval i kartor, pussellösning (till exempel åtgärdssökning i spel), robotnavigation, optimeringsproblem och informationssökning i stora databaser. Begränsningar inkluderar den exponentiella tillväxten av sökrymden och risken för lokala optima i vissa heuristiska metoder.