Embedded Files
Se parte de:
Un estado inicial.
Un conjunto finito de reglas de producción.
Uno o varios objetivos
2.1.1 Caracterización de problemas
Problemas prácticos
Búsqueda de rutas
Generalización del problema de ir hasta Bucarest.
Se añaden complicaciones como el coste en tiempo, dinero, disponibilidad de transporte, etc.
Ejemplo: viajes en líneas aéreas.
Problemas turísticos: visitar ciudades al menos una vez.
Problema del viajante comercial: viajar a una ciudad sólo una vez con un coste mínimo.
Distribución de componentes electrónicos en una tablilla de circuito impreso con un mínimo de área.
Navegación de robots.
Juegos.
Búsqueda en internet.
El primer paso para solucionar un problema es la formulación del objetivo, basado en la situación actual y la medida de rendimiento del agente.
La tarea del agente es encontrar qué secuencia de acciones permite obtener un estado objetivo.
Dado un objetivo, la formulación del problema es el proceso de decidir qué acciones y estados tenemos que considerar.
Busqueda. 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.
Un algoritmo de búsqueda toma como entrada un problema y devuelve una solución de la forma secuencia de acciones. Una vez que encontramos una solución, se procede a ejecutar las acciones que ésta recomienda. Esta es la llamada fase de ejecución.
Medidas de rendimiento.
Completitud: si existe la solución ¿la encuentra?
Optimización: si la encuentra ¿es la mejor?
Complejidad espacial-temporal: ¿cuánto tiempo y memoria se necesita para encontrar la solución?
En informática teórica se expresa mediante el tamaño del grafo.
En IA la dificultad del problema se expresa en función de:
Factor de ramificación: máximo número de sucesos por nodo.
Profundidad del objetivo: profundidad del objetivo menos profundo.
Profundidad máxima en el espacio de estados.
¿Qué cantidad de recursos son necesarios para encontrar la solución? (nodos almacenados en memoria)
¿cuánto se tarda en encontrar la solución? (número de nodos generados).
2.1.2 Espacios de búsqueda
Resolución de problemas con espacios de búsqueda
•Descripción de los estados
•Descripción del estado inicial y de los objetivos de la búsqueda.
•Descripción de las reglas que transforman los estados de la búsqueda.
Al Definir el problema, por tanto se define el espacio de búsqueda.
Problemas prácticos tienen espacios de búsqueda grandes.
No se pueden tener construcciones de grafos explícitos.
La búsqueda puede ser utilizada para planear secuencias de acciones.
Para realizar una búsqueda:
Terminología:
Estado inicial, punto de partida de la búsqueda.
Función sucesor, dado un estado x devuelve un conjunto ordenado de pares (acción, sucesor)
Espacio de búsqueda, conjunto de estados alcanzables a partir del estado inicial.
Camino, es una secuencia de estados conectados por una secuencia de acciones.
Coste del camino, es una función que asigna un coste numérico a cada camino. Suele ser la suma de costes de cada acción individual.
Prueba objetivo, determina si un estado es el objetivo.
Solución, secuencia de acciones que llevan del estado inicial a un estado objetivo. La que tenga coste del camino mínimo, serán óptimas.
Page updated
Google Sites
Report abuse