Zoekruimte

Zoekruimte, in informatica en aanverwante vakgebieden, verwijst naar het geheel van alle mogelijke toestanden of kandidaatoplossingen die door een algoritme verkend kunnen worden om een probleem op te lossen. De exacte samenstelling van de zoekruimte wordt bepaald door de probleemdefinitie: variabelen, mogelijke waarden (domeinen) en eventuele beperkingen.

De structuur van de zoekruimte kan een boom, een graaf of een combinatie daarvan zijn. Elk knooppunt vertegenwoordigt een toestand en elke tak een handeling of transitie die naar een nieuwe toestand leidt. De grootte van de zoekruimte kan exponentieel zijn, waardoor het uitvoerig onderzoeken van alle mogelijkheden onhaalbaar wordt. In veel gevallen is het doel om de ruimte efficiënt te verkennen zonder volledige dekking.

Om het zoeken haalbaar te maken, worden technieken toegepast om de effectieve zoekruimte te verkleinen of de verkenning gericht te sturen. Voorbeelden zijn heuristische zoekmethoden zoals A, die een schatting geeft van de resterende inspanning; pruningsmethoden zoals branch-and-bound; constraint propagation en probleemherformulering; lokale zoekmethoden en approximation methods. Deze aanpakken proberen vaak een balans te vinden tussen volledigheid en efficiëntie.

Zoekruimtes komen voor in diverse domeinen, waaronder kunstmatige intelligentie, planning, taak- en oplossingsoptimalisatie en satisfiability-problemen. De keuze van algoritme hangt af van gewenste garanties (volledigheid, optimaliteit) en van de kenmerken van de ruimte (finite of infinite, discretiseerbaar, beschikbaarheid van heuristieken). Een concreet voorbeeld is een reisschema-optimalisatie, waarbij elke toestand een gedeeltelijk bezochte route is en de doeltoestand een minimumkostenschema oplevert.