matgreco
commented
5 years ago Hola @Pipelao
Lo que hace pathmax es forzar un crecimiento monótono en la función de evaluación.
Siendo v un sucesor de u, y w(u,v) el costo de ir de u a v.
Pathmax se define como f(v) = max(f(u), f(v))
Como una heurística consistente se define como
_h(sg) = 0 (lo que es cierto para cualquier heurística admisible) y h(u) <= h(v) + w(u,v)
Entonces, respetando esta ecuación, podemos decir que:
h(v) <= h(u) - w(u,v)
Si reemplazamos esa definición de h(v), sería lo mismo que
h(v) = max( h(v), h(u) - w(u,v) ) (acá h(v) es el normal y h(u)-w(u,v) está forzando la consistencia. Elijamos el consistente)
Y eso es lo mismo al reemplazarlo en f(v)
f(v) = max( f(v), g(v) + h(u) - w(u,v))
(esa última es la definición de pathmax, ya que f(u) = g(v)-w(u,v) + h(u) )
Hola,
Quiero preguntar de la pregunta 1 de la primera ayudantía, no logro entender qué es lo que hace Pathmax para convertir una heurística admisible en consistente, si pudieran profundizar un poco más en la explicación se lo agradecería.
Saludos.