Tecnología en Desarrollo De Software
Tema:
0407 practica 04 Resolver problemas mediante búsqueda
Nombre y Apellido:
Richard Benitez
Matricula:
2021-0480
Profesor:
Jorge Ramon Taveras Gonzalez
Materia:
Inteligencia Artificial
Fecha de Entrega:
08-06-2023
• Agentes resolventes-problemas:
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. Para esto,
necesitamos decidir qué acciones y estados considerar. Si se utilizaran acciones del tipo
«mueve el pie izquierdo hacia delante» o «gira el volante un grado a la izquierda»,
probablemente el agente nunca encontraría la salida del aparcamiento.
Dado un objetivo, la formulación del problema es el proceso de decidir qué acciones y
estados tenemos que considerar. Discutiremos con más detalle este proceso. Por ahora,
suponemos que el agente considerará acciones del tipo conducir de una ciudad grande a
otra. Consideraremos los estados que corresponden a estar en una ciudad determinada.
Pero, supongamos que el agente tiene un mapa de República Dominicana, en papel o en
su memoria. El propósito del mapa es dotar al agente de información sobre los estados
en los que podría encontrarse, así como las acciones que puede tomar. El agente puede
usar esta información para considerar los siguientes estados de un viaje hipotético por
cada una de las ciudades, intentando encontrar un viaje que llegue a su ciudad destino.
Una vez que ha encontrado un camino en el mapa desde una ciudad a otra, puede
alcanzar su objetivo, tomando las acciones de conducir que corresponden con los tramos
del viaje.
Este proceso de hallar esta secuencia se llama búsqueda. 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. Así, tenemos un diseño simple de
un agente «formular, buscar, ejecutar».
• Ejemplos de problemas:
Un problema puede definirse, formalmente, por varios componentes:
1. El estado inicial en el que comienza el agente. Por ejemplo, el estado inicial para
nuestro agente en San Pedro de Macorís.
2. Una descripción de las posibles acciones disponibles por el agente. La
formulación más común utiliza una función sucesor. Dado un estado particular
x, SUCESOR-FN(x) devuelve un conjunto de pares ordenados <acción,
sucesor>, donde cada acción es una de las acciones legales en el estado x y cada
sucesor es un estado que puede alcanzarse desde x, aplicando la acción.
El primer ejemplo que examinaremos es el mundo de la aspiradora, Éste puede
formularse como:
• Estados: el agente está en una de dos localizaciones, cada una de las cuales puede o no
contener suciedad. Así, hay 2 * 2(2)= 8 posibles estados del mundo.
• Estado inicial: cualquier estado puede designarse como un estado inicial.
• Función sucesor: ésta genera los estados legales que resultan al intentar las tres
acciones (Izquierda, Derecha y Aspirar). En la Figura 3.3 se muestra el espacio de
estados completo.
• Test objetivo: comprueba si todos los cuadrados están limpios.
• Costo del camino: cada costo individual es 1, así que el costo del camino es el número
de pasos que lo compone. Comparado con el mundo real, este problema de juguete tiene
localizaciones discretas, suciedad discreta, limpieza fiable, y nunca se ensucia una vez
que se ha limpiado.
• Búsqueda de soluciones
La raíz del árbol de búsqueda es el nodo de búsqueda que corresponde al estado inicial,
En (San Pedro de Macorís). El primer paso es comprobar si éste es un estado objetivo.
Claramente es que no, pero es importante comprobarlo de modo que podamos resolver
problemas como «comenzar en San Pedro de Macorís, consigue SPM». Como no
estamos en un estado objetivo, tenemos que considerar otros estados. Esto se hace
expandiendo el estado actual; es decir aplicando la función sucesor al estado actual y
generar así un nuevo conjunto de estados.
Hay muchas formas de representar los nodos, pero vamos a suponer que un nodo es una
estructura de datos con cinco componentes:
— ESTADO: el estado, del espacio de estados, que corresponde con el nodo;
— NODO PADRE: el nodo en el árbol de búsqueda que ha generado este nodo;
— ACCIÓN: la acción que se aplicará al padre para generar el nodo;
— COSTO DEL CAMINO: el costo, tradicionalmente denotado por g(n), de un
camino desde el estado inicial al nodo, indicado por los punteros a los padres; y
— PROFUNDIDAD: el número de pasos a los largo del camino desde el estado inicial.
Es importante recordar la distinción entre nodos y estados. Un nodo es una estructura de
datos usada para representar el árbol de búsqueda. Un estado corresponde a una
configuración del mundo. Así, los nodos están en caminos particulares, según lo
definido por los punteros del nodo padre, mientras que los estados no lo están.
• Estrategias de búsqueda no informadas:
Esta sección trata cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda
no informada (llamada también búsqueda a ciegas). El término significa que ellas no
tienen información adicional acerca de los estados más allá de la que proporciona la
definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y
distinguir entre un estado objetivo de uno que no lo es.
• La búsqueda primero en anchura es una estrategia sencilla en la que se
expande primero el nodo raíz, a continuación, se expanden todos los sucesores
del nodo raíz, después sus sucesores, etc. En general, se expanden todos los
nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier
nodo del próximo nivel.
• La búsqueda de costo uniforme no se preocupa por el número de pasos que
tiene un camino, pero sí sobre su coste total. Por lo tanto, éste se meterá en un
bucle infinito si expande un nodo que tiene una acción de coste cero que
conduzca de nuevo al mismo estado (por ejemplo, una acción NoOp). Podemos
garantizar completitud si el costo de cada paso es mayor o igual a alguna
constante positiva pequeña.
• La búsqueda primero en profundidad siempre expande el nodo más profundo
en la frontera actual del árbol de búsqueda. La búsqueda procede
inmediatamente al nivel más profundo del árbol de búsqueda, donde los nodos
no tienen ningún sucesor. Cuando esos nodos se expanden, son quitados de la
frontera, así entonces la búsqueda «retrocede» al siguiente nodo más superficial
que todavía tenga sucesores inexplorados.
• Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda
primero en profundidad con un límite de profundidad, El límite de
profundidad resuelve el problema del camino infinito. Lamentablemente,
también introduce una fuente adicional de incompletitud, es decir, el objetivo
está fuera del límite de profundidad. (Esto no es improbable cuando d es
desconocido.) La búsqueda de profundidad limitada también será no óptima si
escogemos un caso que no se encuentre en el rango de búsqueda. La búsqueda
primero en profundidad puede verse como un caso especial de búsqueda de
profundidad limitada con el infinito
.
