TC2032: Búsqueda sin Información

• TC2032 Diseño de Agentes Inteligentes: Búsqueda sin Información

Contenidos

• Solución de problemas mediante búsqueda.
• Búsqueda de soluciones.
• Algoritmos de búsqueda sin información (ciega).
• Comparación de algoritmos.
• Conclusiones.

Algoritmo general de búsqueda

• El algoritmo de búsqueda toma un problema y una estrategia como entrada y devuelve una solución o un fallo.
• Inicializa el árbol de búsqueda usando el estado inicial.
• Repite los siguientes pasos hasta encontrar una solución o un fallo:
• Si no hay nodos candidatos para expansión, regresa un fallo.
• Escoge un nodo hoja para la expansión de acuerdo a la estrategia.
• Si el nodo contiene un estado meta, regresa la solución.
• Expande el nodo y agrega los nodos resultantes al árbol de búsqueda.

Búsqueda de soluciones

• Árbol de búsqueda.
• Nodo de búsqueda.
• Distinción entre nodo y estado.
• Expansión de un nodo.
• Estrategia de búsqueda.
• Espacio de estados vs. árbol de búsqueda.

Representación de nodos

• Un nodo contiene información sobre el estado actual, el nodo padre, la acción realizada, la profundidad y el costo de la ruta.
• Los nodos se representan gráficamente con flechas que indican las posibles acciones.
• En el ejemplo, el nodo actual tiene como padre el Nodo padre y la acción realizada fue "abajo" con una profundidad de 6 y un costo de ruta de 6.

Estrategia de búsqueda

• La estrategia de búsqueda determina qué nodo será expandido a continuación.
• En el ejemplo, se muestra un grafo con tres nodos: París, Burdeos y Estrasburgo.
• La pregunta es ¿cuál de los dos nodos abiertos, Burdeos o Estrasburgo, se debe explorar primero?

Estrategia: Búsqueda de Árbol

• La función Búsqueda-de-Árbol toma un problema como entrada y devuelve una solución o un fallo.
• Inicializa la frontera usando el estado inicial del problema.
• Repite los siguientes pasos:
• Si la frontera está vacía, regresa un fallo.
• Escoge y remueve un nodo de la frontera.
• Si el nodo contiene un estado meta, regresa la solución correspondiente.
• Expande el nodo, agregando sus nodos sucesores a la frontera.

Estrategia: Búsqueda de Grafo

• La función Búsqueda-de-Grafo toma un problema como entrada y devuelve una solución o un fallo.
• Inicializa la frontera usando el estado inicial del problema.
• Inicializa el conjunto explorado como vacío.
• Repite los siguientes pasos:
• Si la frontera está vacía, regresa un fallo.
• Escoge y remueve un nodo de la frontera.
• Si el nodo contiene un estado meta, regresa la solución correspondiente.
• Agrega el nodo al conjunto explorado.
• Expande el nodo escogido, agregando sus nodos sucesores a la frontera solo si no está en la frontera o en el conjunto explorado.

Selección del Algoritmo de Búsqueda

• Criterios de desempeño: Completez, Optimalidad, Complejidad en tiempo y Complejidad en espacio.
• Medición de la Complejidad: Tiempo (nodos generados) y Espacio (nodos en memoria).

Búsqueda Sin Información

• Solo se utiliza la información de la formulación del problema.
• Algoritmos: Primero en anchura (breadth-first), Costo Uniforme (uniform cost), Primero en profundidad (depth-first), Limitada en profundidad (depth-limited), Profundización Iterativa (iterative deepening depth-first) y Bidireccional (bidirectional).

Búsqueda primero en anchura

• Se basa en checar todos los nodos de un nivel antes de expandir el árbol a un nivel más profundo, es decir, busca nivel por nivel.

Problema BFS: Explosión Combinatorial

• El problema BFS (Breadth-First Search) tiene una explosión combinatoria, lo que significa que requiere mucho tiempo y memoria a medida que aumenta la profundidad.
• A una profundidad de 2, se necesitan 110 nodos, 0.11 milisegundos y 107 kilobytes de memoria.
• A una profundidad de 16, se necesitan 10^16 nodos, 350 años y 10 exabytes de memoria.

Algoritmo de costo uniforme

• Es similar a la búsqueda primero en anchura.
• En lugar de expandir el nodo del menor nivel, se escoge el de menor costo acumulado.

Búsqueda primero en profundidad

• Expande el árbol de búsqueda rama por rama.
• Si una rama no lleva a una solución, se regresa a expandir la siguiente rama sin expandir más profunda (Backtracking).
• Es similar al de búsqueda en anchura, pero utiliza una pila en lugar de una fila.

Búsqueda con Profundización Iterativa y con Profundidad Limitada (Búsqueda de Árbol)

• La búsqueda con profundización iterativa ejecuta repetidamente la búsqueda limitada en profundidad, incrementando el límite de profundidad en cada iteración.
• La búsqueda con profundidad limitada marca un límite en la profundidad que será explorada.

Búsqueda bidireccional

• La idea de la búsqueda bidireccional es buscar en ambos sentidos.
• Se busca hacia adelante desde el estado inicial y hacia atrás desde la meta.

Comparación de estrategias

• Se evalúan los algoritmos de búsqueda en términos de completez, costo óptimo, tiempo y espacio.
• El factor de ramificación es b, la profundidad máxima del árbol de búsqueda es m, y la profundidad de la solución más superficial es d.
• l es el límite de profundidad.

Conclusiones

• El problema de búsqueda es uno de los más importantes en IA.
• Un problema de búsqueda se puede representar en un grafo, en términos de estados y operadores.
• Los algoritmos de búsqueda no informada son sistemáticos pero ineficientes en tiempo y en espacio.
• Para resolver problemas reales es necesario utilizar conocimiento específico del dominio.