Presentacion - Inteligencia Artificial - Tema 3.pdf

Dr. Cristian I. Pinzn

Dr. Cristian Pinzn

Inteligencia Artificial

Dr. Cristian Pinzn

CONTENIDO

1. Agente Resolventes-Problemas

2. Bsqueda de Soluciones

3. Estrategias de Bsqueda No

Informada

4. Problemas Propuestos

Dr. Cristian Pinzn


Asumimos que los agentes Inteligentes deben maximizar su medida de rendimiento. Para ello, el agente debe elegir un objetivo y debe tratar de satisfacerlo.

Los objetivos ayudan a organizar el comportamiento del agente limitando las metas que intenta alcanzar el agente.

AGENTES RESOLVENTES -PROBLEMAS

Dr. Cristian Pinzn


Pasos para la Solucin de un Problema:

Formulacin del Objetivo Un objetivo no es ms que un conjunto de estados del mundo, siendo estos estados los que exactamente satisfacen el objetivo. La tarea es encontrar qu secuencias de acciones permite obtener un estado objetivo.


Dr. Cristian Pinzn


Pasos para la Solucin de un Problema:

Formulacin del Problema Es el proceso de decidir qu acciones y estados tenemos que considerar. Cuando se eliminan detalles de una representacin, se realiza una abstraccin.


Dr. Cristian Pinzn


Bsqueda:

Se realiza cuando el 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.


Dr. Cristian Pinzn


Solucin:

Es el resultado del algoritmo de bsqueda, de la forma de secuencia de acciones, dado un problema como entrada.

Ejecucin:

Una vez encontrada una solucin, se procede a ejecutar las acciones recomendadas.


Dr. Cristian Pinzn


PROBLEMA

Un problema queda definido por los siguientes

componentes:

Estado Inicial: Donde comienza el agente. Funcin Sucesor: Devuelve el siguiente estado que

puede alcanzarse desde el estado actual, aplicando la

accin correspondiente.

Espacio de Estados: Todos los estados alcanzables desde el estado inicial.

Camino: Una secuencia de estados conectados por una secuencia de acciones.


Dr. Cristian Pinzn


PROBLEMA

Un problema queda definido por los siguientes

componentes:

Test Objetivo: Determina si un estado es un estado objetivo.

Costo del Camino: Una funcin que asigna un costo numrico a cada camino.

Solucin: Es el camino desde el estado inicial a un estado objetivo. La calidad de la solucin se mide por la

funcin de costo del camino, y una solucin ptima

tiene el costo ms pequeo del camino entre todas las

soluciones.


Dr. Cristian Pinzn


rbol de Bsqueda: El Espacio de estados. Nodo de Bsqueda: Es el nodo raz del rbol

de bsqueda, que tambin corresponde con el

estado inicial.

Expandir y Generar: Es el proceso de evaluar otros estados expandiendo el estado actual,

mediante la funcin sucesor. Generar implica

crear un nuevo conjunto de estados.

BSQUEDA DE SOLUCIONES

Dr. Cristian Pinzn


Estrategia de Bsqueda: Es el algoritmo utilizado en la bsqueda en rboles.

Nodo Hoja: Nodo sin sucesores en el rbol. Cola: Estructura de datos donde el primer

elemento en entrar ser el primer elemento en

salir.


Dr. Cristian Pinzn


RENDIMIENTO DE LA RESOLUCIN DEL PROBLEMA

La salida del algoritmo de resolucin del

problemas puede generar:

Fallo: No se encontr el estado deseado. Solucin: Se alcanz el estado deseado.


Dr. Cristian Pinzn


RENDIMIENTO DE LA RESOLUCIN DEL PROBLEMA Para evaluar el rendimiento de un algoritmo se tiene que

considerar:

Completitud: Garantizar que se encontrar una solucin siempre y cuando exista.

Optimizacin: Encontrar la estrategia de solucin optima.

Complejidad en tiempo: Tiempo que tardar en encontrar una solucin.

Complejidad en Espacio: Memoria requerida para el funcionamiento de la bsqueda.


Dr. Cristian Pinzn


RENDIMIENTO DE LA RESOLUCIN DEL PROBLEMA Para valorar la eficacia de un algoritmo de

bsqueda, se tiene que considerar:

El costo de la bsqueda: complejidad en tiempo.

El coste total: Costo de la bsqueda + costo del camino solucin encontrado.


Dr. Cristian Pinzn


ESTRATEGIAS DE BSQUEDA NO INFORMADA

Son estrategias de bsqueda que no tienen informacin adicional acerca de la estados ms all de la que proporciona la definicin del problema.


