Inteligencia Artificial: Universidad Ymca

INGENIERÍA EN SISTEMAS COMPUTACIONALES

UNIVERSIDAD YMCA

ESPÍRITU MENTE CUERPO

MATERIA:

INTELIGENCIA ARTIFICIAL PROFESOR LIC. JAIME ERICK LUNA ENRIQUEZ [email protected] 22/10/2009    

CUATRIMESTRE SEPTIEMBRE-DICIEMBRE DEL 2009

Problemas del Mundo Real

Problemas de búsqueda de rutas. Ej.: Línea Aérea. - ESTADOS: Clave del aeropuerto y fecha y hora actual - ESTADO INICIAL. Clave de Aeropuerto de salida. - FUNCION SUCESOR. Estados que resultan de tomar cualquier vuelo. - TEST OBJETIVO. Encontramos vuelo para la fecha y hora deseada? - COSTO DEL CAMINO. Precio del boleto.

(tarea mex-moldova)

BUSQUEDA DE SOLUCIONES

• La solución a estos problemas se obtiene buscando en  el espacio de estados • Contamos con técnicas de búsqueda que usan un  ARBOL DE BUSQUEDA. • Del estado inicial se va expandiendo el estado actual,  mediante la función sucesor y se obtienen mas estados. • Se continua expandiendo y comprobando (test o.) hasta  que se encuentra la ruta. (fig. 3.6)

Arbol de búsqueda

Función Búsqueda  (Diagramar)

  Medida de rendimiento de la solución 4 formas de evaluar el rendimiento del algoritmo: Completitud.- ¿Se garantiza encontrar una solución? Optimización.- ¿Es la solución óptima? Tiempo.- ¿Cuánto tiempo toma encontrar la solución? Espacio.- ¿Cuánta búsqueda?

memoria

se

necesita

para

la

Complejidad de la búsqueda

En I.A. la complejidad se expresa con 3 cantidades: 1.- FACTOR DE RAMIFICACION. Es el máximo número de sucesores en cualquier nodo. 2.- LA PROFUNDIDADdel nodo objetivo mas superficial. 2.- LA LONGITUD. Es el máximo de nodos en cualquier camino en el espacio de estados

ESTRATEGIAS BUSQUEDA NO INFORMADA

Estudiaremos 5 estrategias de búsqueda englobadas bajo el nombre de “BUSQUEDA NO INFORMADA” o “BUSQUEDA A CIEGAS” Significa que la función solo tiene información del estado definido por el problema y solo pueden generar sucesores hasta llegar al objetivo, cuando la función sabe si un estado no objetivo es mejor que otro, se llama búsqueda informada. (ej, frío, caliente)

Busqueda primero en anchura •

La estrategia de búsqueda primero en anchura se expande primero  el  nodo  raíz,  luego  sus  sucesores,  luego  los  sucesores  de  los  sucesores etc.

•

Es una estrategia primero en entrar, primero en salir (FIFO) la cola  fifo  pone  a  los  sucesores  al  final  de  la  cola  y  los  nodos  más  superficiales se expanden antes que los nodos mas profundos. Ver  figura 3.10

Fig. 3.10

                    Búsqueda primero en anchura •

La búsqueda primero en anchura es una buena solución, para ver si  no se debe considerar esta estrategia debemos tener en cuenta la  cantidad del tiempo y de memoria que usa el algoritmo en el  computador.

•

Afortunadamente contamos con otras estrategias de búsqueda que  requieren menos uso de memoria.

•

BUSQUEDA DE COSTO UNIFORME:

•

La estrategia de la búsqueda de costo uniforme, expande el nodo n,  con el menor costo de camino. Intente probar este algoritmo  intentando encontrar el camino más corto a Bucarest.

Encuentre el camino más corto a Bucarest

BUSQUEDA PRIMERO EN PROFUNDIDAD LA BUSQUEDA PRIMERO EN PROFUNDIDAD Siempre expande el  nodo  más profundo en la frontera actual el arbol de búsqueda, el  progreso y expansión de esta estrategia se pueden observar en la  figura 3.12 Esta estrategia se implementa con un algoritmo de ultimo en entrar  primero en salir (LIFO), también conocida como una pila. Esta estrategia no requiere tanta memoria puesto que una vez que un  nodo se ha expandido completamente, se puede quitar de la  memoria

                                           figura 3.13

Busqueda de profundidad Limitada BUSQUEDA DE PROFUNDIDAD LIMITADA Similar al algoritmo anterior pero se tiene un límite de profundidad, en  ocasiones  cuando  se  conoce  un  problema,  se  puede  conocer  y  establecer el límite de profundidad. Por  ejemplo,  el  mapa  de  Rumanía  tiene  20  ciudades,  entonces  sabemos que tendremos cuando máximo una solución con longitud  19.

Búsqueda Bidireccional. BUSQUEDA BIDIRECCIONAL La idea es ejecutar 2 búsquedas simultaneamente, una hacia adelante  desde  el  test  inicial  y  otra  hacia  atrás  desde  el  test  objetivo,  parando cuando las 2 búsquedas se encuentren. La búsqueda bidireccional se implementa teniendo dos búsquedas que  comprueban  antes  de  ser  expandidos  si  cada  nodo  está  en  la  frontera  del  otro  árbol  de  búsqueda,  cuando  esto  ocurre  se  ha  encontrado la solución. Ver figura 3.16

Esquema de la búsqueda bidireccional

Búsqueda con información  Parcial • La  sección  3.3  asume  que  el  entorno  es  totalmente  observable  y  determinista  y  que  el  agente  conoce  completamente  los  efectos  de  cada acción. • ¿Qué  pasa  cuando  el  conocimiento  de  los  estados  o  acciones  es  incompleto? • DIVERSOS  TIPOS  DE  INCOMPLETITUD  conducen  a  3  distintos  tipos de problemas: • 1.- Problemas sin sensores (el agente no tiene ningún sensor) • 2.-  Problemas  de  contingencia,  si  el  entorno  es  parcialmente  observable  entonces  cada  percepción  define  una  contingencia  que  debe  tratarse,  se  llama  entre  adversarios  si  la  incertidumbre  las  causan las acciones de otro agente. • 3.-  De  exploración.  Cuando  no  se  conocen  ni  los  estados  ni  las  acciones.