Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 3. Resolver problemas mediante búsqueda (Estrategia de búsqueda…
Capítulo 3. Resolver problemas mediante búsqueda
Agentes resolventes-problemas
Tercer paso: Búsqueda
Un agente con distintas opciones inmediatas de valores desconocidos puede decidir qué hacer, examinando las diferentes secuencias posibles de acciones que le conduzcan a estados de valores conocidos, y entonces escoger la mejor secuencia.
Primer paso: Formulación del objetivo
Los objetivos ayudan a organizar su comportamiento limitando
las metas que intenta alcanzar el agente.
La tarea del agente es encontrar qué secuencia
de acciones permite obtener un estado objetivo.
Objetivo
Conjunto de estados del mundo (exactamente aquellos estados que satisfacen el objetivo)
Segundo paso: Formulación del problema
Proceso de decidir qué acciones y estados tenemos que considerar.
Cuarto paso: Ejecución
Una vez que encontramos una solución, se procede a ejecutar las acciones que ésta recomienda.
Problemas y soluciones
Problema
Estado inicial
Estado en el que comienza el agente.
Una descripción de las posibles acciones disponibles por el agente
La formulación más común utiliza una función sucesor.
Función sucesor
La función sucesor genera los estados legales que resultan al intentar realizar acciones.
Espacio de estados del problema
Conjunto de todos los estados alcanzables desde el estado inicial
Definido por el estado inicial y la función sucesor.
El espacio de estados forma un grafo en el cual los nodos son estados y los arcos entre los nodos son acciones.
Un camino en el espacio de estados es una secuencia de estados conectados por una secuencia de acciones.
Test Objetivo
Determina si un estado es un estado objetivo.
Una función costo del camino
Asigna un costo numérico a cada camino.
El costo del camino puede describirse como la suma
de los costos de las acciones individuales a lo largo del camino.
Solución
Una solución a un problema es un camino desde el estado inicial a un estado objetivo.
La calidad de la solución se mide por la función costo del camino.
Solución óptima
Tiene el costo más pequeño del camino entre todas las soluciones.
Formular los problemas
Abstracción
Proceso de eliminar detalles de
una representación
Además de abstraer la descripción del estado, debemos abstraer sus acciones
La abstracción es válida si podemos ampliar cualquier solución abstracta a una
solución en el mundo más detallado
La abstracción es útil si al realizar cada una de las acciones en la solución es más
fácil que en el problema original
Ejemplos
Problemas con los juguetes
Problemas de la vida real
Búsqueda de Soluciones
Árbol de búsqueda
Nodo de búsqueda
Raíz del árbol de búsqueda, es el estado inicial.
Comprobar si es un estado objetivo.
Si no es un estado objetivo entonces:
Expandir y Generar
Se aplica la función objetivo
Se genera un nuevo conjunto de estados
Se continua escogiendo, comprobando y expandiendo
hasta que se encuentra una solución o no existen más estados para expandir.
El estado a expandir está determinado por la estrategia de búsqueda.
Estructura de datos usada para representar el árbol de búsqueda.
Formado por 5 componentes
Estado
El estado, del espacio de estados que corresponde con el nodo.
Nodo Padre
El nodo en el árbol que ha generado este nodo
Acción
La acción que se aplicará al padre para generar el nodo.
Costo del camino
El costo de un camino desde el estado inicial al nodo indicado por los punteros a los padres.
Profundidad
El número de pasos a lo largo del camino desde el estado inicial.
Frontera
Cada elemento de la frontera es un nodo hoja
Nodo hoja
Nodo sin sucesores en el árbol
Colección de nodos que se han generado pero todavía no se han expandido.
La estrategia de búsqueda será una función que seleccione de este conjunto el siguiente nodo a expandir
Se implementa con una cola
Hacer cola
Crea una cola con los elementos dados
¿Vacía?
Devuelve verdadero si no hay un elemento en la cola
Primero
Devuelve el primer elemento de la cola
Borrar - primero
Devuelve el primer elemento y lo borra de la cola
Inserta
Inserta un elemento en la cola y devuelve la cola resultado
Insertar - todo
Inserta un conjunto de elementos en la cola
Medir el rendimiento de la solución del problema
Completitud
¿Está garantizado que el algoritmo encuentre una solución cuando esta exista?
Optimización
¿La estrategia encuentra la solución óptima?
Complejidad en tiempo
¿Cuánto tarda en encontrar una solución?
Complejidad en espacio
¿Cuánta memoria se necesita para el funcionamiento de
la búsqueda?
Estrategia de búsqueda no informada
Búsqueda primero en anchura
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, etc.
Búsqueda de costo uniforme
Expande el nodo n con la ruta de costo más pequeña.
Búsqueda primero en profundidad
Siempre expande el nodo más profundo en el borde actual del árbol de búsqueda.
Búsqueda de profundidad limitada
Se realiza con un límite de profundidad predeterminado t, tratando los nodos en profundidad t como si no tuvieran un sucesor.
Búsqueda primero en profundidad con profundidad
iterativa
Aplicar repetidamente la búsqueda de profundidad limitada aumentando el límite. Termina cuando se encuentra una solución
Búsqueda bidireccional
Ejecuta dos búsquedas simultáneas: una hacia adelante desde el estado inicial y la otra hacia atrás desde el objetivo, deteniéndose cuando las dos búsquedas están en el centro.
Búsqueda con información parcial
Problemas
Problemas sin sensores
El agente no tiene sensores, por lo que podría estar en uno de los posibles estados iniciales, y cada acción podría conducir a uno de los posibles estados sucesores
Problemas de contingencia
Si el entorno es parcialmente observable o si las acciones son inciertas, entonces las percepciones del agente proporcionan nueva información después de cada acción.
Problemas de exploración
Cuando se desconocen los estados y las acciones del entorno, el agente debe actuar para descubrirlos
Evitar estados repetidos
La eliminación de estados repetidos produce una reducción exponencial del costo de la búsqueda.
Para algunos problemas, la repetición de estados es inevitable.
Problemas de búsqueda de rutas
Puzles que deslizan sus piezas
Si el algoritmo no detecta los estados repetidos, éstos pueden provocar que
un problema resoluble llegue a ser irresoluble.