Dr. Cristian Pinzn


ALGORITMO

BSQUEDA PRIMERO EN ANCHURA

Dr. Cristian Pinzn


BUSQUEDA PRIMERO EN ANCHURA Primero se expande el nodo raz, a continuacin se expanden todos los sucesores del nodo raz, despus sus sucesores y as sucesivamente. En general se expanden todos los nodos a una profundidad en el rbol de bsqueda antes de expandir cualquier nodo del prximo nivel.


Dr. Cristian Pinzn


BUSQUEDA PRIMERO EN ANCHURA


Dr. Cristian Pinzn



Dr. Cristian Pinzn



Ventajas:

La bsqueda primero en anchura no queda atrapada explorando callejones sin salida.

Si existe una solucin, la bsqueda primero en anchura garantiza que encontrar. Adems si existen mltiples

soluciones, se encuentra la solucin mnima ( es decir, la

que requiere el mnimo nmero de pasos)


Dr. Cristian Pinzn



Desventajas:

Hay que considerar la cantidad de tiempo y memoria que se utiliza para completar una

bsqueda. En aquellos espacios de estados

donde cada estado tiene x sucesores y as

sucesivamente. El problema se puede hace

inmanejable desde el punto de vista de consumo

de memoria y tiempo requerido.


Dr. Cristian Pinzn


BUSQUEDA PRIMERO EN ANCHURA Desventajas:


Dr. Cristian Pinzn




Dr. Cristian Pinzn



Nodos Generados Nodos Expandidos

X X

XXX X

XXXX X

.

XXXX X

Se plantea un rbol donde los dos nicos nodos metas son B y L, y A es el nodo inicial, determnese en qu orden se visitaran los nodos, diferenciando los nodos generados y los

nodos expandidos, de acuerdo al algoritmo en Amplitud.


Dr. Cristian Pinzn


ALGORITMO

BSQUEDA PRIMERO EN PROFUNDIDAD

Dr. Cristian Pinzn


BUSQUEDA PRIMERO EN PROFUNDIDAD

Siempre se expande el nodo ms profundo en la frontera actual del rbol de bsqueda. La bsqueda procede inmediatamente al nivel ms profundo del rbol de bsqueda, donde los nodos no tienen ningn sucesor. Cuando esos nodos se expanden, son quitados de la frontera, as entonces la bsqueda retrocede al siguiente nodo ms superficial que todava tenga sucesores inexplorados.


Dr. Cristian Pinzn



Esta estrategia puede implementarse por la BSQUEDA-RBOLES con una cola ltimo en entrar primero en salir (LIFO), tambin conocida como una pila. Este algoritmo presenta unos requisitos muy modestos de memoria. Necesita almacenar slo un camino desde la raz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino.


Dr. Cristian Pinzn


ESTRATEGIAS DE BSQUEDA NO INFORMADA - PROFUNDIDAD


Dr. Cristian Pinzn




Dr. Cristian Pinzn



Ventajas:

Necesita menos memoria. Si se tiene suerte, la bsqueda primero

en profundidad puede encontrar una

solucin sin tener que examinar gran

parte del espacio de estados.


Dr. Cristian Pinzn



Desventajas:

Su principal desventaja es que puede hacer una eleccin equivocada y obtener un camino muy

largo (o infinito) aun cuando una eleccin diferente

llevara a una solucin cerca de la raz del rbol

de bsqueda.


Dr. Cristian Pinzn




Dr. Cristian Pinzn



Nodos Generados Nodos Expandidos

X X

XXX X

XXXX X

.

XXXX X

Se plantea un rbol donde los dos nicos nodos metas son B y L, y A es el nodo inicial, determnese en qu orden se visitaran los nodos, diferenciando los nodos generados y los

nodos expandidos, de acuerdo al algoritmo en Profundidad.


Dr. Cristian Pinzn


PROBLEMAS PROPUESTOS ALGORITMOS DE BSQUEDA NO

INFORMADA

Dr. Cristian Pinzn


Preguntas por Resolver

1. Defina con sus propias palabras los

siguientes trminos: estado, espacio de

estados, rbol de bsqueda, nodo de

bsqueda, objetivo, accin, funcin sucesor, y

factor de ramificacin.

2. Explique por qu la formulacin del

problema debe seguir a la formulacin del

objetivo.

Dr. Cristian Pinzn


Problema N1: Anchura y Profundidad

Dr. Cristian Pinzn



Documents

Presentacion - Inteligencia Artificial - Tema 3.pdf