Tipo de Búsqueda No Informada -Python
Cada uno de estos algoritmos puede ser útil en diferentes contextos y para diferentes
tipos de problemas de búsqueda en grafos.
1.Búsqueda en Anchura (BFS): Explora todos los nodos al nivel actual antes de pasar al
siguiente nivel. Es útil para encontrar el camino más corto en términos de aristas.
from collections import deque
def bfs(graph, start, goal):
queue = deque([start]) # Inicializa una cola con el nodo inicial
visited = {start: None} # Diccionario para rastrear nodos visitados y sus predecesores
while queue: # Mientras la cola no esté vacía
node = [Link]() # Extrae el primer nodo de la cola
if node == goal: # Si el nodo es el objetivo, termina la búsqueda
break
for neighbor in graph[node]: # Itera sobre los vecinos del nodo actual
if neighbor not in visited: # Si el vecino no ha sido visitado
[Link](neighbor) # Añade el vecino a la cola
visited[neighbor] = node # Marca el vecino como visitado y guarda su predecesor
path = [] # Lista para almacenar el camino encontrado
while node is not None: # Reconstruye el camino desde el objetivo hasta el inicio
[Link](node) # Añade el nodo al camino
node = visited[node] # Mueve al predecesor del nodo actual
return path[::-1] # Devuelve el camino invertido, desde el inicio hasta el objetivo
# Ejemplo de uso
graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B'],
'D': ['A', 'E'],
'E': ['B', 'D']
print("BFS:", bfs(graph, 'A', 'C'))
2.Búsqueda en Profundidad (DFS): Explora lo más profundo posible antes de retroceder.
Puede quedar atrapada en bucles en grafos con ciclos.
def dfs(graph, start, goal):
stack = [start] # Inicializa una pila con el nodo inicial
visited = {start: None} # Diccionario para rastrear nodos visitados y sus predecesores
while stack: # Mientras la pila no esté vacía
node = [Link]() # Extrae el último nodo de la pila
if node == goal: # Si el nodo es el objetivo, termina la búsqueda
break
for neighbor in graph[node]: # Itera sobre los vecinos del nodo actual
if neighbor not in visited: # Si el vecino no ha sido visitado
[Link](neighbor) # Añade el vecino a la pila
visited[neighbor] = node # Marca el vecino como visitado y guarda su predecesor
path = [] # Lista para almacenar el camino encontrado
while node is not None: # Reconstruye el camino desde el objetivo hasta el inicio
[Link](node) # Añade el nodo al camino
node = visited[node] # Mueve al predecesor del nodo actual
return path[::-1] # Devuelve el camino invertido, desde el inicio hasta el objetivo
# Ejemplo de uso
print("DFS:", dfs(graph, 'A', 'C'))
3.Búsqueda de Costo Uniforme (UCS): Similar a BFS pero tiene en cuenta el costo de las
aristas, siempre eligiendo la ruta de menor costo total hasta el momento.
import heapq # librería conocido como algoritmo de cola con prioridad
def ucs(graph, start, goal):
queue = [(0, start)] # Inicializa una cola de prioridad con el costo inicial 0 y el nodo
inicial
visited = {start: None} # Diccionario para rastrear nodos visitados y sus predecesores
costs = {start: 0} # Diccionario para rastrear los costos mínimos desde el nodo inicial
while queue: # Mientras la cola de prioridad no esté vacía
cost, node = [Link](queue) # Extrae el nodo con el menor costo de la cola de
prioridad
if node == goal: # Si el nodo es el objetivo, termina la búsqueda
break
for neighbor, weight in graph[node].items(): # Itera sobre los vecinos del nodo actual
y sus costos
new_cost = cost + weight # Calcula el nuevo costo desde el nodo inicial hasta el
vecino
if neighbor not in costs or new_cost < costs[neighbor]: # Si es un costo menor al
ya registrado
costs[neighbor] = new_cost # Actualiza el costo mínimo
[Link](queue, (new_cost, neighbor)) # Añade el vecino a la cola de
prioridad
visited[neighbor] = node # Marca el vecino como visitado y guarda su predecesor
path = [] # Lista para almacenar el camino encontrado
while node is not None: # Reconstruye el camino desde el objetivo hasta el inicio
[Link](node) # Añade el nodo al camino
node = visited[node] # Mueve al predecesor del nodo actual
return path[::-1] # Devuelve el camino invertido, desde el inicio hasta el objetivo
# Ejemplo de uso
graph_ucs = {
'A': {'B': 1, 'D': 3},
'B': {'A': 1, 'C': 1, 'E': 5},
'C': {'B': 1},
'D': {'A': 3, 'E': 1},
'E': {'B': 5, 'D': 1}
print("UCS:", ucs(graph_ucs, 'A', 'C'))
4.Búsqueda en Profundidad Limitada (DLS): Variante de DFS que limita la profundidad
máxima para evitar ciclos y búsqueda infinita.
def dls(graph, start, goal, limit):
def recursive_dls(node, goal, limit, visited):
if node == goal: # Si el nodo es el objetivo, termina la búsqueda
return [node]
if limit <= 0: # Si se alcanza el límite de profundidad, termina la búsqueda
return None
[Link](node) # Marca el nodo como visitado
for neighbor in graph[node]: # Itera sobre los vecinos del nodo actual
if neighbor not in visited: # Si el vecino no ha sido visitado
path = recursive_dls(neighbor, goal, limit - 1, visited) # Realiza una búsqueda
recursiva
if path: # Si se encuentra un camino al objetivo, devuelve el camino
return [node] + path
[Link](node) # Elimina el nodo de los visitados si no se encuentra un camino al
objetivo
return None
return recursive_dls(start, goal, limit, set())
# Ejemplo de uso
print("DLS:", dls(graph, 'A', 'C', 2))
5.Búsqueda en Profundidad Iterativa (IDS): Combina las ventajas de BFS y DFS,
ejecutando DLS con profundidades crecientes hasta encontrar el objetivo.
def ids(graph, start, goal, max_depth):
for depth in range(max_depth): # Itera desde la profundidad 0 hasta la máxima profundidad
permitida
path = dls(graph, start, goal, depth) # Realiza una búsqueda en profundidad limitada
if path: # Si se encuentra un camino, lo devuelve
return path
return None # Si no se encuentra un camino dentro de la profundidad máxima, devuelve None
