El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Exercicis d'Algoritmes

Següent ►
►

En aquest tema, ens centrarem en la pràctica dels conceptes apresos sobre algoritmes en IA. Els exercicis estan dissenyats per reforçar els coneixements teòrics i proporcionar experiència pràctica en la implementació d'algoritmes. Cada exercici inclou una explicació detallada, un exemple pràctic i una solució.

Objectius d'Aprenentatge

  • Comprendre i implementar diferents tipus d'algoritmes de cerca i optimització.
  • Aplicar algoritmes a problemes reals.
  • Avaluar l'eficiència dels algoritmes.

Exercici 1: Algoritme de Cerca en Amplitud (BFS)

Descripció

Implementa l'algoritme de Cerca en Amplitud (Breadth-First Search, BFS) per trobar el camí més curt en un graf no ponderat.

Pas a Pas

  1. Inicialització: Comença des del node inicial i afegeix-lo a una cua.
  2. Exploració: Extreu el primer node de la cua i explora els seus veïns.
  3. Visitació: Marca els veïns no visitats i afegeix-los a la cua.
  4. Repetició: Repeteix els passos 2 i 3 fins que trobis el node objectiu o la cua estigui buida.

Exemple de Codi

from collections import deque

def bfs(graph, start, goal):
    # Inicialització
    queue = deque([start])
    visited = set()
    visited.add(start)
    
    while queue:
        # Exploració
        node = queue.popleft()
        
        # Si hem arribat al node objectiu
        if node == goal:
            return True
        
        # Visitació
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return False

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

# Crida a la funció
print(bfs(graph, 'A', 'F'))  # Output: True

Explicació del Codi

  • Inicialització: Utilitzem una cua (deque) per mantenir els nodes a explorar i un conjunt (set) per marcar els nodes visitats.
  • Exploració: Extreiem el primer node de la cua i comprovem si és el node objectiu.
  • Visitació: Afegim els veïns no visitats a la cua i els marquem com a visitats.

Exercici Pràctic

Implementa l'algoritme BFS per trobar el camí més curt en un graf més complex. Prova amb diferents nodes inicials i objectius.

Exercici 2: Algoritme de Cerca en Profunditat (DFS)

Descripció

Implementa l'algoritme de Cerca en Profunditat (Depth-First Search, DFS) per explorar tots els nodes d'un graf.

Pas a Pas

  1. Inicialització: Comença des del node inicial i afegeix-lo a una pila.
  2. Exploració: Extreu el node superior de la pila i explora els seus veïns.
  3. Visitació: Marca els veïns no visitats i afegeix-los a la pila.
  4. Repetició: Repeteix els passos 2 i 3 fins que la pila estigui buida.

Exemple de Codi

def dfs(graph, start, goal):
    # Inicialització
    stack = [start]
    visited = set()
    
    while stack:
        # Exploració
        node = stack.pop()
        
        if node not in visited:
            # Visitació
            visited.add(node)
            
            # Si hem arribat al node objectiu
            if node == goal:
                return True
            
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return False

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

# Crida a la funció
print(dfs(graph, 'A', 'F'))  # Output: True

Explicació del Codi

  • Inicialització: Utilitzem una pila (stack) per mantenir els nodes a explorar i un conjunt (set) per marcar els nodes visitats.
  • Exploració: Extreiem el node superior de la pila i comprovem si és el node objectiu.
  • Visitació: Afegim els veïns no visitats a la pila i els marquem com a visitats.

Exercici Pràctic

Implementa l'algoritme DFS per explorar un graf més complex. Prova amb diferents nodes inicials i objectius.

Exercici 3: Algoritme d'Optimització - Algoritme de Dijkstra

Descripció

Implementa l'algoritme de Dijkstra per trobar el camí més curt en un graf ponderat.

Pas a Pas

  1. Inicialització: Assigna una distància infinita a tots els nodes excepte el node inicial, que tindrà distància zero.
  2. Exploració: Selecciona el node amb la menor distància no visitat.
  3. Actualització: Actualitza les distàncies dels veïns del node seleccionat.
  4. Repetició: Repeteix els passos 2 i 3 fins que tots els nodes hagin estat visitats.

Exemple de Codi

import heapq

def dijkstra(graph, start):
    # Inicialització
    queue = [(0, start)]
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    visited = set()
    
    while queue:
        # Exploració
        current_distance, current_node = heapq.heappop(queue)
        
        if current_node in visited:
            continue
        
        visited.add(current_node)
        
        # Actualització
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    
    return distances

# Exemple de graf ponderat
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# Crida a la funció
print(dijkstra(graph, 'A'))  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Explicació del Codi

  • Inicialització: Utilitzem una cua de prioritat (heapq) per mantenir els nodes a explorar i un diccionari (distances) per mantenir les distàncies mínimes.
  • Exploració: Extreiem el node amb la menor distància de la cua de prioritat.
  • Actualització: Actualitzem les distàncies dels veïns del node seleccionat si trobem un camí més curt.

Exercici Pràctic

Implementa l'algoritme de Dijkstra per trobar el camí més curt en un graf ponderat més complex. Prova amb diferents nodes inicials.

Conclusió

En aquesta secció, hem treballat amb diversos algoritmes de cerca i optimització, implementant-los en Python i aplicant-los a problemes reals. Els exercicis pràctics proporcionen una base sòlida per comprendre com funcionen aquests algoritmes i com es poden aplicar en diferents contextos.

Errors Comuns i Consells

  • No inicialitzar correctament les estructures de dades: Assegura't de començar amb les estructures de dades buides o inicialitzades correctament.
  • Oblidar marcar els nodes com a visitats: Això pot provocar bucles infinits.
  • No actualitzar correctament les distàncies en Dijkstra: Comprova sempre si la nova distància és menor abans d'actualitzar.

Amb aquests exercicis, hauràs adquirit una comprensió pràctica dels algoritmes de cerca i optimització, preparant-te per a aplicacions més avançades en IA.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats