BÚSQUEDAS

BUSQUEDA EN PROFUNDIDAD
 Define una clase llamada Nodo que representa un nodo
en un árbol binario.
Método constructor (__init__):
dato: Almacena el valor del nodo.
[Link]: Referencia al hijo izquierdo del nodo,
inicializado como None.
[Link]: Referencia al hijo derecho del nodo,
inicializado como None.

Método especial (__str__): Convierte el valor del nodo a una

cadena para que sea fácil de imprimir. Es útil para imprimir
directamente el nodo.
Define una función para realizar una búsqueda en profundidad
en el árbol binario.
Caso base 1: Si el nodo raíz es None (nodo vacío), retorna False
porque no hay nada que buscar.
Caso base 2: Si el valor del nodo actual coincide con el objetivo,
imprime un mensaje indicando que el nodo fue encontrado y
retorna True.
Imprime el valor del nodo que se está visitando en el recorrido.

Llama recursivamente a la función en el subárbol izquierdo. Si

el nodo objetivo se encuentra en este subárbol, retorna True.

Llama recursivamente a la función en el subárbol derecho. Si el

nodo objetivo se encuentra en este subárbol, retorna True.
Si no se encuentra el nodo en el subárbol izquierdo ni en el
derecho, retorna False.
 Se crea el nodo raíz con el valor 'A'.
Se asignan los nodos 'B' y 'C' como hijos izquierdo y derecho del nodo raíz 'A'.

Se asignan los nodos 'D' y 'E' como hijos izquierdo y derecho del nodo 'B'.

Se asignan los nodos 'F' y 'G' como hijos izquierdo y derecho del nodo 'C'.

Solicita al usuario que ingrese el valor del nodo que desea buscar.
.strip(): Elimina espacios en blanco al inicio y al final.
.upper(): Convierte el texto a mayúsculas.

Llama a la función BusquedaEnProfundidad con la raíz del árbol y el nodo objetivo ingresado por el usuario.

Si el resultado es False (el nodo no fue encontrado), imprime un mensaje indicando que no existe en el árbol.
BÚSQUEDA EN AMPLITUD
Define una función que implementa el algoritmo de búsqueda en amplitud para un árbol binario.
Recibe:
raiz: El nodo inicial (la raíz del árbol).
objetivo: El valor que queremos encontrar.

Si la raíz del árbol es None (es decir, el árbol está vacío), no hay nada que buscar y se retorna False.

Cola: Se utiliza una lista para simular una cola. La cola almacenará los nodos pendientes de visitar.
[raiz]: Se inicializa la cola con el nodo raíz del árbol.

Se inicia un bucle que continúa mientras la cola no esté vacía (es decir, mientras haya nodos por visitar).
pop(0): Extrae y elimina el primer nodo de la cola (esto respeta el comportamiento FIFO: primero en entrar, primero en
salir).
nodo_actual: Es el nodo que se esta visitando en este momento.
 Muestra el valor del nodo que se está visitando actualmente.

Compara el valor del nodo actual (nodo_actual.dato) con el objetivo.

Si coinciden:
Imprime un mensaje indicando que el nodo fue encontrado.
Retorna True para detener la búsqueda.

Si el nodo actual tiene un hijo izquierdo (nodo_actual.izquierdo no es None), se agrega este hijo a la cola para que
sea visitado después.

Si el nodo actual tiene un hijo derecho (nodo_actual.derecho no es None), también se agrega a la cola.
Si la cola se vacía y no se encontró el nodo objetivo, retorna False.
BUSQUEDA EN PROFUNDIDAD LIMITADA
class Nodo:
def __init__(self, dato):
[Link] = None
[Link] = None
[Link] = dato

def __str__(self):
return str([Link])
def BusquedaEnProfundidadLimitada(raiz, objetivo, limite):

Se define una función para realizar una búsqueda en profundidad limitada.

Recibe:
raiz: El nodo inicial del árbol (la raíz).
objetivo: El valor del nodo que se desea encontrar.
limite: El nivel máximo de profundidad permitido en la búsqueda.
if raiz is None:
return False

Si el nodo actual es None, no hay nada que buscar y retorna False. Esto ocurre cuando se alcanza una hoja (nodo sin hijos).
if limite < 0:
return False

Si el límite de profundidad es menor que 0, la búsqueda se detiene en esa rama y retorna False.
print(f"Visitando nodo: {[Link]}, Profundidad restante: {limite}")

Muestra el valor del nodo actual y la profundidad restante para el seguimiento del recorrido.
if [Link] == objetivo: # Nodo objetivo encontrado
print(f"Nodo {objetivo} encontrado!")
return True
Compara el valor del nodo actual con el valor del objetivo.
Si coinciden:
Imprime un mensaje indicando que el nodo fue encontrado.
Retorna True para detener la búsqueda.

# Buscar en el subárbol izquierdo con límite reducido

