Implementación en Python del Algoritmo de Búsqueda por Profundización Iterativa.
Estoy tratando de implementar la Búsqueda en Profundidad Iterativa con python, pero tengo un problema con la configuración del nivel de profundidad. Aquí está el Árbol que estoy tratando de implementar y aquí está el código. He incluido el código del algoritmo DFS ya que “Visited” es la respuesta del último nivel en el IDS. Quiero que el código imprima el DFS de cada nivel del Árbol mencionado en la imagen.
paths = {
5: [3, 7],
7: [8],
3: [2, 4],
4: [8],
8: [],
2: []
}
def ids(graph, start, target):
depth = 1
bottom_reached = False
while not bottom_reached:
result, bottom_reached = ids_rec(graph, start, target, 0, depth)
if result is not None:
return result
depth *= 2
print("Aumentando la profundidad a " + str(depth))
return None
def ids_rec(graph, start2, target, current_depth, max_depth):
print(f"Visitando nodo {start2}")
if start2 == target:
return start2, True
if current_depth == max_depth:
print("Se alcanzó la profundidad máxima")
if not graph.get(start2):
return None, False
else:
return None, True
bottom_reached = True
for i in graph[start2]:
result, bottom_reached_rec = ids_rec(graph, i, target, current_depth+1, max_depth)
if result is not None:
return result, True
bottom_reached = bottom_reached and bottom_reached_rec
return None, bottom_reached
ids(paths, 5, 8)
Código de Búsqueda en Profundidad (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, 8)
print(visited)
davy.ai
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:
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.