Una introducción a la Inteligenca Artificial (IA)



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

4.8 A*

El procedimiento A* es una búsqueda de ramificación y cota con una estimación de la distancia restante, en continuación con el principio de programación dinámica. Si la estimación de la distancia restante es un límite inferior de la distancia real, entonces el procedimiento A* produce soluciones óptimas.



La función heurística para este metodo es:
f(n)=g(n)+h(n)
Donde:

g(n): coste real del mejor camino encontrado en un determinado momento desde la raíz hasta n.

h(n): Estimación del coste del camino óptimo desde n a una meta.

Algoritmo del Procedimiento A*

  1. Crear una lista de nodos llamada ABIERTA y asignarle el nodo raíz, que representa el estado inicial del problema planteado. Llamar a este elemento r y asignarle g(r)=0.

  2. Crear una lista de nodos llamada CERRADA que inicialmente estará vacía.

  3. Hasta que se encuentre una meta o se devuelva falla, realizar las siguientes acciones:

    1. Si ABIERTA esta vacía, terminar con fallo; en caso contrario continuar.

    2. Eliminar el nodo de ABIERTA que tenga un valor mínimo de f; llamar a este nodo m e introducirlo en la lista CERRADA.

    3. Si m es meta, abandonar el proceso iterativo señalado en 3, devolviendo el camino de la solución que se obtiene recorriendo los punteros de sus antepasados (creados en 3.5)

    4. En caso contrario, expandir m generando todos sus sucesores.

    5. Para cada sucesor de n’ de m:

    1. Crear un puntero de n’ a m.

    2. Calcular g(n’)=g(m)+c(m,n’), tal que c(a,b): coste de pasar de a a b.

    3. Si n’ esta en ABIERTA, llamar n al nodo encontrado en dicha lista, añadirlo a los sucesores de m y realizar (3.1)

(3.1) Si g(n’)n a m y cambiar el camino de menor coste encontrado a n desde la raíz, g(n)=g(n’) y f(n)=g(n’)+h(n).


    1. Si n’ no cumple (3), comprobar si esta en CERRADA; llamar n al nodo encontrado en dicha lista y realizar las siguientes acciones.

(4.1 ) Si (3.1) no se cumple, abandonar (4); en caso contrario propagar el nuevo menor coste g(n’) (por lo que también se actualizaran los valores de f correspondientes) a sus descendientes (que llamaremos ni, tal que i=1,2,.., que siendo sus costes anteriores g(ni)), realizando un recorrido en profundidad de estos, empezando en n’ y teniendo en cuenta las siguientes consideraciones:

(4.2) Para los nodos descendientes ni cuyo puntero (que debe apuntar siempre al mejor predecesor hasta ese momento) conduzca hacia el nodo n’, actualizar g(ni)=g(ni’) y f(ni)=g(ni’)+h(ni) y seguir el recorrido hasta que se encuentre un ni que no tenga más sucesores calculados o se llegue a un nodo en que ya ocurra que g(ni)=g(ni’), en cuyo caso se habría producido un ciclo y también habría que terminar la propagación.




    1. Si n’ no esta en ABIERTA o en CERRADA, calcular h(n’) y f(n’)=g(n’)+h(n’), introducirlo en ABIERTA y añadirlo a la lista de sucesores de m.


Ejercicio 4.6.


Utiliza el mapa de la figura 4.2 y encuentra una trayectoria de la ciudad S a la ciudad G utilizando el método de A*





Comparaciones de los diferentes métodos de búsqueda.


  • El procedimiento del Museo Británico es bueno sólo cuando el árbol de búsqueda es pequeño.

  • El procedimiento de Branch & Bound es eficaz cuando el árbol es grande y las malas trayectorias se identifican rápidamente.

  • El procedimiento de Branch & Bound con uso de subestimados es eficaz cuando existe una buena estimación de límite inferior de la distancia que resta hacia la meta

  • La programación dinámica es conveniente cuando muchas trayectorias convergen en el mismo lugar

  • El procedimiento A* es eficaz cuando la búsqueda de ramificación y cota con conjetura y la programación dinámica son buenas.





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


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

enter | registro
    Página principal


subir archivos