LEERKERN

9.2 Zoektechnieken

Introductie

In deze paragraaf worden enkele verschillende zoektechnieken gekarakteriseerd.

9.2.1 Basistypen zoektechnieken

Lees uit Stefik: paragraaf 2.1.2 (pagina 153 tot en met 156).

Stefik onderscheid vier basistypen zoektechnieken:
exhaustive search (uitputtend zoeken)
satisficing search (voldoende zoeken)
optimizing search (optimaal zoeken)
resource limited search (beperkt zoeken).
Hij geeft daarvan de karakteristieken en verschillen.
Op pagina 155 noemt hij nog een andere zoektechniek: due-process search. Dat zou vertaald kunnen worden met ‘overtuigend’ zoeken. Er wordt daarbij doorgezocht tot er een ‘overtuigende’ oplossing is gevonden.

In de meeste situaties waarin we een zoektechniek gebruiken, moeten we een compromis sluiten tussen de efficiëntie en de volledigheid van het zoekproces.
Beschouw bijvoorbeeld een computerprogramma voor het spelen van schaak. Als we bij het zoeken volledigheid zouden nastreven, zouden we alle spelvoortzettingen moeten berekenen die mogelijk zijn bij een gegeven positie. Als we hiertoe in staat zouden zijn, zouden we altijd de beste zet kunnen doen. Op dit moment bestaat er echter geen computer die dat kan, en zo’n computer zal waarschijnlijk nooit gebouwd kunnen worden. (Merk op dat indien zo’n computer zou bestaan, het schaakspel opgelost zou zijn. We zouden dan kunnen bepalen welke zet tot winst zou leiden, op voorwaarde dat beide spelers vervolgens altijd de beste vervolgzet doen. Het is overigens de vraag of er zo’n oplossing bestaat.)
Omdat het ook in dit geval ondoenlijk is om alle mogelijkheden te doorzoeken, vanwege de beperkte rekencapaciteit van mensen en machines, worden heuristieken gebruikt. Een heuristiek bij computerschaak is een waarderingsfunctie die als doel heeft in te schatten of een bepaalde zoekrichting vruchtbaar zal zijn. Een zet die leidt tot stukwinst zal beter zijn dan een zet die leidt stukverlies. Moderne schaakprogramma’s gebruiken uitgekookte algoritmes voor de waardering van posities. Op grond van deze waarderingen wordt die zet gedaan die leidt tot de positie met de hoogste waardering. Er is echter geen garantie dat de gekozen zet inderdaad de beste is. De beste zet kunnen we alleen bepalen door alle mogelijkheden te bekijken, dus wanneer we volledigheid hebben.

9.2.2 Zoekruimtes representeren

Lees uit Stefik: paragraaf 2.1.3 tot en met 2.1.5 (pagina 156 tot en met 159).

Als bomen worden gebruikt om zoekruimtes mee te representeren, kunnen oplossingen knopen in de boom zijn (eventueel alleen de bladeren), of de paden van de wortel van de boom naar de betreffende knoop. Beide mogelijkheden zijn in essentie equivalent, omdat er altijd maar één pad is van de wortel naar een bepaalde knoop.

> Opgave 9.2.1

> Opgave 9.2.2

> Opgave 9.2.3

> Opgave 9.2.4

> Opgave 9.2.5