Una función heurística es ...
- Consistente si el costo estimado del nodo al objetivo no es mayor que el costo del paso para su sucesor n ' más el costo estimado del sucesor al objetivo.
- Admisible si nunca sobreestima el costo real para el estado objetivo.
El libro de texto para mi curso de Inteligencia Artificial establece que la consistencia es más fuerte que la admisibilidad pero no lo prueba, y estoy teniendo problemas para encontrar una explicación matemática.
algorithms
shortest-path
heuristics
usuario58348
fuente
fuente
Respuestas:
Para probar la afirmación en su pregunta, demostremos que la coherencia implica admisibilidad, mientras que lo contrario no es necesariamente cierto. Esto haría que la consistencia sea una condición más fuerte que esta última.
La consistencia implica admisibilidad:
La prueba procede por inducción:
La admisibilidad no implica necesariamente coherencia:
Para esto, un simple ejemplo es suficiente. Considere un gráfico que consiste en una sola ruta con 10 nodos: , donde el objetivo es . Supongamos wlog que todos los costos de borde son iguales a 1. Obviamente , y hagamos que , y . Claramente, la función heurística es admisible :⟨n0,n1,n2,...,n9⟩ n9 h∗(n0)=9 h(n0)=8 h(ni)=1,1≤i<9 h(n9)=0
Sin embargo, no es consistente y .h(n) h(n0)=8>c(n0,n1)+h(n1)=1+1=2
Espero que esto ayude,
fuente