Un componente integral de la informática y la inteligencia artificial son los algoritmos de búsqueda. Se utilizan para resolver una variedad de problemas, desde jugar juegos como el ajedrez y las damas hasta localizar la ruta más corta en un mapa. El método Depth First Search (DFS), uno de los algoritmos de búsqueda más populares, busca en una red o árbol viajando lo más lejos posible a lo largo de cada rama antes de dar la vuelta. Sin embargo, DFS tiene un inconveniente crítico: si el gráfico contiene ciclos, podría quedar atrapado en un bucle sin fin. El uso de la búsqueda iterativa y profunda (IDS) o la búsqueda iterativa y profunda en profundidad es una técnica para resolver este problema (IDDFS).

¿Qué es el IDDS?

Un algoritmo de búsqueda conocido como IDS combina los beneficios de DFS con Breadth First Search (BFS). El gráfico se explora utilizando DFS, pero el límite de profundidad aumentó constantemente hasta que se localiza el objetivo. En otras palabras, IDS ejecuta DFS continuamente, elevando el límite de profundidad cada vez, hasta obtener el resultado deseado. La profundización iterativa es un método que garantiza que la búsqueda sea exhaustiva (es decir, descubre una solución si existe) y eficiente (es decir, encuentra el camino más corto hacia la meta).

El pseudocódigo de IDS es sencillo:

Código

 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 

¿Cómo funciona el IDS?

La función iterativeDeepeningSearch realiza una búsqueda iterativa de profundización en el gráfico utilizando un nodo raíz y un nodo objetivo como entradas hasta que se alcanza el objetivo o se agota el espacio de búsqueda. Esto se logra mediante el uso regular de la función DepthLimitedSearch, que aplica una restricción de profundidad a DFS. La búsqueda finaliza y devuelve el nodo objetivo si el objetivo se encuentra a cualquier profundidad. La búsqueda arroja Ninguno si el espacio de búsqueda está agotado (se han investigado todos los nodos hasta el límite de profundidad).

La función DepthLimitedSearch realiza DFS en el gráfico con el límite de profundidad especificado tomando como entradas un nodo, un nodo de destino y un límite de profundidad. La búsqueda devuelve ENCONTRADO si el nodo deseado se encuentra en la profundidad actual. La búsqueda devuelve NO ENCONTRADO si se alcanza el límite de profundidad pero no se puede ubicar el nodo objetivo. Si ninguno de los criterios es verdadero, la búsqueda pasa iterativamente a la descendencia del nodo.

Programa:

Código

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

Producción

 Path found 

Ventajas

• IDS es superior a otros algoritmos de búsqueda en varios aspectos. El primer beneficio es que es integral, lo que garantiza que se encontrará una solución si uno está presente en el espacio de búsqueda. Esto es para que todos los nodos bajo un límite de profundidad específico sean investigados antes de que IDS aumente el límite de profundidad, que realiza un DFS de profundidad limitada.
• IDS ahorra memoria, lo cual es su segundo beneficio. Esto se debe a que IDS disminuye las necesidades de memoria del algoritmo al no almacenar en la memoria todos los nodos del área de búsqueda. IDS minimiza la huella de memoria del algoritmo al almacenar solo los nodos hasta el límite de profundidad actual.
• La capacidad de IDS para utilizarse tanto en búsquedas de árboles como de gráficos es su tercer beneficio. Esto se debe al hecho de que IDS es un algoritmo de búsqueda genérico que funciona en cualquier espacio de búsqueda, incluidos un árbol o un gráfico.

Desventajas

• IDS tiene la desventaja de visitar ciertos nodos más de una vez, lo que podría ralentizar la búsqueda. Los beneficios de la integridad y la optimización con frecuencia superan esta desventaja. Además, al emplear estrategias como la memoria o el almacenamiento en caché, se pueden minimizar los viajes repetidos.