naivesökning

Naivesökning, eller naive search, avser grundläggande sökalgoritmer som undersöker varje möjlig lösning i en sökrymd i en förutbestämd ordning tills ett mål hittas eller resurserna tar slut. Det kännetecknas av avsaknad av speciell domänkunskap eller heuristik som riktar sökningen mot sannolikt relevanta områden. Metoden används ofta som baslinje eller referens i teoretiska studier och i småskaliga tillämpningar.

Inom text- och mönstersökning innebär naïv sökning att varje position i texten jämförs med mönstret. Om textlängden är n och m är mönstrets längd, kan detta kräva upp till n−m+1 jämförelser av m tecken, vilket ger tidskomplexitet O(nm) i värsta fall. I andra problemrum kan naivsökning innebära att varje kandidat i en sökrymd kontrolleras mot målet innan nästa kontrolleras.

Fördelarna med naivsökning är enkelhet, få externa beroenden och minimal minnesanvändning. Nackdelarna är att metoden ofta blir ineffektiv vid stora sökrymder eller när målet är svårt att hitta; den utnyttjar ingen vägledning mot relevanta områden och kan vara ohållbar i praktiken.

Alternativ till naiv sökning är heuristiska eller optimal sökning, som A*-baserade metoder i väg- och planneringproblem, eller effektiva mönstersökningsalgoritmer som Knuth–Morris–Pratt och Boyer–Moore, vilka minskar antalet jämförelser.

Historiskt har termen naiv sökning använts inom datavetenskap för att beteckna en grundläggande, icke-optimal metod och som referens för att jämföra mer avancerade algoritmer.