Explorando la Inteligencia Artificial: Búsqueda y Estrategias Clave

Las definiciones de Inteligencia Artificial pueden agruparse en cuatro categorías:

• Pensar humanamente
• Pensar racionalmente
• Actuar humanamente
• Actuar racionalmente

La búsqueda puede ser informada si el agente conoce el resultado de la transición entre cada estado (por ejemplo, conocer el mapa de la ciudad y el tiempo estimado para cruzar de una calle a otra), o desinformada si no la conoce.

Formulación del Problema de Búsqueda

Formular, buscar, ejecutar.

Open Loop

Se refiere a un sistema de control donde el agente ejecuta acciones sin considerar las percepciones actuales del ambiente.

Infraestructura de Algoritmos de Búsqueda

Para cada nodo del árbol, tenemos una estructura que contiene cuatro componentes:

• .ESTADO: El estado en el espacio de estado al que corresponde el nodo.
• .PADRE: El nodo en el árbol de búsqueda que generó este nodo.
• .ACCION: La acción que se aplicó al padre para generar el nodo.
• .PATH-COST: El costo de la ruta desde el estado inicial hasta el nodo. Tradicionalmente denotado por g(n).

Manejando la Frontera

Las colas se caracterizan por el orden en que almacenan los nodos insertados. Las variantes más comunes son:

• Primero en salir o FIFO, que hace aparecer el elemento FIFO QUEUE más antiguo de la cola.
• Cola LIFO (último en entrar, primero en salir), también conocida como pila, que muestra el elemento más nuevo.
• Cola de prioridad, que muestra el elemento de la cola con la prioridad más alta según alguna función ordenadora.

Criterios de Desempeño de un Algoritmo de Búsqueda

Podemos evaluar el rendimiento de un algoritmo en cuatro maneras:

• Integridad o Completitud: ¿Se garantiza que el algoritmo encuentre una solución cuando la hay?
• Optimalidad: ¿La estrategia encuentra la solución óptima?
• Complejidad del tiempo: ¿Cuánto tiempo lleva encontrar una solución?
• Complejidad del espacio: ¿Cuánta memoria se necesita para realizar la búsqueda?

Tipos de Estrategias de Búsqueda Desinformadas

• Breadth-First Search (Búsqueda en amplitud)
• Uniform Cost Search (Búsqueda de costo uniforme)
• Depth-First Search (Búsqueda en profundidad)

Breadth-First Search

La búsqueda en amplitud es una estrategia simple en la que el nodo raíz se expande primero, luego se expanden todos los sucesores del nodo raíz, luego sus sucesores, y así sucesivamente. El mejor ejemplo para este método de búsqueda es una cola del supermercado.

• ¿Es completo?: Sí, ya que si el nodo final más superficial está a profundidad d, BFS lo encontrará cuando genere todos los nodos hasta dicha profundidad.
• ¿Es óptimo?: No necesariamente el nodo final más superficial generará la solución con menor costo (más óptima). La función de costo tendría que ser uniforme (todas las acciones con el mismo costo) para alcanzar el óptimo.

Uniform Cost Search

En lugar de expandir el nodo más superficial, la búsqueda de costo uniforme expande el nodo con el costo del camino más bajo. Esto se hace almacenando la frontera como una cola de prioridad ordenada por g.

• ¿Es completo?: Sí, ya que solo se prueban los nodos finales que se expanden, y solo se expandirá el nodo si es un camino de costo mínimo, considerando por supuesto que los costos son todos positivos. Ya que si hay costos cero, el algoritmo podría caer en un loop infinito.

Depth-First Search

Baja por la primera rama que encuentre sin importar el costo, hasta que no recorra todos los nodos de dicha rama, no pasará a la otra.

• ¿Es completo?: No, ya que puede caer en ramas de largo infinito si es que cae en loops. Para evitarlo, hay que revisar que el estado no se repita dentro del camino.
• ¿Es óptimo?: Tampoco es óptima, ya que podría encontrar una solución en otra rama diferente, la de menor costo.