Resolventes-Problema

INTRODUCCIÓN

 En este  capítulo   hablaremos de los agentes   que  están basados  en resolver problemas  en donde   veremos que  un agente  puede  realizar búsqueda de  secuencias de acciones   donde  alcanzara sus  objetivos, ya que  conoceremos  de lo agentes basados en objetivos, hay que  saber que los agentes  resolvente de problemas  ellos toman decisiones de que hacer  para encontrar secuencias  de acciones que  los   conlleve  a un estado  deseables

Agentes resolventes-problemas

Se supone que los agentes inteligentes deben maximizar su medida de rendimiento. Como mencionamos en el Los agentes resolventes-problemas deciden que hacer para encontrar secuencias de acciones que conduzcan a los estados deseables.

Los algoritmos son no informados, en el sentido que no da información sobre el problema salvo su definición. Los algoritmos de búsqueda informada, los que tengan cierta idea de dónde buscar las soluciones.

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.

Problemas y soluciones bien definidos

Puede definirse, formalmente, por cuatro componentes importantes:

Ø  El estado inicial en el que comienza el agente.

ü  Acciones.- son disponibles por el agente

ü  Espacio de Estado.-  trata  del   conjunto de todos los estados alcanzables desde el estado inicial.

ü  El test objetivo, el cual determina si un estado es un estado objetivo.

ü  Costo del Camino que asigna un costo numérico a cada camino.

ü  El costo individual de una acción a que va desde un estado xal estado y se denota por cix,a,y).Los costos individuales para Rumania se muestran en la Figura 3.2 como las distancias de las carreteras.

Una solución de 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, y una solución óptima tiene el costo más pequeño del camino entre todas las soluciones.

Formular los problemas

En la sección anterior propusimos una formulación del problema de ir a Bucarest en términos de estado inicial, función sucesor, test objetivo y costo del camino. Esta formulación parece razonable, a pesar de omitir muchos aspectos del mundo real.

o   Estados: la descripción de un estado especifica la localización de cada una de las ocho fichas y el blanco en cada uno de los nueve cuadrados.

o   Estado inicial: cualquier estado puede ser un estado inicial. Nótese que cualquier objetivo puede alcanzarse desde exactamente la mitad de los estados iniciales posibles

•         Fundón sucesor: esta genera los estados legales que resultan de aplicar las cuatro acciones (mover el blanco a la Izquierda, Derecha, Arriba y Abajo).

•         Test objetivo: comprueba si el estado coincide con la configuración objetivo que se muestra en la Figura 3.4. (son posibles otras configuraciones objetivo).

•         Costo del camino: el costo de cada paso del camino tiene valor 1, así que el costo del camino es el número de pasos.

Busqueda de soluciones

ARBOL DE BUSQUEDA explicito generado por el estado inicial y la función sucesor, definiendo así el espacio de estados. La raíz del árbol de búsqueda es el nodo de búsqueda que corresponde al estado inicial, En{Arad).

Es importante distinguir entre el espacio de estados y el arbol de busqueda.

Una estructura de datos con cinco componentes:

ü  Estado: el estado del espacio  de estados que  corresponden con el nodo

ü  Nodo padre: el nodo en el árbol de búsqueda que ha generado este nodo

ü  Acción: la acción que realiza 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;

ü  Profundidad: el número  de paso  a lo largo del camino desde el estado inicial

Imagen

Medir el rendimiento de la resolución del problema

ü  Completitud: está garantizado que el algoritmo encuentre una solución  cuando esta exista

ü  Optimización: encuentra la estrategia de solución óptima

ü  Complejidad del tiempo: cuando tarda en encontrar una solución

ü  Complejidad en espacio: cuando se necesita para funcionamiento de búsqueda

Estrategias de búsqueda no informada

Esta sección trata cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda no informada El termino significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema.

Busqueda 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.

Búsqueda de costo uniforme

La búsqueda primero en anchura es óptima cuando todos los costos son iguales, porque siempre expande el nodo no expandido más superficial. Con una extensión sencilla, podemos encontrar un algoritmo que es óptimo con cualquier función costo. En vez de expandir el nodo más superficial, la búsqueda de costo uniforme expande el nodo n con el camino de costo más pequeño. Notemos que si todos los costos son iguales, es idéntico a la búsqueda primero en anchura.

Busqueda primero en profundidad

Siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda. El progreso de la búsqueda se ilustra en 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.

Búsqueda de profundidad limitada

Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en profundidad con un límite de profundidad t predeterminado. Es decir, los nodos a profundidad i se tratan como si no tuvieran ningún sucesor.

Búsqueda primero en profundidad con profundidad iterativo

Es una estrategia general, usada a menudo en combinación con la búsqueda primero en profundidad, la cual encuentra el mejor límite de profundidad hasta que encontramos un objetivo.

Búsqueda bidireccional

La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro mucho menor

Conclusión

En este capítulo concluimos  que los  agentes resolventes-problemas  son agentes basados en objetivo aprendienendo a utilizar  los métodos de busquedad para cada  problema, llegando a  una buena solución bien definidos y llegando al objetivo planteado del agente, utilizando  objetivos el cual se encarga de organizar los problemas.

BIBLIOGRAFÍA

Holger, B. Rubén, O. 2012. Fundamentos de Inteligencia Artificial.Ing. Sup. en Informática, 3º. (En línea). PE. Consultado, 15  de oct.2014. Disponible en:http://www.ia.urjc.es/grupo/docencia/fia/material/temario_FIA_tema1.pdfRussell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España