Una introducción a la Inteligenca Artificial (IA)


UNIDAD IV TEORIA DE BÚSQUEDA HEURÍSTICA Y TEORIA DE JUEGOS



Descargar 2.01 Mb.
Página19/29
Fecha de conversión20.03.2018
Tamaño2.01 Mb.
Vistas516
Descargas0
1   ...   15   16   17   18   19   20   21   22   ...   29

UNIDAD IV TEORIA DE BÚSQUEDA HEURÍSTICA Y TEORIA DE JUEGOS




4.1 Introduccion

Porqué los métodos heurísticos? Por que aunque en un principio se pensó que toda tarea de búsqueda podía ser completada por un computador sin mas que realizar una exploración de todos los caminos que llevan a una solución y una posterior selección del mejor de tales caminos, mas tarde se comprobó que aunque esta suposición era cierta, no era eficaz debido a la explosión combinatoria que aparece en este tipo de problemas.


Los procesos de búsqueda son muy tardados debido a la gran cantidad de combinaciones que se tienen que realizar.

4.2 Búsqueda Heurística


El conocimiento dependiente del dominio puede ayudar a dirigir el proceso de búsqueda de manera que sean exploraras en primer lugar aquellas trayectorias que parecen más prometedoras a la hora de conducir a un estado solución. La búsqueda inspirada en el razonamiento anterior se denomina heurística.
La eficiencia en la búsqueda puede mejorar si existe una forma de ordenar las selecciones de modo que las más prometedoras se exploren primero. Una forma de ordenarlas es incorporando heurísticas.
En IA se considera la heurística como una técnica que aumenta la eficiencia en un proceso de búsqueda.
Metodología: la principal diferencia entre este tipo de búsqueda respecto a la que no emplea información del dominio (búsqueda exhaustiva) es que ahora a cada nodo se le va a poder asociar un valor que dará idea de lo cerca que se encuentra de un nodo meta. Evidentemente ese valor no será mas que una estimación de la distancia real a la meta.

4.3 Ventajas de los métodos:


  1. Los métodos heurísticos no garantizan hallar la solución optima a un problema, pero permiten, de una manera más eficiente desde el punto de vista computacional, aproximarse a tal solución.

  2. Normalmente no se necesita una solución óptima, con frecuencia una buena aproximación es adecuada.

  3. El intentar comprender porqué funciona una heurística sirve para comprender mejor el problema



4.4 Desventajas de los métodos:


  1. Probablemente no considere la mejor ruta. Al hablar de heurística estamos hablando de algo probable y no de algo cien por ciento seguro.

  2. Es difícil encontrar la heurística adecuada. Las heurísticas se tienen que definir dependiendo del problema que estamos tratando de resolver, a veces los problemas son tan complejos que es difícil encontrar la heurística adecuada.


4.5 Funciones Heurísticas.


El conocimiento heurístico se puede incorporar en las mismas reglas u operadores, o como una función heurística que evalúa los estados individuales del problema y determina su grado de deseabilidad. La función heurística depende del problema y de la creatividad del implementador; por lo tanto, un mismo problema puede tener varias funciones heurísticas.
Ejemplos:

Problemas

Posibles funciones heurísticas


El agente viajero

  1. La suma de las distancias recorridas

  2. La distancia en línea recta del nodo inicial al nodo meta

Juego del gato

La función de evaluación sumaría 1 por cada fila en la que podamos ganar y ya se tenga una tirada y 2 por cada fila en la que podamos ganar y que se tengan dos tiradas

El problema del 8-puzzle

  1. La cantidad de placas que están en lugar incorrecto

  2. La suma de las distancias que separa a las placas de sus posiciones meta

A continuación se describen diferentes tipos de algoritmos basados en este tipo de búsqueda:




4.6 Búsqueda Primero el Mejor


En la búsqueda primero el mejor, la búsqueda se realiza a partir del mejor nodo abierto que se tiene hasta ese punto, sin importar dónde esté ese nodo en al árbol parcialmente desarrollado.
El algoritmo de búsqueda primero el mejor se enlista a continuación:


  1. Forme una lista con una trayectoria que contenga el nodo inicial.

  2. Hasta que la lista esté vacía

2a. Eliga trayectoria de menor distancia heurística

2b. Si la trayectoria llega al nodo meta vaya al paso 3

2c. Si no, genere nuevas trayectorias extendiendo la trayectoria elegida

2d. Si alguna trayectoria generada contiene ciclos, elimínela



2e. Agrege las trayectorias generadas, si existen, a la lista

  1. Si se encontró el nodo meta notificar éxito, si no notificar fracaso.


Ejercicio 4.1.



Utiliza el mapa de la figura 4.1 y considera que la función heurística es la distancia en línea recta de cada ciudad a la ciudad meta (G), como lo muestra la siguiente tabla. Aplica el algoritmo de primero el mejor.








Figura 4.1 Mapa de carreteras de una ciudad a otra


Ciudad

Distancia en línea recta a G

S

11.0

A

10.4

B

6.7

C

4.0

D

8.9

E

6.9

F

3.0


Tabla 4.1 Distancia de cada ciudad a la ciudad meta.

Enfoque distancia de nodo a nodo



4

4


3

4

3


4


4


2

3


Figura 4.2 Mapa con distancias entre ciudades



Lista

Trayectoria Elegida

Trayectorias generadas

[(S)]

(S)

(S,A); (S,D)

[(S,A); (S,D)]

(S,A)

(S,A,S);(S,A,B),(S,A,D)

[(S,A,B); (S,A,D),(S,D)]

(S,A,D)

(S,A,D,S); (S,A,D,A), (S,A,D,E);

[(S,A,B);(S,A,D,E);(S,D) ]

(S,A,D,E)

(S,A,D,E,F);(S,A,D,E,B); (S,A,D,E,D)

[(S,A,B); (S,A,D,E,B)

(S,A,D,E,F)(S,D)]



(S,A,D,E,F)

(S,A,D,E,F,G), (S,A,D,E,F,E)

[(S,A,B); (S,A,D,E,B)

(S,A,D,E,F,G)(S,D)]



(S,A,D,E,F,G)








Compartir con tus amigos:
1   ...   15   16   17   18   19   20   21   22   ...   29


La base de datos está protegida por derechos de autor ©psicolog.org 2019
enviar mensaje

enter | registro
    Página principal


subir archivos