BÚSQUEDA HEURÍSTICA
A*
Prueba de escritorio
Algoritmo:
1.
Lista abierta <-Nodo_raiz
2.
Si open vacío, fallo, Stop.
Si no n<- extraer-mínimo-lista abierta
3.Si n es objetivo, éxito, stop
Si no añadir n a lista cerrada y generar
sucesores de n (expansión de n)
4.Para cada sucesor de n hacer
4.1. Si n esta en lista cerrada, ignorar n.
4.2. Si n esta en lista abierta, re
etiquetar con el camino mas corto.
4.3. Si n no está en lista abierta ni en
lista cerrada, añadir n a lista abierta.
4.4. Continuar en punto 2.
Problema:
Ir del punto inicial (OR) al punto final(DE).
0 1
2 3 4
OR
|
-----
|
|||
-----
|
||||
-----
|
-----
|
-----
|
||
-----
|
||||
-----
|
DE
|
-----
|
OR = punto inicial
DE= punto final
----- = obstáculo
Calculo de g(n) h(n) y f(n).
G(n)=costo de un nodo a otro es
de 1.
H(n)=raíz cuadrada de (X1-X2)^2+(
Y1-Y2)^2
F(n)=G(n)+F(n).
Árbol Generado
En el siguiente cuadro se muestra
el paso a paso de la prueba de escritorio del algoritmo A*; la columna Open, va
hacer referencia a los nodos que se encuentran en esta lista en cada iteración,
Closed se encuentran los nodos añadidos a esta lista tras cada iteración, N será
el nodo seleccionado en cada iteración y S son los nodos generados a partir de
N.
Cada nodo
esta representado por sus coordenadas.
Los nodos
marcados en rojo, son los q fueron eliminados o descartados.
Open
|
Closed
|
N
|
S
|
(0,2)
|
(0,2)
|
(0,2)
|
(0,1), (0,3),(1,2)
|
(0,1),(0,3),(1,2)
|
(1,2)
|
(1,2)
|
(0,2),(2,2),(1,3)
|
(2,2),(1,3)
|
(2,2)
|
(2,2)
|
(1,2)
|
(0,0)
|
(0,1)
|
(0,1)
|
(0,0)
|
(1,4), (1,0)
|
(0,3)
|
(0,3)
|
(0,2), (1,3)
|
(2,4)
|
(1,3)
|
(1,3)
|
(1,4), (1,2),(0,3)
|
(3,4)
|
(0,0)
|
(0,0)
|
(1,0),(0,1)
|
(3,3)
|
(1,0)
|
(1,0)
|
(0,0)
|
(4,3)
|
(1,4)
|
(1,4)
|
(2,4), (1.3)
|
(4,2)
|
(3,4)
|
(2,4)
|
(3,4),(1,4)
|
(4,1)
|
(4,3)
|
(3,4)
|
(3,3),(3,4)
|
(4,2)
|
(4,3)
|
(4,3),(3,4)
|
|
(4,2)
|
(4,2),(3,3)
|
||
(4,1)
|
(4,1),(4,3)
|
No hay comentarios:
Publicar un comentario