Agentes Inteligentes, Búsqueda Best-First y Breadth-First: Conceptos y Algoritmos

Agentes Inteligentes: Definición y Tipos de Entornos

Un agente inteligente es una entidad capaz de percibir su entorno, procesar dichas percepciones y responder o actuar en él de manera racional. Esto significa que actúa de forma correcta y buscando maximizar un resultado esperado.

Los agentes operan dentro de un ambiente, y existen varios tipos de entornos:

• Accesible vs. Inaccesible: En un entorno accesible, los sensores del agente proporcionan toda la información relevante.
• Determinístico vs. No Determinístico: En un entorno determinista, el estado siguiente puede obtenerse a partir del estado actual y de las acciones del agente.
• Episódico vs. No Episódico: Los ambientes episódicos son más sencillos, ya que el agente no necesita pensar a futuro.
• Discreto vs. Continuo: En un entorno discreto, existe un número concreto de percepciones y acciones claramente definidas. Por ejemplo, el ajedrez es discreto porque hay una cantidad fija de movimientos en cada jugada.
• Estático vs. Dinámico: Un entorno dinámico puede sufrir cambios mientras el agente está razonando. En un ambiente estático, el agente no tiene que preocuparse por el paso del tiempo.

Algoritmo de Búsqueda Best-First (Primero el Mejor)

En la búsqueda Best-First, se expande primero el nodo con la mejor evaluación. No se expande necesariamente el "mejor" nodo, sino el que *parece* ser el mejor según la función de evaluación. Se consideran todos los nodos vistos hasta el momento.

Usar el costo acumulado (como en la búsqueda de costo uniforme) no siempre guía la búsqueda hacia la meta. Para ello, se utiliza una estimación del costo del camino desde el estado actual hasta una meta (h(n)). Esta estrategia, que minimiza el costo estimado para alcanzar una meta, se conoce como estrategia "greedy" (voraz).

La función de evaluación (h) puede ser cualquier función, siempre y cuando h(n) = 0 si n es una meta. Una estrategia greedy es susceptible de errores. El tiempo, en el peor de los casos, es O(b^m), donde m es la profundidad máxima del espacio de búsqueda.

Algoritmo de Búsqueda Breadth-First (Búsqueda en Anchura)

El algoritmo Breadth-First (BFS) es un algoritmo de búsqueda en grafos que comienza en el nodo raíz y explora todos los nodos vecinos. Luego, para cada uno de esos nodos, explora sus vecinos no explorados, y así sucesivamente, hasta encontrar el objetivo.

¿Cómo funciona BFS?

BFS explora exhaustivamente el grafo o secuencia sin considerar el objetivo hasta que lo encuentra. No utiliza una heurística. Desde la perspectiva del algoritmo, todos los nodos hijos obtenidos al expandir un nodo se añaden a una cola FIFO (First-In, First-Out).

En implementaciones típicas, los nodos que aún no han sido examinados se colocan en un contenedor (como una cola o una lista enlazada) llamado "abierto", y una vez examinados, se colocan en el contenedor "cerrado".

Algoritmo BFS

1. Poner en cola el nodo raíz.
2. Sacar de la cola un nodo y examinarlo:
   • Si el elemento buscado se encuentra en este nodo, detener la búsqueda y devolver el resultado.
   • De lo contrario, poner en cola cualquier sucesor (nodos hijos directos) que aún no haya sido examinado.
3. Si la cola está vacía, todos los nodos del grafo han sido examinados. Detener la búsqueda y devolver "no encontrado".
4. Repetir el paso 2.

Procedimiento de BFS

• Dado un vértice fuente s, Breadth-first search explora sistemáticamente los vértices de G para “descubrir” todos los vértices alcanzables desde s.
• Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables.
• Produce un árbol BF con raíz en s que contiene a todos los vértices alcanzables.
• El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.

El nombre "búsqueda en anchura" se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k solo después de haber llegado a todos los nodos a distancia k-1.