El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios de Algoritmos

Siguiente ►
►

En esta sección, vamos a poner en práctica los conceptos aprendidos sobre algoritmos en inteligencia artificial. Los ejercicios están diseñados para reforzar tu comprensión y habilidades en la implementación de algoritmos de búsqueda y optimización. Cada ejercicio incluye una descripción del problema, un ejemplo de código y una explicación detallada. Al final de la sección, encontrarás las soluciones y retroalimentación sobre errores comunes.

Ejercicio 1: Búsqueda en Anchura (Breadth-First Search)

Descripción del Problema

Implementa el algoritmo de Búsqueda en Anchura (BFS) para encontrar el camino más corto en un grafo no ponderado desde un nodo inicial hasta un nodo objetivo.

Ejemplo de Código

from collections import deque

def bfs(graph, start, goal):
    # Cola para mantener los nodos a explorar
    queue = deque([start])
    # Diccionario para mantener el camino recorrido
    paths = {start: [start]}
    
    while queue:
        current_node = queue.popleft()
        
        # Si encontramos el nodo objetivo, retornamos el camino
        if current_node == goal:
            return paths[current_node]
        
        for neighbor in graph[current_node]:
            if neighbor not in paths:
                queue.append(neighbor)
                paths[neighbor] = paths[current_node] + [neighbor]
    
    return None  # Si no se encuentra el camino

# Grafo de ejemplo
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Prueba del algoritmo
start_node = 'A'
goal_node = 'F'
path = bfs(graph, start_node, goal_node)
print(f"Camino más corto de {start_node} a {goal_node}: {path}")

Explicación del Código

  1. Inicialización: Utilizamos una cola (queue) para explorar los nodos y un diccionario (paths) para mantener el camino recorrido.
  2. Exploración de Nodos: Mientras la cola no esté vacía, extraemos el nodo actual y verificamos si es el nodo objetivo.
  3. Actualización de Caminos: Para cada vecino del nodo actual, si no ha sido visitado, lo añadimos a la cola y actualizamos el camino.
  4. Retorno del Camino: Si encontramos el nodo objetivo, retornamos el camino almacenado en el diccionario paths.

Ejercicio

Implementa el algoritmo BFS para el siguiente grafo y encuentra el camino más corto de 'A' a 'D':

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

Ejercicio 2: Búsqueda en Profundidad (Depth-First Search)

Descripción del Problema

Implementa el algoritmo de Búsqueda en Profundidad (DFS) para recorrer un grafo y encontrar un camino desde un nodo inicial hasta un nodo objetivo.

Ejemplo de Código

def dfs(graph, start, goal, path=None):
    if path is None:
        path = [start]
    if start == goal:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in path:
            new_path = dfs(graph, neighbor, goal, path + [neighbor])
            if new_path:
                return new_path
    
    return None

# Grafo de ejemplo
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Prueba del algoritmo
start_node = 'A'
goal_node = 'F'
path = dfs(graph, start_node, goal_node)
print(f"Camino encontrado de {start_node} a {goal_node}: {path}")

Explicación del Código

  1. Inicialización: La función dfs se llama recursivamente, manteniendo el camino actual en la lista path.
  2. Condición de Parada: Si el nodo actual es el nodo objetivo, retornamos el camino.
  3. Exploración de Vecinos: Para cada vecino del nodo actual, si no ha sido visitado, llamamos recursivamente a dfs con el vecino y el camino actualizado.
  4. Retorno del Camino: Si encontramos un camino válido, lo retornamos; de lo contrario, retornamos None.

Ejercicio

Implementa el algoritmo DFS para el siguiente grafo y encuentra un camino de 'A' a 'D':

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

Ejercicio 3: Algoritmo de Dijkstra

Descripción del Problema

Implementa el algoritmo de Dijkstra para encontrar el camino más corto en un grafo ponderado desde un nodo inicial hasta un nodo objetivo.

Ejemplo de Código

import heapq

def dijkstra(graph, start, goal):
    # Cola de prioridad para mantener los nodos a explorar
    queue = [(0, start)]
    # Diccionario para mantener las distancias mínimas
    distances = {start: 0}
    # Diccionario para mantener el camino recorrido
    paths = {start: [start]}
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_node == goal:
            return paths[current_node], current_distance
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if neighbor not in distances or distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
                paths[neighbor] = paths[current_node] + [neighbor]
    
    return None, float('inf')  # Si no se encuentra el camino

# Grafo de ejemplo
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 1},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 1, 'E': 1}
}

# Prueba del algoritmo
start_node = 'A'
goal_node = 'F'
path, distance = dijkstra(graph, start_node, goal_node)
print(f"Camino más corto de {start_node} a {goal_node}: {path} con distancia {distance}")

Explicación del Código

  1. Inicialización: Utilizamos una cola de prioridad (queue) para explorar los nodos y diccionarios (distances y paths) para mantener las distancias mínimas y el camino recorrido.
  2. Exploración de Nodos: Mientras la cola no esté vacía, extraemos el nodo con la distancia mínima.
  3. Actualización de Distancias y Caminos: Para cada vecino del nodo actual, calculamos la nueva distancia y actualizamos si es menor que la distancia conocida.
  4. Retorno del Camino: Si encontramos el nodo objetivo, retornamos el camino y la distancia; de lo contrario, retornamos None.

Ejercicio

Implementa el algoritmo de Dijkstra para el siguiente grafo y encuentra el camino más corto de 'A' a 'D':

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'D': 2},
    'C': {'A': 3, 'E': 1},
    'D': {'B': 2},
    'E': {'C': 1, 'D': 4}
}

Soluciones y Retroalimentación

Solución al Ejercicio 1

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

start_node = 'A'
goal_node = 'D'
path = bfs(graph, start_node, goal_node)
print(f"Camino más corto de {start_node} a {goal_node}: {path}")

Solución al Ejercicio 2

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

start_node = 'A'
goal_node = 'D'
path = dfs(graph, start_node, goal_node)
print(f"Camino encontrado de {start_node} a {goal_node}: {path}")

Solución al Ejercicio 3

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'D': 2},
    'C': {'A': 3, 'E': 1},
    'D': {'B': 2},
    'E': {'C': 1, 'D': 4}
}

start_node = 'A'
goal_node = 'D'
path, distance = dijkstra(graph, start_node, goal_node)
print(f"Camino más corto de {start_node} a {goal_node}: {path} con distancia {distance}")

Retroalimentación sobre Errores Comunes

  1. BFS y DFS: Asegúrate de no visitar nodos repetidos para evitar ciclos infinitos.
  2. Dijkstra: Verifica que las distancias se actualicen correctamente y que la cola de prioridad se maneje adecuadamente.

Conclusión

En esta sección, hemos practicado la implementación de algoritmos de búsqueda y optimización fundamentales en inteligencia artificial. Estos ejercicios te ayudarán a comprender mejor cómo funcionan estos algoritmos y cómo aplicarlos a problemas reales. En el siguiente módulo, profundizaremos en el aprendizaje automático y sus aplicaciones.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados