Una componente integrale dell'informatica e dell'intelligenza artificiale sono gli algoritmi di ricerca. Vengono utilizzati per risolvere una serie di problemi, dal gioco a scacchi e dama all'individuazione del percorso più breve su una mappa. Il metodo Depth First Search (DFS), uno degli algoritmi di ricerca più diffusi, ricerca una rete o un albero viaggiando il più lontano possibile lungo ciascun ramo prima di voltarsi. Tuttavia, DFS presenta uno svantaggio critico: se il grafico contiene cicli, potrebbe rimanere intrappolato in un ciclo infinito. L'utilizzo della ricerca iterativa di approfondimento (IDS) o della ricerca iterativa di approfondimento approfondito è una tecnica per risolvere questo problema (IDDFS).

Cos'è l'IDS?

Un algoritmo di ricerca noto come IDS combina i vantaggi di DFS con Breadth First Search (BFS). Il grafico viene esplorato utilizzando DFS, ma il limite di profondità aumenta costantemente fino all'individuazione del bersaglio. In altre parole, IDS esegue continuamente DFS, aumentando ogni volta il limite di profondità, fino a ottenere il risultato desiderato. L'approfondimento iterativo è un metodo che garantisce che la ricerca sia approfondita (ovvero, scopra una soluzione se ne esiste una) ed efficiente (ovvero, trovi il percorso più breve verso l'obiettivo).

Lo pseudocodice per IDS è semplice:

Codice

 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 

Come funziona l'IDS?

La funzione iterativeDeepeningSearch esegue una ricerca approfondita iterativa sul grafico utilizzando un nodo radice e un nodo obiettivo come input fino al raggiungimento dell'obiettivo o all'esaurimento dello spazio di ricerca. Ciò si ottiene utilizzando regolarmente la funzione DepthLimitedSearch, che applica una restrizione di profondità a DFS. La ricerca termina e restituisce il nodo obiettivo se l'obiettivo si trova a qualsiasi profondità. La ricerca restituisce Nessuno se lo spazio di ricerca è esaurito (sono stati esaminati tutti i nodi fino al limite di profondità).

La funzione DepthLimitedSearch conduce DFS sul grafico con il limite di profondità specificato prendendo come input un nodo, un nodo di destinazione e un limite di profondità. La ricerca restituisce TROVATO se il nodo desiderato si trova alla profondità attuale. La ricerca restituisce NON TROVATO se viene raggiunto il limite di profondità ma non è possibile localizzare il nodo obiettivo. Se nessuno dei due criteri è vero, la ricerca passa iterativamente al figlio del nodo.

Programma:

Codice

 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') 

Produzione

 Path found 

Vantaggi

• IDS è superiore ad altri algoritmi di ricerca in molti modi. Il primo vantaggio è che è completo, il che garantisce che una soluzione venga trovata se presente nello spazio di ricerca. In questo modo tutti i nodi al di sotto di un limite di profondità specifico vengono esaminati prima che il limite di profondità venga aumentato da IDS, che esegue un DFS con profondità limitata.
• IDS è efficiente in termini di memoria, che è il suo secondo vantaggio. Questo perché IDS diminuisce il fabbisogno di memoria dell'algoritmo non memorizzando in memoria tutti i nodi nell'area di ricerca. IDS riduce al minimo l'impronta di memoria dell'algoritmo archiviando i nodi solo fino al limite di profondità corrente.
• Il terzo vantaggio è la capacità di IDS di essere utilizzato sia per la ricerca ad albero che per quella su grafico. Ciò è dovuto al fatto che IDS è un algoritmo di ricerca generico che funziona su qualsiasi spazio di ricerca, incluso un albero o un grafico.

Svantaggi

• IDS ha lo svantaggio di visitare potenzialmente determinati nodi più di una volta, il che potrebbe rallentare la ricerca. I vantaggi della completezza e dell’ottimalità spesso superano questo svantaggio. Inoltre, impiegando strategie come la memoria o il caching, è possibile ridurre al minimo i viaggi ripetuti.