Introductie

Wat is een boom?

Een boomstructuur waarin belangrijke termen getoond worden.

De zoek algoritmen die hier behandeld worden, werken door middel van het doorlopen van een boom. Het algoritme specificeert de manier waarop dit gebeurt. Een boom bestaat uit een verzameling knopen. De knoop aan de top van de boom is de wortel. Een knoop kan nul of meer knopen onder zich hebben, dit zijn de kinderen van die knoop. De knopen die geen kinderen bevatten zijn de bladeren van de boom. Elke knoop heeft precies één ouder, met uitzondering van de wortel, deze heeft geen ouder. Een tak is een knoop inclusief alle knopen daaronder. De diepte van een knoop is gelijk aan het aantal (voor)ouders dat de knoop heeft. De doelknoop, of oplossing, is de knoop waarnaar gezocht wordt. De vertakkingsgraad is het aantal vertakkingen/kinderen die de knopen hebben.

Eigenschappen van zoekalgoritmen

De zoekalgoritmen beginnen met zoeken bij de wortel van de boom. Vervolgens worden de rest van de knopen op een door het algoritme bepaalde volgorde doorlopen. Er zijn ongeïnformeerde zoekalgoritmen die de boom op een vaste volgorde doorlopen en er zijn geïnformeerde zoekalgoritmen die gebruik maken van voorkennis om te bepalen in welke volgorde de knopen doorzocht worden. Bij het kiezen voor een algoritme zijn een aantal eigenschappen waar rekening mee gehouden moet worden.

Geheugengebruik

Het geheugengebruik wordt bepaald door het aantal knopen dat onthouden moet worden. Om het geheugengebruik te beperken, worden er bij sommige algoritmen knopen soms niet in het geheugen opgeslagen. Dit heeft als voordeel dat er minder geheugen gebruikt wordt, maar kan negatieve effecten hebben op andere eigenschappen, zoals de garantie op een oplossing. Het maximale geheugengebruik is het aantal knopen dat in het ergste geval onthouden moet worden.

Rekentijd

Een algoritme bezoekt de knopen stuk voor stuk om tot een oplossing te komen. Het aantal knopen dat doorzocht moet worden, bepaalt de rekentijd van een algoritme. Bij algoritmen die elke knoop in de boom maximaal één keer bezoeken is de rekentijd gelijk aan het aantal knopen in de boom.

Garantie op een oplossing

Algoritmen die garantie bieden op een oplossing vinden altijd een oplossing, onder de aanname dat er geen tijdslimiet en onbeperkt geheugen is. Er zijn ook algoritmen die niet gegarandeerd een oplossing vinden. Dit is het geval wanneer een algoritme slechts een beperkt aantal knopen onthoudt. Delen van de boom zijn dan niet meer bereikbaar. Doelknopen in dat deel van de boom kunnen dan niet meer gevonden worden. Een andere situatie waarin niet alle algoritmen gegarandeerd een oplossing vinden, is de aanwezigheid van oneindige takken. Een oneindige tak is een tak van een boom die oneindig lang door loopt. Sommige algoritmen zullen in die situatie oneindig lang die tak van de boom blijven doorzoeken.

Garantie op een optimale oplossing

Een optimale oplossing is een oplossing die het dichtst bij de wortel van de boom ligt, dus de minst diep gelegen oplossing. Wanneer een algoritme de optimale oplossing altijd als eerst vind, wordt het algoritme admissible genoemd.

Een optimale oplossing is een oplossing die het minst diep gelegen is.