Depth-limited search

Depth-limited search (DLS) is een zoekalgoritme waarbij een depth-first search uitgevoerd wordt tot een vaste dieptegrens. Het wordt bijvoorbeeld gebruikt in de iterative deepening depth-first search, een zoekalgoritme waarbij de depth-first search iteratief wordt uitgevoerd met een steeds grotere dieptegrens totdat een oplossing is gevonden of totdat de gehele boom is doorzocht.

Het algoritme zal een knoop die zich dieper dan de dieptegrens in de graaf bevindt niet onderzoeken: het zoekalgoritme zal kinderen van knopen die zich op deze dieptegrens bevinden dus niet onderzoeken. DLS zal alleen oplossingen vinden die zich binnen deze dieptegrens bevinden. Door het toevoegen van een dieptegrens zal het algoritme altijd termineren en kan het niet, zoals depth-first search, terechtkomen in een pad met oneindige lengte of een cykel.