Una introducción a la Inteligenca Artificial (IA)



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

4.7. Métodos heurísticos.




4.7.1 Metodos heurísticos que encuentran la mejor solucion

Los métodos vistos hasta ahora devuelven la primer solución que encuentran. Sin embargo, existen problemas para los cuales lo más importante es el costo de la trayectoria encontrada y no el tiempo que se tarden en encontrarla. Es decir, lo que interesa es encontrar la ruta óptima. A continuación se muestran algunos.

A continuación se enlistan algunos de los métodos que encuentran la ruta óptima y que se explicarán posteriormente.


  • Museo Británico

  • Branch & Bound

  • Branch & Bound con subestimados

  • Principio de programación dinámica

  • A*



4.7.2 Procedimiento del museo Británico

El procedimiento del Museo Británico busca todas las trayectorias posibles en el árbol de búsqueda y selecciona la mejor de ellas. Para encontrar todas las trayectorias posibles, tanto el búsqueda en profundidad como la búsqueda en amplitud funcionan con una modificación: la búsqueda continua hasta que se encuentran todas la soluciones.


Este procedimiento es casi inaceptable debido al tamaño de los árboles de búsqueda. Por ejemplo, un árbol con una profundidad de 10 y un factor de ramificación de 10 produciria 10 millones de trayectorias.
El algoritmo de búsqueda para amplitud se enlista a continuación:


  1. Forme una lista con la trayectoria que contiene el nodo inicial.

  2. Hasta que la lista esté vacía

2a. Elimine la primer trayectoria de la lista

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

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

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

2e. Agrege las trayectorias generadas, si existen, al final de la lista


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

  2. Continue extendiendo las trayectorias eliminadas hasta encontrar todas las metas o no haya salida.

  3. Elija la meta que muestre la solución de menor costo heurístico

4.7.3 Procedimiento de Branch and Bound

En este esquema, se mantienen al tanto todas las trayectorias parciales que compiten para su consideración posterior. La mas corta de ellas se extiende un nivel, créandose tantas trayectorias parciales como ramas existan. En seguida, se consideran estas nuevas trayectorias junto con las anteriores restantes: de nuevo se extiende la trayectoria mas corta. Este proceso se repite hasta llegar a la meta a través de una trayectoria. Dado que la trayectoria mas corta es la que siempre se escoge para su extensión, la trayectoria que primero encuentra la meta es probable que sea la óptima.


Para convertir lo probable en cierto, se extienden todas las trayectorias parciales hasta que tengan una longitud igual o mayor que la trayectoria completa más corta. La razón es que el último paso para alcanzar la meta puede ser lo suficientemente largo para hacer que la supuesta solución resulte más larga que una o más trayectorias parciales. Puede ser que sólo un paso pequeño extienda una de las trayectorias parciales al punto solución. Para asegurarse de que esto no suceda, en lugar de terminar al encontrar una trayectoria, termine cuando la trayectoria parcial más corta tenga una longitud mayor que la trayectoria completa más corta.
El algoritmo de búsqueda 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 desde el nodo inicial

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.

  2. Continue extendiendo las trayectorias de menor distancia heurística al nodo inicial que queden sin alcanzar aun la meta, hasta que todas las trayectorias sean mayores o iguales a la mejor meta encontrada.


Ejercicio 4.5.


Utiliza el mapa de la figura 4.2 y encuentra una trayectoria de la ciudad S a la ciudad G utilizando el método del Museo Británico y el Branch & Bound




4.7.4 Principio de programación dinámica

El principio de programación dinámica dice que el mejor camino a través de un lugar intermedio específico es el mejor camino hacia éste desde el lugar de inicio, seguido por el mejor camino desde éste a la meta. No hay necesidad de buscar cualesquiera otras trayectorias hacia, o desde el punto intermedio.

Es decir, si se tienen dos ramas que lleven al mismo nodo, cancelar la rama que contenga el mayor costo heurístico, sin importar cual se encuentre primero.
Algoritmo de búsqueda:


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

  2. Hasta que la lista esté vacía

    1. Elija el camino que represente el menor costo heurístico

    2. Si llegó al estado meta, ir al paso 3

    3. Expanda todas las ramas de ese nodo

    4. Si encuentra un nodo que cuyo costo heurístico sea mayor que el mismo nodo en cualquier rama del árbol expandido, elimínelo.

    5. Si la trayectoria genera un ciclo, elimínela.

  3. Notificar el éxito o fracaso de la rama.

4.7.5 Branch and Bound con subestimados

Un subestimado es una conjetura, algo que suponemos pero que no sabemos a ciencia cierta si es verdad. Supongamos que en el caso de la búsqueda de las ciudades se utilice la conjetura acerca de las distancias restantes, así como de los hechos sobre las distancias ya obtenidos. Después de todo, si la conjetura sobre una distancia restante es buena, entonces esa distancia supuesta, al agregarse a la distancia que se conoce definitivamente y que ya se ha recorrido, deberá ser un buen cálculo de la longitud total de la trayectoria, e(longitud total de trayectoria):


e(longitud total de trayectoria) = d(ya recorrida) + e(distancia restante)
donde d(ya recorrida) es la distancia que ya se recorrió y e(distancia restante) es un cálculo de la distancia que falta.





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


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

enter | registro
    Página principal


subir archivos