Introducció
La cerca en espais d'estats és una tècnica fonamental en la resolució de problemes computacionals, especialment en intel·ligència artificial i teoria de jocs. Aquesta tècnica implica explorar un conjunt d'estats possibles per trobar una solució òptima o acceptable a un problema donat.
Conceptes Clau
- Espai d'Estats: Conjunt de tots els estats possibles que es poden assolir des d'un estat inicial mitjançant una sèrie d'operacions.
- Estat Inicial: El punt de partida en l'espai d'estats.
- Estat Final: L'objectiu o solució del problema.
- Operadors: Accions que transformen un estat en un altre.
- Camí: Seqüència d'operadors que condueixen d'un estat inicial a un estat final.
Algoritmes de Cerca en Espais d'Estats
Cerca en Amplitud (BFS)
La cerca en amplitud (Breadth-First Search, BFS) explora tots els estats a un nivell de profunditat abans de passar al següent nivell.
Pseudocodi
BFS(estat_inicial):
crear cua Q
afegir estat_inicial a Q
mentre Q no estigui buida:
estat_actual = Q.desencuar()
si estat_actual és l'estat_final:
retornar camí a estat_actual
per cada veí de estat_actual:
si veí no ha estat visitat:
marcar veí com visitat
afegir veí a QExemple
Considerem un problema de trobar el camí més curt en un laberint. Cada cel·la del laberint és un estat, i els moviments possibles (amunt, avall, esquerra, dreta) són els operadors.
Cerca en Profunditat (DFS)
La cerca en profunditat (Depth-First Search, DFS) explora tan profundament com sigui possible abans de retrocedir.
Pseudocodi
DFS(estat_inicial):
crear pila S
afegir estat_inicial a S
mentre S no estigui buida:
estat_actual = S.desapilar()
si estat_actual és l'estat_final:
retornar camí a estat_actual
per cada veí de estat_actual:
si veí no ha estat visitat:
marcar veí com visitat
afegir veí a SExemple
Considerem el mateix laberint. En aquest cas, DFS pot trobar un camí, però no necessàriament el més curt.
Cerca A*
La cerca A* és una tècnica heurística que combina els avantatges de BFS i DFS. Utilitza una funció de cost per prioritzar els estats a explorar.
Pseudocodi
A*(estat_inicial, estat_final):
crear cua de prioritat Q
afegir estat_inicial a Q amb prioritat 0
mentre Q no estigui buida:
estat_actual = Q.desencuar()
si estat_actual és l'estat_final:
retornar camí a estat_actual
per cada veí de estat_actual:
cost = cost fins a estat_actual + cost de moure's a veí
si veí no ha estat visitat o cost és menor que el cost anterior:
marcar veí com visitat
afegir veí a Q amb prioritat cost + heurística(veí, estat_final)Exemple
En el laberint, la funció heurística podria ser la distància Manhattan entre l'estat actual i l'estat final.
Exercicis Pràctics
Exercici 1: Implementació de BFS
Implementa l'algoritme BFS per trobar el camí més curt en un laberint representat com una matriu.
Solució
from collections import deque
def bfs(laberint, start, goal):
files = len(laberint)
columnes = len(laberint[0])
moviments = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cua = deque([start])
visitats = set()
visitats.add(start)
camins = {start: [start]}
while cua:
actual = cua.popleft()
if actual == goal:
return camins[actual]
for moviment in moviments:
veí = (actual[0] + moviment[0], actual[1] + moviment[1])
if 0 <= veí[0] < files and 0 <= veí[1] < columnes and laberint[veí[0]][veí[1]] == 0 and veí not in visitats:
visitats.add(veí)
cua.append(veí)
camins[veí] = camins[actual] + [veí]
return None
# Exemple d'ús
laberint = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
print(bfs(laberint, start, goal))Exercici 2: Implementació de DFS
Implementa l'algoritme DFS per trobar un camí en un laberint representat com una matriu.
Solució
def dfs(laberint, start, goal):
files = len(laberint)
columnes = len(laberint[0])
moviments = [(-1, 0), (1, 0), (0, -1), (0, 1)]
pila = [start]
visitats = set()
visitats.add(start)
camins = {start: [start]}
while pila:
actual = pila.pop()
if actual == goal:
return camins[actual]
for moviment in moviments:
veí = (actual[0] + moviment[0], actual[1] + moviment[1])
if 0 <= veí[0] < files and 0 <= veí[1] < columnes and laberint[veí[0]][veí[1]] == 0 and veí not in visitats:
visitats.add(veí)
pila.append(veí)
camins[veí] = camins[actual] + [veí]
return None
# Exemple d'ús
print(dfs(laberint, start, goal))Exercici 3: Implementació de Cerca A*
Implementa l'algoritme A* per trobar el camí més curt en un laberint representat com una matriu.
Solució
import heapq
def heuristica(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_star(laberint, start, goal):
files = len(laberint)
columnes = len(laberint[0])
moviments = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cua = []
heapq.heappush(cua, (0, start))
costos = {start: 0}
camins = {start: [start]}
while cua:
_, actual = heapq.heappop(cua)
if actual == goal:
return camins[actual]
for moviment in moviments:
veí = (actual[0] + moviment[0], actual[1] + moviment[1])
if 0 <= veí[0] < files and 0 <= veí[1] < columnes and laberint[veí[0]][veí[1]] == 0:
nou_cost = costos[actual] + 1
if veí not in costos or nou_cost < costos[veí]:
costos[veí] = nou_cost
prioritat = nou_cost + heuristica(veí, goal)
heapq.heappush(cua, (prioritat, veí))
camins[veí] = camins[actual] + [veí]
return None
# Exemple d'ús
print(a_star(laberint, start, goal))Resum
En aquesta secció, hem explorat diferents tècniques de cerca en espais d'estats, incloent BFS, DFS i A*. Hem vist com cadascun d'aquests algoritmes pot ser utilitzat per resoldre problemes de cerca en laberints i altres espais d'estats. També hem proporcionat exemples pràctics i exercicis per ajudar a consolidar els conceptes apresos.
Algoritmes Avançats
Mòdul 1: Introducció als Algoritmes Avançats
Mòdul 2: Algoritmes d'Optimització
- Programació Lineal
- Algoritmes d'Optimització Combinatòria
- Algoritmes Genètics
- Optimització de Colònia de Formigues
Mòdul 3: Algoritmes en Grafs
- Representació de Grafs
- Cerca en Grafs: BFS i DFS
- Algoritmes de Camins Mínims
- Algoritmes de Flux Màxim
- Algoritmes d'Aparellament en Grafs
Mòdul 4: Algoritmes de Cerca i Ordenació
Mòdul 5: Algoritmes d'Aprenentatge Automàtic
- Introducció a l'Aprenentatge Automàtic
- Algoritmes de Classificació
- Algoritmes de Regressió
- Xarxes Neuronals i Deep Learning
- Algoritmes de Clustering
Mòdul 6: Casos d'Estudi i Aplicacions
- Optimització en la Indústria
- Aplicacions de Grafs en Xarxes Socials
- Cerca i Ordenació en Grans Volums de Dades
- Aplicacions d'Aprenentatge Automàtic en la Vida Real