Een integraal onderdeel van de informatica en kunstmatige intelligentie zijn zoekalgoritmen. Ze worden gebruikt om allerlei problemen op te lossen, van het spelen van spellen zoals schaken en dammen tot het lokaliseren van de kortste route op een kaart. De Depth First Search (DFS)-methode, een van de populairste zoekalgoritmen, doorzoekt een netwerk of boom door zo ver mogelijk langs elke tak te reizen voordat hij zich omdraait. DFS heeft echter een cruciaal nadeel: als de grafiek cycli bevat, kan deze in een eindeloze lus terechtkomen. Het gebruik van Iterative Deepening Search (IDS) of Iterative Deepening Depth First Search is een techniek om dit probleem op te lossen (IDDFS).

Wat is IDS?

Een zoekalgoritme dat bekend staat als IDS combineert de voordelen van DFS met Breadth First Search (BFS). De grafiek wordt onderzocht met behulp van DFS, maar de dieptelimiet neemt gestaag toe totdat het doel is gelokaliseerd. Met andere woorden, IDS voert DFS voortdurend uit, waarbij de dieptelimiet elke keer wordt verhoogd, totdat het gewenste resultaat is bereikt. Iteratieve verdieping is een methode die ervoor zorgt dat de zoektocht grondig is (dat wil zeggen dat er een oplossing wordt ontdekt als die bestaat) en efficiënt (dat wil zeggen dat er de kortste weg naar het doel wordt gevonden).

De pseudocode voor IDS is eenvoudig:

Code

 function iterativeDeepeningSearch(root, goal): depth = 0 while True: result = depthLimitedSearch(root, goal, depth) if result == FOUND: return goal if result == NOT_FOUND: return None depth = depth + 1 function depthLimitedSearch(node, goal, depth): if node == goal: return FOUND if depth == 0: return NOT_FOUND for child in node.children: result = depthLimitedSearch(child, goal, depth - 1) if result == FOUND: return FOUND return NOT_FOUND 

Hoe werkt IDS?

De iterativeDeepeningSearch-functie voert iteratieve verdiepingszoekopdrachten uit op de grafiek met behulp van een hoofdknooppunt en een doelknooppunt als invoer totdat het doel is bereikt of de zoekruimte is opgebruikt. Dit wordt bereikt door regelmatig gebruik te maken van de depthLimitedSearch-functie, die een dieptebeperking op DFS toepast. De zoekopdracht eindigt en retourneert het doelknooppunt als het doel zich op welke diepte dan ook bevindt. De zoekopdracht levert Geen op als de zoekruimte is opgebruikt (alle knooppunten tot aan de dieptelimiet zijn onderzocht).

De functie depthLimitedSearch voert DFS uit op de grafiek met de opgegeven dieptelimiet door als invoer een knooppunt, een bestemmingsknooppunt en een dieptelimiet te nemen. De zoekopdracht retourneert GEVONDEN als het gewenste knooppunt zich op de huidige diepte bevindt. De zoekopdracht retourneert NOT FOUND als de dieptelimiet is bereikt, maar het doelknooppunt niet kan worden gelokaliseerd. Als geen van beide criteria waar is, gaat de zoekopdracht iteratief verder naar de nakomelingen van het knooppunt.

Programma:

Code

 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) def iddfs(self, start, goal, max_depth): for depth in range(max_depth+1): visited = set() if self.dls(start, goal, depth, visited): return True return False def dls(self, node, goal, depth, visited): if node == goal: return True if depth == 0: return False visited.add(node) for neighbor in self.graph[node]: if neighbor not in visited: if self.dls(neighbor, goal, depth-1, visited): return True return False # Example usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) start = 0 goal = 3 max_depth = 3 if g.iddfs(start, goal, max_depth): print('Path found') else: print('Path not found') 

Uitvoer

 Path found 

Voordelen

• IDS is in een aantal opzichten superieur aan andere zoekalgoritmen. Het eerste voordeel is dat het alomvattend is, wat ervoor zorgt dat er een oplossing wordt gevonden als die zich in de zoekruimte bevindt. Dit is zodat alle knooppunten onder een specifieke dieptelimiet worden onderzocht voordat de dieptelimiet wordt verhoogd door IDS, die een dieptebeperkte DFS uitvoert.
• IDS is geheugenefficiënt, wat het tweede voordeel is. Dit komt omdat IDS de geheugenbehoeften van het algoritme vermindert door niet elk knooppunt in het zoekgebied in het geheugen op te slaan. IDS minimaliseert de geheugenvoetafdruk van het algoritme door de knooppunten alleen op te slaan tot aan de huidige dieptelimiet.
• Het derde voordeel is dat IDS gebruikt kan worden voor het zoeken in zowel boom- als grafiekvormen. Dit komt door het feit dat IDS een generiek zoekalgoritme is dat op elke zoekruimte werkt, inclusief een boom of een grafiek.

Nadelen

• IDS heeft het nadeel dat het mogelijk bepaalde knooppunten meer dan één keer bezoekt, wat de zoektocht zou kunnen vertragen. De voordelen van volledigheid en optimaliteit overstijgen vaak dit nadeel. Door strategieën als geheugen of caching te gebruiken, kunnen bovendien de herhaalde trips worden geminimaliseerd.