matgreco
commented
5 years ago Hola. La demostación es la siguiente.
Siendo h(S0) el costo óptimo de S0 al objetivo, Sg un estado objetivo y S la solución óptima.
Suponga que wA* extrae Sg de la open. Como la búsqueda es creciente y la heurística admisible (por lo tanto h(Sg) = 0)
g(Sg) > w h(S0)
Por lo tanto
f(Sg) > w h(S0)
Se sabe que existe un S* en OPEN tal que
g(S) = g(S*)
Como wA prefiere a Sg en vez de S, se puede decir que
f(Sg) <= f(S) = g(S) + wh(S)
como w >= 1
f(Sg) <= w( g(S) + h(S) ) (se mantiene la desigualdad) f(Sg) <= w(C(S))
Hola, hemos estado harto rato pegados analizando este problema, alguien tiene una demostración de porque wA* encuentra soluciones a lo más w veces el optimo?
Gracias!