Please enable JavaScript.
Coggle requires JavaScript to display documents.
Resolver problemas mediante busqueda (agente resolvente-problemas. (Buscan…
Resolver problemas mediante busqueda
agente resolvente-problemas.
son
Los agentes resolvente-problemas deciden qué hacer para
encontrar secuencias de acciones que conduzcan a los estados deseables.
Buscan soluciones
El primer paso para la resolución de un problema
es la formulación del objetivo
Arbol de busqueda
Se puede utilizar para encontrar una solución en el espacio de estados
La raíz del árbol corresponde al estado inicial
Constantemente se verifica si el estado actual el solucion y sino lo es se expande el estado utilizando la función sucesor y se toma como estado actual alguno de los estados proporcionados por esta funcion
Estos agente suponen que el ambiente es estatico
Tambien Supone que se conoce el estado inicial
Supone que el ambiente es determinista
Problema
Se pueden definir por:
Estado Inicial
Acciones al alcance del agente. Estas pueden cambiar dependiendo del estado actual del agente. Tambien se tiene en cuenta que estas acciones cambiaran el estado actual del agente
Test objetivo, que comprueba si el estado actual del agente es solución al problema. o más bien si es un estado objetivo
Función de costo, asigna un costo numérico a una serie de acciones disponible a un agente, como podría ser un camino a seguir. En otras palabras, la función de costo denota la calidad de una solución
Abstraccion
La utilizamos para mantener el problema lo mas simple posible
Evaluar Soluciones
Se Evaluan por
Optimización
Encuentra la mejor solución posible
Eficacia
Que garantiza encontrar una solución si esta existe
Complejidad Temporal
Cuanto tiempo tarda en encontrar una solución
Complejidad Espacial
Cuanta memoria física utiliza el algoritmo
Complejidad de problema
Se evalua por
Factor de ramificación
Máximo número de sucesores de cualquier nodo
La profundidad del nodo objetivo más superficial
La longitud máxima de cualquier camino en el espacio de estados
Estrategias de búsqueda no informada
Definicion
El algoritmo no cuenta con información adicional de los estados mas allá de la definición del problema
Estrategias
Breadth first search
Se expande primero el nodo actual y después se expanden todos sus sucesore, etc
Uniform cost search
Es óptima cuando no todos los caminos tiene el mismo coste, ya que expande siempre el nodo n con menor coste. Si todos los nodos tienen el mismo coste, no es diferente de BFS
Requiere que todos los costos de todos los nodos sean al menos mayores a cero para que sea eficaz
Depth First Search
Expande siempre los nodos hasta alcanzar su máxima profundidad. después expande el siguiente más superficial que aun tenga sucesores inexplorados
En caso de implementar DFS de manera recursiva este debe tener un límite de profundidad, este también puede tener utilidad si se está tratando con árboles infinitos.