søgealgoritmer

Søgealgoritmer er procedurer til at finde et bestemt element eller et sæt elementer i en datastruktur eller i et søgeområde. De vælges ofte ud fra dataens struktur, krav til ydeevne og om elementerne er ordnede. Målet kan være at finde et element, fastslå at det ikke forekommer, eller at finde den korteste eller billigste løsning i et givent søgeområde.

Lineær søgning undersøger elementer i en samling i rækkefølge og kræver ingen forudgående ordning. I værste fald gennemløbes alle elementer, hvilket giver O(n). Hvis data er sorteret, kan binær søgning bruges, hvor området halveres ved hvert trin og kompleksiteten er O(log n).

I grafbaserede søgninger skelnes ofte mellem bredde-først søgning (BFS) og dybde-først søgning (DFS). BFS udforsker noderne niveau for niveau og kan give korte løsninger i uvejlede grafer. DFS går længere ned ad en sti og kan bruge mindre hukommelse i nogle tilfælde. For korteste sti i vægtede grafer findes Dijkstra's algoritme, normalt med en heap, hvilket giver O((n+m) log n) tid. Bellman-Ford kan håndtere negative vægte. A* algoritmen tilføjer en heuristik og kan fremskynde søgningen ved at prioritere noder tættere på målet.

Inden for søgning i tilstandsrummene bruges teknikker som best-first søgning og heuristisk søgning, herunder iterative deepening og backtracking, afhængigt af problemets krav til fuldkommenhed og hukommelsesforbrug. Mange praktiske systemer kombinerer flere metoder gennem domæne-specifikke heuristikker og forbehandling.

Valg af søgealgoritme afhænger af dataets størrelse og struktur, ønsket om optimalitet og tilgængelig hukommelse. En sorteret liste kan drage fordel af binær søgning; større grafbaserede søgeproblemer kræver ofte A* eller Dijkstra med passende datastrukturer for at opnå effektivitet.