Please enable JavaScript.
Coggle requires JavaScript to display documents.
IA: Resolver problemas mediante búsqueda (Estrategias de búsqueda no…
IA: Resolver problemas mediante búsqueda
Agentes resolventes-problemas
Formulación del (objetivo: como un conjunto de estados del mundo)
Formulación del problema: proceso qué decide cuales acciones y estados tenemos que considerar
Problemas y soluciones bien definidos
Un Problema tiene 4 componentes:
Estado inicial
Función sucesor:
da las posibles acciones y con el estado inicial dan el
espacio de estados
.
Test-objetivo:
determina si un estado es objetivo
Costo del camino:
asigna un costo a cada camino
Formular los problemas
Abstracción: el procesos de eliminar detalles de una representación
Ejemplos:
Problemas de juguete
Aspiradora
8-puzzle
8 reinas
Formulación incremental:
aumentan la descripción del estado, se inicia con un estado vacío.
Formulación completa de estados:
comienza con las ocho reinas en el tablero y las mueve.
Problemas del mundo real: mayor preocupación
Búsqueda de una ruta
Los problemas turísticos
El problema del viajante de comercio: encontrar el viaje más corto.
Problema de distribución VLSI: colocar de millones de componentes con una área mínima.
Distribución de las celdas
Dirección del canal
Navegación de un robot
La secuenciación para el ensamblaje automático
Diseño de proteínas
Búsqueda en Internet
Secuencia solución:
La
búsqueda
toma un problema y devuelve la
solución.
Lazo abierto:
hacen planes con los ojos cerrados, osea están completamente seguros.
Fase de Ejecución:
se ejecutan las acciones
Luego de esto, el agente formula un nuevo objetivo.
Búsqueda de soluciones
Árbol de búsqueda
Raíz: es el nodo de búsqueda
Pasos:
Comprobar si éste es un estado objetivo
Sino expandir el estado actual
Generar un nuevo conjunto de estados
Determinado por la estrategia de búsqueda
Nodo y componentes
Nodo padre
Estado
Acción
Costo del camino
Profundidad
Frontera:
nodos generados pero no se han expandido, osea son nodos hoja.
Coleecion de nodos: se pueden implementar como:
Cola
Medir el rendimiento de la resolución del problema
Completitud
Optimización
Complejidad en tiempo
Complejidad en espacio
Ambas complejidades se expresa en términos de:
Factor de ramificación
Profundidad del nodo
Longitud máxima de cualquier camino
Para valorar eficiencia
Coste total
Coste de la búsqueda
Estrategias de búsqueda no informada
Búsqueda primero en anchura:
es una estrategia sencilla en la que se expande primero el nodo raíz, luego se expanden todos los sucesores del nodo raíz
Búsqueda de costo uniforme:
expande el nodo n con el camino de costo más pequeño
Búsqueda primero en profundidad:
siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda.
Pila
Variante:
Búsqueda hacia
atrás, utiliza todavía menos memoria, expande solo un sucesor a la vez.
Búsqueda de profundidad limitada:
Es una búsqueda primero en profundidad pero con un límite.
El diámetro del espacio de estados, nos da un mejor límite
Búsqueda primero en profundidad con profundidad iterativa:
encuentra el mejor límite de profundidad
Búsqueda bidireccional:
ejecuta dos búsquedas simultáneas, una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo
Cuando se topan han encontrado una solución
Evitar estados repetidos
Guardar más nodos en la memoria
Lista cerrada:
nodos expandidos
Lista abierta:
nodos frontera
Búsqueda con información parcial
Problemas sin sensores o problemas conformados
Ocupa estado de creencia
Problemas de contingencia:
entorno es parcialmente observable, percepciones dan nueva info después de acciones.
Intercalar la búsqueda y la ejecución es también útil para problemas de exploración
Problemas de exploración:
debe actuar para descubrir.