search

IIC2613 / Syllabus-2019-2

16 stars 3 forks source link

Poda en restarting wA* #14

Closed FloValdes closed 4 years ago

FloValdes commented 4 years ago

Hola, no entiendo a qué se le tiene que hacer la poda en RWA. Según entiendo, la lista open no se mantiene desde la búsqueda anterior, así que no se le hace la poda a ella como en AWA.

Gracias.

Pipelao commented 4 years ago

Hola @FloValdes

Lo que entiendo yo es que como reinicias weighted A*, tienes nuevamente la lista open, y cada vez que extraes de la lista open, comparas con la solución ya encontrada y si resulta ser menor a la solución, sigues expandiendo, en caso contrario no expandes porque tienes una solución de menor costo.

matgreco commented 4 years ago

Hola @FloValdes y @Pipelao

RWA*, en su primera iteración, encuentra una solución que supongamos tiene costo 100.

En la iteración siguiente, al momento de expandir un nodo, si el nodo generado tiene un costo g(s)+h(s) > 100, no lo genera (lo poda). De esa manera, la open queda mas pequeña.

Entonces, la poda se hace al momento de generar un nodo.

Saludos!