if BusquedaEnProfundidadLimitada([Link], objetivo, limite - 1):
return True
Llama a la función recursivamente para buscar en el hijo izquierdo del nodo actual.
Reduce el límite de profundidad en 1 (limite - 1), debido a que se ha descendido un nivel en el árbol.
Si se encuentra el nodo objetivo en esta rama, retorna True.

# Buscar en el subárbol derecho con límite reducido

if BusquedaEnProfundidadLimitada([Link], objetivo, limite - 1):
return True

Similar al caso anterior, pero busca en el hijo derecho del nodo actual.
 return False # Si no se encontró en este nivel ni en los descendientes
Si el nodo objetivo no se encuentra en el subárbol izquierdo ni en el derecho dentro del límite de profundidad, retorna False.

# Crear el árbol
raiz = Nodo('A')
[Link] = Nodo('B')
[Link] = Nodo('C')
[Link] = Nodo('D')
[Link] = Nodo('E')
[Link] = Nodo('F')
[Link] = Nodo('G')

# Solicitar el nodo objetivo y el límite de profundidad al usuario

nodo_objetivo = input("Ingrese el nodo que desea buscar (A-G): ").strip().upper()
limite = int(input("Ingrese el límite de profundidad (0 para la raíz): ").strip())

Solicita al usuario que ingrese el valor del nodo que desea buscar.
Solicita al usuario que ingrese el límite de profundidad de la búsqueda. Convierte la entrada en un entero (int).
.strip(): Elimina los espacios en blanco al inicio y al final de la entrada.
.upper(): Convierte la entrada a mayúsculas para evitar errores con las letras minúsculas.
 # Realizar la búsqueda en profundidad limitada
resultado = BusquedaEnProfundidadLimitada(raiz, nodo_objetivo, limite)

