Zoekproblemen

Zoekproblemen zijn vraagstellingen waarbij het doel is om een reeks acties te vinden die leidt van een begintoestand naar een gewenste eindtoestand. Een zoekprobleem wordt meestal beschreven door vijf componenten: de beginstaat, een set mogelijke acties (of operatoren), een overgangsmodel dat aangeeft welke toestand volgt uit welke toestand, een doeltoestand of doeltest, en vaak een kostenfunctie die de lengte of moeite van een pad meet. Een oplossing bestaat uit een pad in de zoekruimte, vaak uit opeenvolgende toestandsovergangen.

De zoekruimte kan worden weergegeven als een boom of een graf, waarbij knopen toestanden voorstellen en randen acties. Zoekproblemen kunnen onbewust (zonder heuristiek) worden opgelost met eenvoudige strategieën zoals breadth-first search, depth-first search en uniform-cost search. Daarnaast bestaan geïnformeerde methoden die gebruikmaken van heuristieken om gericht te zoeken, bijvoorbeeld greedy search en A*. Ideeën zoals IDA* combineren diepe zoekingen met iteratieve verkenning.

Belangrijke eigenschappen van zoekalgoritmen zijn volledigheid (of ze altijd een oplossing vinden als die bestaat), optimaliteit (of de gevonden oplossing minimaal is) en de benodigde geheugenruimte. Deze eigenschappen hangen af van de kenmerken van de zoekruimte en de gebruikte strategie, zoals de takbreedte, de diepte van de oplossing en de kosten.

Heuristieken zijn functies die een schatting geven van de resterende kosten naar het doel. Een admissibele heuristiek overschat nooit, en een consistente heuristiek houdt rekening met de transitiekosten tussen toestanden. Voorbeelden van toepassingen zijn robotnavigation, routeplanning, puzzels (zoals de 8-puzzel) en automatisering van logistiek en planning.

Zoekproblemen vormen een fundamenteel concept in kunstmatige intelligentie en operationele onderzoeksproblemen, en worden vaak als basis gebruikt voor meer complexe taken zoals planning en satisfiability. Limitaties omvatten de exponentiële toename van de zoekruimte bij grotere problemen.