Salta el contingut

Resolució de problemes: cerca en espais d'estats

Molts dels problemes que ha de resoldre un agent intel·ligent es poden formular com un problema de cerca: partint d'una situació inicial, trobar la seqüència d'accions que porta a un objectiu. Aquesta família de tècniques —anteriors al deep learning i encara vigents avui (navegadors GPS, videojocs, optimització de rutes)— és una de les tècniques bàsiques de la IA que tot professional IABD ha de conèixer.

Espai d'estats

Un problema de cerca es defineix formalment amb cinc elements:

  1. Estat inicial: el punt de partida.
  2. Estat final (o condicions objectiu): què hem d'assolir.
  3. Operadors: funcions de transformació que porten d'un estat a un altre (amb les seves condicions d'aplicabilitat).
  4. Espai d'estats: el conjunt de tots els estats i les relacions d'accessibilitat entre ells (representat com a arbre o graf).
  5. Tipus de solució buscada: una solució qualsevol, totes les solucions, o la de menor cost.

Exemple clàssic — el 8-puzzle: l'estat és la configuració de les 8 fitxes al tauler 3×3, l'operador és "moure el buit" (amunt/avall/esquerra/dreta), i l'objectiu és arribar a una configuració ordenada concreta. Amb 9 posicions i 8 fitxes numerades, l'espai d'estats té 9! = 362.880 configuracions possibles.

funció Cerca_en_espai_d_estats retorna solucio
    Seleccionar el primer estat com l-estat actual
    mentre l-estat actual no sigui l-estat final fer
        Generar i guardar successors de l-estat actual (expansio)
        Escollir el seguent estat entre els pendents (seleccio)
    fmentre
    retorna solucio
ffuncio

Tots els algorismes d'aquesta pàgina comparteixen aquest esquema expansió + selecció: el que canvia entre ells és, exactament, com se selecciona el següent node a explorar.

Per comparar algorismes de cerca es fan servir quatre propietats: completitud (sempre troba una solució si n'hi ha?), optimalitat (troba la millor solució?), complexitat temporal i complexitat espacial (en funció del factor de ramificació r i la profunditat de la solució p).

Cerca cega o no informada

Els algorismes de cerca cega no fan servir cap coneixement específic del problema: exploren l'espai d'estats de manera sistemàtica, sense estimar quins camins són més prometedors.

BFS — Primer en amplada (Breadth-First Search)

Explora l'espai d'estats nivell a nivell, usant una cua (FIFO). És complet i òptim en nombre de passos, però la seva complexitat espacial és exponencial: O(r^(p+1)).

from collections import deque

def bfs(graf, inici, objectiu):
    """Cerca en amplada sobre un graf representat com a diccionari d'adjacencia."""
    frontera = deque([[inici]])
    visitats = {inici}

    while frontera:
        cami = frontera.popleft()
        node = cami[-1]

        if node == objectiu:
            return cami

        for veí in graf.get(node, []):
            if veí not in visitats:
                visitats.add(veí)
                frontera.append(cami + [veí])

    return None  # No hi ha solucio

graf = {
    'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G'],
    'D': ['G'], 'E': ['D', 'G'], 'F': ['G'], 'G': [],
}
print(bfs(graf, 'A', 'G'))  # ['A', 'B', 'D', 'G'] (el cami mes curt en nombre de salts)

DFS — Primer en profunditat (Depth-First Search)

Explora fins al fons d'una branca abans de retrocedir, usant una pila (LIFO). Cal imposar un límit de profunditat perquè acabi. No garanteix la solució òptima, però té complexitat espacial molt més baixa que BFS: O(r·p).

UCS — Cost uniforme (Uniform Cost Search)

Com BFS, però expandeix sempre el node de menor cost acumulat conegut fins al moment (no el més antic a la cua). Òptim quan els costos de les accions no són tots iguals.

IDS — Aprofundiment iteratiu (Iterative Deepening Search)

Combina el millor de BFS i DFS: fa cerques en profunditat successives amb un límit de profunditat creixent (1, 2, 3...). Aconsegueix la completesa i optimalitat de BFS amb la complexitat espacial lineal de DFS —a costa de regenerar nodes ja visitats a cada iteració.

Cerca bidireccional: quan es coneix l'estat objectiu, es pot buscar simultàniament des de l'inici i des del final fins que els dos fronts es troben, reduint dràsticament el nombre de nodes explorats.

Cerca heurística: Greedy, A* i IDA*

