Zoekalgoritme

In de informatica is een zoekalgoritme een algoritme dat in brongegevens zoekt naar bepaalde objecten. De verzameling gegevens waarin men zoekt wordt de zoekruimte genoemd. Eenvoudige zoekalgoritmen gebruiken algemene intuïtieve methoden om een oplossing te vinden, heuristische zoekalgortimen gebruiken een voorkennis omtrent de zoekruimte om sneller tot een resultaat te komen.

Eenvoudige zoekalgoritmen

Een eenvoudig zoekalgoritme houdt geen rekening met de specifieke aard van het probleem. Deze algoritmen kunnen abstract geformuleerd en geïmplementeerd worden. Ze kunnen voor een breed aantal problemen gebruikt worden. Deze methoden hebben als nadeel dat bij grote zoekruimtes de zoektijd onaanvaardbaar groot kan worden.

Zoeken in lijsten

De eenvoudigste zoekalgoritmen zoeken in lijsten (list search). Het doel is het vinden van één element in een verzameling dat voldoet aan een bepaalde eigenschap of een bepaalde waarde heeft. Deze problemen komen vaak voor in de informatica en hun complexiteit is goed bestudeerd. De eenvoudigste methode is lineair zoeken, waarbij de elementen in de lijst in volgorde afgelopen worden tot men het gewenste element vindt. De hoeveelheid tijd die nodig is voor deze methode is evenredig met de lengte van de lijst (O(n)), waarbij n het aantal elementen in de lijst is, maar de methode kan onmiddellijk op elke lijst worden toegepast. Een snellere methode voor gesorteerde lijsten is bisectie (binair zoeken), de zoektijd neemt dan logaritmisch toe met de lengte van de lijst (O(log n)). Deze methode levert een beduidend kortere zoektijd voor lange lijsten op, maar de lijst moet wel eerst gesorteerd worden en elk element moet direct toegankelijk zijn (random access). Interpolatiezoeken levert nog betere resultaten voor heel grote lijsten die redelijk evenwichtig verdeeld zijn. Grovers algoritme is een kwantumalgoritme dat kwadratisch sneller is dan het klassieke lineaire zoeken van ongesorteerde lijsten. In lijsten kan ook hashing gebruikt worden, zodat het zoeken in het beste geval een constante tijd O(1) heeft en in het slechtste geval O(n).

Zoeken in bomen

Veel zoektechnieken zijn gebaseerd op zoeken in bomen. De algoritmen zoeken in de knopen van een boom (deze kan expliciet gegeven zijn, of op het moment zelf gegenereerd zijn). Een zoekboom heeft bepaalde eigenschappen om de zoektijd te verkorten maar ook in ander soort bomen kan gezocht worden. Het basisprincipe is het volgende: het algoritme haalt een knoop uit een datastructuur, de opvolgers van deze knoop worden onderzocht en aan de datastructuur toegevoegd. Door manipulatie van deze gegevensstructuur kan de boom in verschillende volgordes worden doorzocht, zoals niveau per niveau (breadth-first search), of eerst zoeken tot men een bladknoop bereikt en vervolgens terugkeren (depth-first search). Andere methodes van zoeken in bomen zijn de iterative deepening depth-first search, depth-limited search, bidirectioneel zoeken en uniforme kost zoeken.

Zoeken in grafen

Diverse problemen in de grafentheorie kunnen opgelost worden met zoekalgoritmes, zoals het algoritme van Dijkstra, algoritme van Kruskal en het algoritme van Prim. Deze kunnen gezien worden als uitbreidingen van de zoekalgoritmes voor bomen.

Heuristisch zoeken

Een zoekmethode met voorkennis wordt een heuristiek gebruikt die specifiek is voor het probleem in kwestie. Een goede heuristiek kan de zoektijd drastisch reduceren ten opzichte van een gewoon zoekalgoritme.

Er zijn relatief weinig veelgebruikte zoekalgoritmes in lijsten die voorkennis gebruiken. Een van deze methoden is een hashtabel met een hashfunctie die bestaat uit een heuristiek voor het probleem. De meeste zoekalgoritmes met voorkennis maken gebruik van bomen. Enkele van deze methodes zijn beste-eerst zoeken en A*-algoritme. Net zoals bij de eenvoudige zoekalgoritmen kunnen ook deze uitgebreid worden naar grafen.

Resultaat

Aangezien het een algoritme betreft, levert de gehele zoekactie steeds een resultaat op. Weliswaar kan het resultaat zijn dat de zoekacties niets opleverde maar de melding dat het gezochte niet voorkomt is ook een resultaat.