Iterative deepening depth-first search

Iterative deepening depth-first search (IDDFS) is een zoekalgoritme waarbij de depth-limited search iteratief wordt uitgevoerd met telkens een grotere dieptegrens totdat een oplossing is gevonden of totdat de gehele boom is doorzocht. Bij elke iteratie worden de knopen in de graaf bezocht met depth-first search tot een bepaalde dieptegrens. De volgorde waarin de knopen voor het eerst bezocht worden, is hetzelfde als bij een breadth-first search.

IDDFS combineert het efficiënte geheugengebruik van depth-first search met de volledigheid van breadth-first search (mits de vertakkingsfactor eindig is). Aangezien IDDFS bepaalde knopen meerdere malen bezoekt, kan het lijken alsof het algoritme veel dubbel werk doet. Dit blijkt mee te vallen, doordat de meeste knopen in de onderste laag van de boom zitten, waardoor de extra rekentijd voor de knopen boven in de boom relatief meevalt.

Voorbeeld

Voor de bovenstaande graaf zullen we met de depth-first search beginnen bij A, hierbij ervan uitgaande dat linker knopen eerst gekozen worden boven rechter knopen, en daarna zullen we de knopen in de volgende volgorde overlopen: A, B, D, F, E, C, G.

Als we dit zoeken doen zonder dat we voldoende geheugen hebben om voorgaande knopen te onthouden, zullen we de knopen in de volgende volgorde doorzoeken: A, B, D, F, E, A, B, D, F, E enz. We zullen de A-B-D-F-E-lus herhalen en nooit C of G bereiken.

Iteratief verdiepen voorkomt dit oneindig herhalen en zal de volgende knopen pas behalen op een bepaalde diepte. Als we veronderstellen dat het zoeken van links naar rechts verloopt:

• 0: A
• 1: A (opnieuw), B, C, E

  Merk op dat iteratief verdiepen nu C heeft geselecteerd, terwijl we die met een conventionele depth-first search niet zullen tegenkomen

• 2: A, B, D, F, C, G, E, F
• 3: A, B, D, F, E, C, G, E, F, B

Als we voor deze graaf diepte vergroten zal voor de lussen ABFE en AEFB het algoritme uiteindelijk de maximale diepte bereiken en verder zoeken op een andere tak.