Answer

1. 

   davy.ai

   July 25, 2023 at 2:47 am

   Para implementar la Búsqueda en Profundidad Iterativa en Python para el árbol dado, es necesario modificar el código actual agregando un bucle que itere sobre cada nivel del árbol, y luego llamar al algoritmo DFS para cada nivel especificando la profundidad máxima. Aquí está el código modificado que implementa IDS para el árbol proporcionado en el archivo PNG:

   paths = {
       5: [3, 7],
       7: [8],
       3: [2, 4],
       4: [8],
       8: [],
       2: []
   }
   
   
   def ids(graph, start, target):
       # comenzando con depth = 1
       depth = 1
       bottom_reached = False
   
       # repetir hasta llegar al nivel inferior
       while not bottom_reached:
           # llamar a la función recursiva IDS para la profundidad actual
           result, bottom_reached = ids_rec(graph, start, target, 0, depth)
   
           # si se encuentra un camino, devolver el resultado
           if result is not None:
               return result
   
           # duplicar la profundidad para la siguiente iteración
           depth *= 2
           print("Aumentando la profundidad a " + str(depth))
   
       # devolver None si no se encuentra el objetivo
       return None
   
   
   def ids_rec(graph, start, target, current_depth, max_depth):
       # imprimir el nodo visitado
       print(f"Visitando el nodo {start}")
   
       # si se encuentra el objetivo, devolverlo con bottom_reached = True
       if start == target:
           return start, True
   
       # si se alcanza la profundidad máxima, devolver None con bottom_reached = False
       if current_depth == max_depth:
           print("Se alcanzó la profundidad máxima")
           if not graph.get(start):
               return None, False
           else:
               return None, True
   
       # establecer bottom_reached inicialmente en True
       bottom_reached = True
   
       # iterar sobre los hijos del nodo actual
       for child in graph[start]:
           # llamar recursivamente a IDS para el hijo
           result, bottom_reached_rec = ids_rec(graph, child, target, current_depth+1, max_depth)
   
           # si se encuentra el objetivo, devolverlo con bottom_reached = True
           if result is not None:
               return result, True
   
           # actualizar bottom_reached con el resultado del hijo
           bottom_reached = bottom_reached and bottom_reached_rec
   
       # devolver None si no se encuentra el objetivo y bottom_reached es False
       return None, bottom_reached
   
   
   # llamar a la función IDS para cada nivel del árbol e imprimir el DFS para cada nivel
   for depth_level in range(1, 5):
       print(f"\nEjecutando IDS para el nivel de profundidad {depth_level}:")
       result = ids(paths, 5, 8)
       print(f"Resultado IDS para el nivel de profundidad {depth_level}: {result}")
   
       # código del algoritmo DFS
       done = False
       visited = []
   
       def dfs(graph, start, end):
           global done
           if start not in visited:
               if not done:
                   visited.append(start)
               if start == end:
                   done = True
                   return
               for i in graph[start]:
                   dfs(graph, i, end)
   
       dfs(paths, 5, result)
       print(f"Resultado DFS para el nivel de profundidad {depth_level}: {visited}")
   

   Este código implementa IDS para el árbol con niveles máximos de 1, 2, 4 y 8. Para cada nivel, llama a la función IDS e imprime el resultado, luego ejecuta el algoritmo DFS para los mismos nodos de inicio y objetivo utilizando el resultado de IDS como objetivo. Finalmente, imprime los nodos visitados por el DFS para cada nivel. Nótese que el nivel máximo del árbol es 3, por lo que no es necesario ejecutar IDS para niveles superiores a 8.

Comments are closed.