Llama a la función BusquedaEnProfundidadLimitada con la raíz del árbol, el nodo objetivo y el límite de profundidad
especificado.
if not resultado:
print(f"Nodo {nodo_objetivo} no encontrado dentro del límite de profundidad
{limite}.")
Si la función retorna False, significa que el nodo objetivo no se encontró dentro del límite de profundidad.
Imprime un mensaje indicando que el nodo no fue encontrado.

Ingrese el nodo que desea buscar (A-G): e

Ingrese el límite de profundidad (0 para la
raíz): 2 Visitando nodo: A, Profundidad
restante: 2 Visitando nodo: B, Profundidad
restante: 1 Visitando nodo: D, Profundidad
restante: 0 Visitando nodo: E, Profundidad
restante: 0 Nodo E encontrado!
PRIMERO EL MEJOR
 import heapq
heapq: Es un módulo de Python que proporciona una implementación de colas de prioridad (heaps pilas). Se utiliza para
manejar la cola de prioridad en la búsqueda primero el mejor.
# Definimos una función heurística (distancia euclidiana entre dos nodos)
def heuristica(nodo, objetivo):
distancia = ((nodo[0] - objetivo[0])**2 + (nodo[1] - objetivo[1])**2)**0.5
print(f"\n Distancia euclidiana desde {nodo} hasta {objetivo}:
{distancia:.2f}")
return distancia

heuristica(nodo, objetivo): Esta función calcula la distancia euclidiana entre dos nodos (coordenadas (x, y)).

nodo[0] y nodo[1] son las coordenadas x e y del nodo actual.

objetivo[0] y objetivo[1] son las coordenadas x e y del nodo objetivo.

La distancia euclidiana se calcula como la raíz cuadrada de la suma de los cuadrados de las diferencias en las coordenadas
x e y.
La función también imprime la distancia calculada con dos decimales.
# Implementación de la búsqueda primero el mejor
def busqueda_primero_el_mejor(grafo, inicio, objetivo):
cola_prioridad = [] # Usamos una cola de prioridad (heap)
[Link](cola_prioridad, (heuristica(inicio, objetivo), inicio)) #
(heurística, nodo)
visitados = set() # Conjunto de nodos visitados
ruta = {} # Diccionario para reconstruir la ruta
ruta[inicio] = None

busqueda_primero_el_mejor(grafo, inicio, objetivo): Esta función implementa el algoritmo de búsqueda primero el

mejor.
cola_prioridad: Es una lista que funciona como una cola de prioridad (heap) donde se almacenan los nodos a explorar,
ordenados por su valor heurístico.
[Link](cola_prioridad, (heuristica(inicio, objetivo), inicio)): Se inserta el nodo inicial en la cola de prioridad
junto con su valor heurístico.
visitados: Es un conjunto que almacena los nodos que ya han sido visitados.
ruta: Es un diccionario que se utiliza para reconstruir la ruta desde el nodo inicial hasta el nodo objetivo. Almacena la
conexión entre cada nodo y su predecesor.
heappush es una función del módulo heapq en Python que permite insertar un elemento en una cola de prioridad (heap
mínimo) manteniendo el orden adecuado. Se usa principalmente en algoritmos de búsqueda, planificación y estructuras
de datos eficientes.
Python reorganiza la lista internamente para que siempre el menor elemento esté al inicio
while cola_prioridad:
_, nodo_actual = [Link](cola_prioridad) # Extraemos el nodo con menor
heurística
print(f"Visitando nodo: {nodo_actual}")
if nodo_actual == objetivo: # Si encontramos el objetivo, reconstruimos la
ruta
print(f"Nodo {objetivo} encontrado!")
camino = []
while nodo_actual is not None:
[Link](nodo_actual)
nodo_actual = ruta[nodo_actual]
return camino[::-1] # Devolvemos la ruta en orden correcto

while cola_prioridad: El bucle continúa mientras haya nodos en la cola de prioridad.

_, nodo_actual = [Link](cola_prioridad): Se extrae el nodo con el menor valor heurístico (distancia) de la cola de
prioridad.
print(f"Visitando nodo: {nodo_actual}"): Se imprime el nodo que se está visitando.
if nodo_actual == objetivo: Si el nodo actual es el objetivo, se reconstruye la ruta.
camino = []: Se inicializa una lista para almacenar la ruta.
while nodo_actual is not None: Se recorre el diccionario ruta desde el nodo objetivo hasta el nodo inicial.
[Link](nodo_actual): Se añade cada nodo a la lista camino.
return camino[::-1]: Se devuelve la ruta en orden correcto (desde el inicio hasta el objetivo).
[::-1] indica que se quiere recorrer la lista de atrás hacia adelante, invirtiéndola.
-1 es el paso negativo, lo que significa que se recorre la lista en orden inverso.
[Link](nodo_actual)

for vecino in grafo[nodo_actual]: # Exploramos los vecinos del nodo actual

if vecino not in visitados:
distancia = heuristica(vecino, objetivo) # Calculamos la distancia
[Link](cola_prioridad, (distancia, vecino))
ruta[vecino] = nodo_actual # Guardamos la ruta

return None # Si no se encuentra una ruta

[Link](nodo_actual): Se añade el nodo actual al conjunto de nodos visitados.

for vecino in grafo[nodo_actual]: Se exploran los vecinos del nodo actual.

if vecino not in visitados: Si el vecino no ha sido visitado, se calcula su heurística y se añade a la cola de prioridad.

distancia = heuristica(vecino, objetivo): Se calcula su distancia heurística al objetivo

[Link](cola_prioridad, (distancia, vecino)): Se añade el vecino a la cola de prioridad con su valor heurístico.
ruta[vecino] = nodo_actual: Se guarda la ruta desde el vecino hasta el nodo actual.
return None: Si no se encuentra una ruta al objetivo, se devuelve None.
grafo: Es un diccionario que representa un grafo donde las claves son nodos (coordenadas (x, y)) y los valores son listas
de nodos vecinos.
# Solicitar al usuario el nodo objetivo
try:
x_objetivo, y_objetivo = map(int, input("Ingrese las coordenadas del nodo objetivo
(x y): ").split())
objetivo = (x_objetivo, y_objetivo)

if objetivo not in grafo:

print(f"El nodo {objetivo} no existe en el grafo.")
else:
# Nodo inicial fijo
inicio = (0, 0)

# Ejecutamos la búsqueda
ruta = busqueda_primero_el_mejor(grafo, inicio, objetivo)

# Mostramos el resultado
if ruta:
print("Ruta encontrada:", ruta)
else:
print("No se encontró una ruta.")
except ValueError:
print("Error: Ingrese coordenadas válidas en formato 'x y' (por ejemplo: 2 2).")
try: Se intenta obtener las coordenadas del nodo objetivo del usuario.

x_objetivo, y_objetivo = map(int, input("Ingrese las coordenadas del nodo objetivo (x y): ").split()): Se solicitan las
coordenadas x e y del nodo objetivo.

objetivo = (x_objetivo, y_objetivo): Se crea una tupla con las coordenadas del objetivo.

if objetivo not in grafo: Si el nodo objetivo no existe en el grafo, se imprime un mensaje de error.
print(f"El nodo {objetivo} no existe en el grafo.")
inicio = (0, 0): Se define el nodo inicial como (0, 0).

ruta = busqueda_primero_el_mejor(grafo, inicio, objetivo): Se ejecuta la búsqueda primero el mejor.

if ruta: Si se encuentra una ruta, se imprime; de lo contrario, se indica que no se encontró una ruta.
print("Ruta encontrada:", ruta)
else:
print("No se encontró una ruta.")

except ValueError: Si el usuario ingresa coordenadas inválidas, se imprime un mensaje de error.

print("Error: Ingrese coordenadas válidas en formato 'x y' (por ejemplo: 2 2).")
La función map() en Python se utiliza para aplicar una función a cada elemento de un iterable (como una lista o una
tupla) y devolver un objeto iterable con los resultados.

La función .split() en Python se utiliza para dividir una cadena de texto en una lista de palabras o elementos usando un
separador específico.