La inteligencia artificial utiliza grafos para representar estados, acciones, conocimiento, dependencias y probabilidades. Buscar una solución equivale con frecuencia a encontrar un camino dentro de una estructura enorme.
Resolver un rompecabezas, construir un plan o responder preguntas sobre conocimiento puede formularse mediante vértices y aristas.
El reto no suele ser dibujar el grafo completo, sino explorarlo implícitamente sin agotar tiempo y memoria.
Un estado describe toda la información necesaria para decidir el futuro. Una acción válida conecta el estado actual con uno nuevo.
Dos secuencias de acciones pueden conducir al mismo estado, por lo que el espacio es normalmente un grafo y no un árbol.
La representación debe distinguir situaciones con futuros diferentes y unificar las equivalentes.
Una forma canónica permite detectar estados visitados. Si se omite información relevante, se mezclan problemas distintos; si sobra información, el grafo crece innecesariamente.
BFS explora por cantidad de acciones y encuentra caminos con el mínimo número de aristas en grafos no ponderados. DFS consume poca memoria, pero puede internarse en ramas poco útiles.
Uniform Cost Search prioriza el costo acumulado y encuentra rutas óptimas con costos no negativos.
Una heurística h(n) estima la distancia restante hasta una meta. La búsqueda voraz prioriza h(n), mientras A* combina costo real y estimado.
La voraz puede ser rápida, pero ignora lo que ya costó llegar al estado.
Selecciona un algoritmo y avanza. BFS minimiza saltos, la voraz sigue la estimación y A* combina costos para encontrar la ruta óptima.
Frontera ordenada
Ruta resultante
Acción actual
Una heurística admisible nunca sobreestima el costo óptimo restante. Una heurística consistente satisface h(u) ≤ costo(u,v) + h(v).
Con estas condiciones, A* puede garantizar optimalidad de manera eficiente.
Una heurística puede derivarse de una versión relajada del problema, donde se eliminan restricciones. El costo óptimo del problema relajado es una cota inferior.
También pueden precomputarse bases de patrones o combinarse heurísticas tomando su máximo cuando todas son admisibles.
function prioridad(nodo, algoritmo) {
if (algoritmo === "bfs") return nodo.profundidad;
if (algoritmo === "voraz") return nodo.h;
return nodo.g + nodo.h; // A*
}
while (!frontera.estaVacia()) {
const actual = frontera.extraerMinimo();
if (esMeta(actual.estado)) return reconstruir(actual);
expandir(actual).forEach(sucesor => frontera.insertar(sucesor));
}En planificación, un estado describe hechos verdaderos y cada acción posee precondiciones y efectos.
La meta puede ser parcial: basta con alcanzar un estado que satisfaga ciertas condiciones, sin especificar todos sus detalles.
Un grafo de planificación alterna niveles de hechos y acciones, registrando incompatibilidades. Ayuda a estimar qué metas pueden alcanzarse conjuntamente y a extraer planes.
Las dependencias y exclusiones proporcionan heurísticas más informativas que contar simplemente metas pendientes.
En un grafo OR basta elegir uno de varios sucesores. En un nodo AND deben resolverse varios subproblemas.
Diagnóstico, demostración automática y planes con contingencias pueden requerir esta estructura en lugar de un camino lineal.
Entidades como personas, lugares y conceptos se conectan mediante relaciones tipadas. El grafo permite integrar datos y responder consultas de varios saltos.
La inferencia puede combinar reglas, recorridos y modelos aprendidos.
Una red bayesiana es un DAG donde los vértices son variables aleatorias y las aristas representan dependencias condicionales directas.
La factorización conjunta sigue el orden de padres: P(X₁,...,Xₙ) = ∏ P(Xᵢ | padres(Xᵢ)).
Una red de Markov utiliza un grafo no dirigido para representar dependencias. Las distribuciones se expresan mediante factores sobre cliques.
Son adecuadas cuando la relación no tiene una dirección causal natural, por ejemplo en ciertas tareas de visión o etiquetado.
Las GNN actualizan la representación de cada nodo agregando información de sus vecinos. Varias capas permiten incorporar vecindarios más lejanos.
Se aplican a moléculas, recomendaciones, tráfico, conocimiento y predicción de enlaces.
En juegos adversarios, los estados forman vértices y las jugadas aristas. Minimax alterna decisiones de jugadores con objetivos opuestos.
Monte Carlo Tree Search construye solo una parte del árbol y equilibra exploración de opciones nuevas con explotación de las prometedoras.
Con factor de ramificación b y profundidad d, una búsqueda puede generar O(bᵈ) estados. Las podas, heurísticas y abstracciones son esenciales.
También deben controlarse memoria, estados repetidos y costo de generar sucesores.
Los grafos proporcionan un lenguaje común para distintas áreas de IA. Una solución puede ser un camino, un subgrafo, una asignación probabilística o una representación aprendida.
En el próximo tema estudiaremos grafos en redes de computadoras, donde los vértices y enlaces representan dispositivos, rutas y capacidades reales.