La cerca informada aprofita coneixement del domini (una funció heurística h(n), que estima el cost restant fins a l'objectiu) per prioritzar quins nodes explorar primer.

Greedy Best-First Search: expandeix sempre el node amb menor h(n) (menor distància estimada a l'objectiu). És ràpid però ni complet ni òptim: una heurística que enganya pot portar-lo per camins sense sortida.

A*: combina el cost real acumulat g(n) amb l'heurística h(n) en una única funció d'avaluació:

f(n) = g(n) + h(n)

A* és òptim si h(n) és admissible (mai sobreestima el cost real restant) — per exemple, la distància en línia recta en un problema de rutes. Amb una heurística admissible i consistent (h(n) ≤ cost(n,n') + h(n')), A* garanteix trobar la solució de menor cost.

import heapq

def a_estrella(graf_amb_cost, heuristica, inici, objectiu):
    """A* sobre un graf { node: [(veí, cost), ...] }."""
    oberts = [(heuristica[inici], 0, inici, [inici])]  # (f, g, node, cami)
    visitats = {}

    while oberts:
        f, g, node, cami = heapq.heappop(oberts)

        if node == objectiu:
            return cami, g

        if node in visitats and visitats[node] <= g:
            continue
        visitats[node] = g

        for veí, cost in graf_amb_cost.get(node, []):
            nou_g = g + cost
            nou_f = nou_g + heuristica.get(veí, 0)
            heapq.heappush(oberts, (nou_f, nou_g, veí, cami + [veí]))

    return None, float('inf')

graf_cost = {
    'Arad': [('Sibiu', 140), ('Timisoara', 118), ('Zerind', 75)],
    'Sibiu': [('Fagaras', 99), ('RimnicuVilcea', 80)],
    'Fagaras': [('Bucarest', 211)],
    'RimnicuVilcea': [('Pitesti', 97)],
    'Pitesti': [('Bucarest', 101)],
    'Timisoara': [], 'Zerind': [], 'Bucarest': [],
}
heur = {  # distancia en linia recta fins a Bucarest
    'Arad': 366, 'Sibiu': 253, 'Fagaras': 178, 'RimnicuVilcea': 193,
    'Pitesti': 98, 'Timisoara': 329, 'Zerind': 374, 'Bucarest': 0,
}
cami, cost = a_estrella(graf_cost, heur, 'Arad', 'Bucarest')
print(f"Camí: {cami}, cost total: {cost}")

IDA* (Iterative Deepening A*): aplica la mateixa idea que IDS però fent servir f(n)=g(n)+h(n) com a límit d'aprofundiment (en lloc de la profunditat). Manté la complexitat espacial lineal de DFS però amb la qualitat de cerca d'A*, a costa de reexplorar nodes a cada iteració.

Cerca local: hill-climbing, temperat simulat i algorismes genètics

Quan el camí fins a la solució no importa (només l'estat final) i l'espai de cerca és enorme, és més eficient moure's entre estats veïns intentant millorar una funció d'avaluació, en lloc de mantenir tot un arbre de cerca.

Hill-climbing (escalada): parteix d'un estat (sovint aleatori) i es mou repetidament cap al millor veí, fins que cap veí millora l'estat actual. Complexitat espacial constant (només cal recordar l'estat actual!), però es pot quedar atrapat en un màxim local.

import random

def hill_climbing(estat_inicial, generar_veins, avaluar, iteracions_max=1000):
    """Escalada simple: es queda amb el primer veí que millori l-estat actual."""
    actual = estat_inicial
    for _ in range(iteracions_max):
        veins = generar_veins(actual)
        millor_vei = max(veins, key=avaluar, default=None)
        if millor_vei is None or avaluar(millor_vei) <= avaluar(actual):
            break  # Maxim local: cap veí millora l-actual
        actual = millor_vei
    return actual

Simulated Annealing (temperat simulat): igual que hill-climbing, però de tant en tant accepta moviments que empitjoren la solució, amb una probabilitat e^(-ΔE/T) que depèn d'una "temperatura" T que va baixant. Al principi (temperatura alta) explora molt, cap al final (temperatura baixa) es comporta com hill-climbing. Això li permet escapar de màxims locals.

Algorismes genètics: mantenen una població de solucions candidates (cadascuna codificada com un "gen", sovint una cadena de bits) que evoluciona per generacions mitjançant:

  • Selecció: els individus amb millor funció de qualitat (fitness) tenen més probabilitat de reproduir-se.
  • Creuament (crossover): dos individus "pares" intercanvien parts de la seva codificació per generar-ne de nous.
  • Mutació: canvis aleatoris i puntuals en la codificació, per mantenir diversitat i evitar convergència prematura.
graph LR
    P[Poblacio inicial aleatoria] --> S[Seleccio segons fitness]
    S --> C[Creuament de parelles]
    C --> M[Mutacio aleatoria]
    M --> N[Nova generacio]
    N -->|Repeteix fins convergir| S

Miniactivitat — AC5071/01/05 — Hill-climbing per al problema de les 8 reines

El problema de les 8 reines consisteix a col·locar 8 reines en un tauler d'escacs 8×8 sense que cap es puguin capturar mútuament (cap parell a la mateixa fila, columna o diagonal). Implementa una funció d'avaluació que compti el nombre de parelles de reines que s'ataquen (com menys, millor) i aplica l'algorisme d'escalada simple de dalt per intentar arribar a 0 atacs des d'una configuració aleatòria inicial. Executa'l 20 vegades i registra en quants intents troba una solució òptima (recorda: amb hill-climbing simple només ho aconsegueix al voltant del 14% de les vegades).