Els algoritmes de cerca són fonamentals en la intel·ligència artificial, ja que permeten trobar solucions a problemes complexos explorant espais de solucions possibles. En aquest tema, explorarem els conceptes bàsics dels algoritmes de cerca, els tipus principals i alguns exemples pràctics.

Un algoritme de cerca és un procediment pas a pas utilitzat per trobar una solució a un problema donat. Aquests algoritmes poden ser utilitzats en una varietat de contextos, com ara la resolució de puzles, la navegació en mapes, i la planificació d'accions en sistemes autònoms.

• Espai d'Estats: Conjunt de tots els estats possibles que es poden assolir des de l'estat inicial.
• Estat Inicial: El punt de partida del problema.
• Estat Final o Objectiu: L'estat que representa la solució del problema.
• Operadors: Accions que permeten moure's d'un estat a un altre dins de l'espai d'estats.
• Camí: Seqüència d'operadors que porta de l'estat inicial a l'estat final.

Els algoritmes de cerca no informada no tenen informació addicional sobre l'espai d'estats més enllà de la definició del problema. Alguns exemples inclouen:

1. Cerca en Ample (Breadth-First Search, BFS)

   • Explora tots els nodes a un nivell de profunditat abans de passar al següent nivell.
   • Avantatges: Troba la solució més curta (en termes de nombre de passos).
   • Desavantatges: Pot requerir molta memòria.

   from collections import deque
   
   def bfs(graph, start, goal):
       queue = deque([start])
       visited = set()
       while queue:
           node = queue.popleft()
           if node == goal:
               return True
           if node not in visited:
               visited.add(node)
               queue.extend(graph[node] - visited)
       return False
   

2. Cerca en Profunditat (Depth-First Search, DFS)

   • Explora tan profundament com sigui possible abans de retrocedir.
   • Avantatges: Requereix menys memòria que BFS.
   • Desavantatges: Pot quedar atrapat en bucles infinits si no es controla.

   def dfs(graph, start, goal, visited=None):
       if visited is None:
           visited = set()
       visited.add(start)
       if start == goal:
           return True
       for next in graph[start] - visited:
           if dfs(graph, next, goal, visited):
               return True
       return False
   

Els algoritmes de cerca informada utilitzen informació addicional (heurística) per guiar la cerca cap a la solució de manera més eficient.

1. Cerca A*

   • Utilitza una funció heurística per estimar el cost total des de l'estat inicial fins a l'objectiu.
   • Avantatges: Pot ser molt més eficient que BFS i DFS.
   • Desavantatges: La qualitat de la solució depèn de la precisió de la funció heurística.

   import heapq
   
   def a_star(graph, start, goal, h):
       open_set = []
       heapq.heappush(open_set, (0, start))
       came_from = {}
       g_score = {start: 0}
       f_score = {start: h(start, goal)}
   
       while open_set:
           _, current = heapq.heappop(open_set)
           if current == goal:
               return reconstruct_path(came_from, current)
           for neighbor in graph[current]:
               tentative_g_score = g_score[current] + graph[current][neighbor]
               if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                   came_from[neighbor] = current
                   g_score[neighbor] = tentative_g_score
                   f_score[neighbor] = g_score[neighbor] + h(neighbor, goal)
                   heapq.heappush(open_set, (f_score[neighbor], neighbor))
       return False
   
   def reconstruct_path(came_from, current):
       total_path = [current]
       while current in came_from:
           current = came_from[current]
           total_path.append(current)
       return total_path[::-1]
   

Implementa l'algoritme de Cerca en Ample per a un graf donat i troba el camí més curt entre dos nodes.

Implementa l'algoritme de Cerca en Profunditat per a un graf donat i determina si existeix un camí entre dos nodes.

Implementa l'algoritme A* per a un graf donat amb una funció heurística adequada i troba el camí més eficient entre dos nodes.

En aquesta secció hem explorat els conceptes bàsics dels algoritmes de cerca, incloent-hi la cerca no informada i la cerca informada. Hem vist exemples pràctics de BFS, DFS i A*, i hem proporcionat exercicis per reforçar els conceptes apresos. Els algoritmes de cerca són una eina poderosa en la intel·ligència artificial, i comprendre'ls és essencial per a qualsevol professional en aquest camp.