Un component integral de la informàtica i la intel·ligència artificial són els algorismes de cerca. S'utilitzen per resoldre una varietat de problemes, des de jugar a jocs com els escacs i les dames fins a localitzar la ruta més curta en un mapa. El mètode Depth First Search (DFS), un dels algorismes de cerca més populars, cerca una xarxa o un arbre viatjant el més lluny possible per cada branca abans de girar-se. Tanmateix, DFS té un inconvenient crític: si el gràfic conté cicles, podria quedar atrapat en un bucle sense fi. L'ús de la cerca iterativa d'aprofundiment (IDS) o la primera cerca iterativa de profunditat d'aprofundiment és una tècnica per resoldre aquest problema (IDDFS).

Què és l'IDS?

Un algorisme de cerca conegut com IDS combina els avantatges de DFS amb Breadth First Search (BFS). El gràfic s'explora mitjançant DFS, però el límit de profunditat va augmentar constantment fins a localitzar l'objectiu. En altres paraules, IDS executa contínuament DFS, augmentant el límit de profunditat cada vegada, fins que s'obté el resultat desitjat. L'aprofundiment iteratiu és un mètode que assegura que la cerca és exhaustiva (és a dir, descobreix una solució si n'hi ha) i eficient (és a dir, troba el camí més curt cap a l'objectiu).

El pseudocodi per a IDS és senzill:

Codi

 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 

Com funciona l'IDS?

La funció iterativeDeepeningSearch realitza una cerca iterativa d'aprofundiment al gràfic utilitzant un node arrel i un node objectiu com a entrades fins que s'aconsegueix l'objectiu o s'esgota l'espai de cerca. Això s'aconsegueix utilitzant regularment la funció depthLimitedSearch, que aplica una restricció de profunditat a DFS. La cerca acaba i retorna el node de l'objectiu si l'objectiu es troba a qualsevol profunditat. La cerca dóna Cap si l'espai de cerca s'ha esgotat (s'han investigat tots els nodes fins al límit de profunditat).

La funció depthLimitedSearch realitza DFS al gràfic amb el límit de profunditat especificat prenent com a entrades un node, un node de destinació i un límit de profunditat. La cerca retorna TROBAT si el node desitjat es troba a la profunditat actual. La cerca torna NO TROBAT si s'arriba al límit de profunditat però no es pot localitzar el node objectiu. Si cap dels criteris és cert, la cerca passa iterativament a la descendència del node.

Programa:

Codi

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

Sortida

 Path found 

Avantatges

• IDS és superior a altres algorismes de cerca de diverses maneres. El primer avantatge és que és complet, cosa que garanteix que es trobarà una solució si hi ha algú a l'espai de cerca. Això és perquè tots els nodes sota un límit de profunditat específic s'investiguin abans que IDS augmenti el límit de profunditat, que fa un DFS amb profunditat limitada.
• IDS és eficient en memòria, que és el seu segon avantatge. Això es deu al fet que l'IDS disminueix les necessitats de memòria de l'algoritme al no emmagatzemar tots els nodes de l'àrea de cerca a la memòria. L'IDS minimitza la petjada de memòria de l'algorisme només emmagatzemant els nodes fins al límit de profunditat actual.
• La capacitat d'IDS d'utilitzar-se tant per a la cerca d'arbres com de gràfics és el seu tercer avantatge. Això es deu al fet que IDS és un algorisme de cerca genèric que funciona en qualsevol espai de cerca, inclòs un arbre o un gràfic.

Desavantatges

• L'IDS té l'inconvenient de visitar certs nodes més d'una vegada, cosa que podria alentir la cerca. Els avantatges de l'exhaustivitat i l'optimitat sovint superen aquest inconvenient. A més, mitjançant l'ús d'estratègies com la memòria o la memòria cau, es poden minimitzar els viatges repetits.