Heurística consistente

En el estudio de los problemas de búsqueda de rutas en inteligencia artificial , se dice que una función heurística es consistente o monótona si su estimación es siempre menor o igual a la distancia estimada desde cualquier vértice vecino hasta el objetivo, más el coste de llegar a ese vecino.

Formalmente, para cada nodo N y cada sucesor P de N , el costo estimado de alcanzar el objetivo desde N no es mayor que el costo del paso para llegar a P más el costo estimado de alcanzar el objetivo desde P. Es decir:

${\displaystyle h(N)\leq c(N,P)+h(P)}$y

${\displaystyle h(G)=0.\,}$

dónde

• h es la función heurística consistente
• N es cualquier nodo en el grafo.
• P es cualquier descendiente de N
• G es cualquier nodo objetivo
• c(N,P) es el costo de llegar al nodo P desde N.

De manera informal, cada nodo i dará una estimación que, teniendo en cuenta el coste para llegar al siguiente nodo, siempre será menor o igual que la estimación en el nodo i+1 .

También es admisible una heurística consistente , es decir, que nunca sobreestime el costo de alcanzar el objetivo ( sin embargo, lo contrario no siempre es cierto). Suponiendo aristas no negativas, esto se puede demostrar fácilmente por inducción . ^{[ 1 ]}

Dejar${\displaystyle h(N_{0})=0}$sea ​​el costo estimado para el nodo objetivo. Esto implica que la condición base es trivialmente verdadera ya que 0 ≤ 0. Dado que la heurística es consistente,${\displaystyle h(N_{i+1})\leq c(N_{i+1},N_{i})+h(N_{i})\leq c(N_{i+1},N_{i})+c(N_{i},N_{i-1})+...+c(N_{1},N_{0})+h(N_{0})}$mediante la expansión de cada término. Los términos dados son iguales al costo real,${\displaystyle \sum _{i=1}^{n}c(N_{i},N_{i-1})}$, por lo que cualquier heurística consistente también es admisible ya que está limitada superiormente por el costo real.

Lo contrario claramente no es cierto, ya que siempre podemos construir una heurística que siempre esté por debajo del costo real, pero que, sin embargo, sea inconsistente, por ejemplo, aumentando la estimación heurística desde el nodo más lejano a medida que nos acercamos y, cuando la estimación${\displaystyle h(N_{i})}$se convierte, como mucho, en el costo real${\displaystyle h^{*}(N_{i})}$, hacemos${\displaystyle h(N_{i-1})=h(N_{i})-c(N_{i},N_{i-1})}$.

Las heurísticas consistentes se denominan monótonas porque el costo final estimado de una solución parcial,${\displaystyle f(N_{j})=g(N_{j})+h(N_{j})}$es monótonamente no decreciente a lo largo de cualquier camino, donde${\displaystyle g(N_{j})=\sum _{i=2}^{j}c(N_{i-1},N_{i})}$es el costo de la mejor ruta desde el nodo de inicio${\displaystyle N_{1}}$a${\displaystyle N_{j}}$Es necesario y suficiente que una heurística cumpla la desigualdad triangular para ser consistente. ^{[ 2 ]}

La justificación de${\displaystyle f(N)}$Para que sea monótonamente no decreciente bajo una heurística consistente, se debe decir lo siguiente:

Suponer${\displaystyle P}$es un sucesor de${\displaystyle N}$, entonces ${\displaystyle g(P)=g(N)+c(N,a,P)}$para alguna acción${\displaystyle a}$de${\displaystyle N}$a${\displaystyle P}$. Entonces tenemos eso

${\displaystyle f(P)=g(P)+h(P)=g(N)+c(N,a,P)+h(P)\geq g(N)+h(N)=f(N)}$

por eso${\displaystyle f(P)\geq f(N)}$.

En el algoritmo de búsqueda A* , usar una heurística consistente significa que una vez que se expande un nodo, el costo por el cual se llegó a él es el más bajo posible, bajo las mismas condiciones que requiere el algoritmo de Dijkstra para resolver el problema del camino más corto (sin aristas de costo negativo). De hecho, si se le da al grafo de búsqueda un costo${\displaystyle c'(N,P)=c(N,P)+h(P)-h(N)}$para una consistencia${\displaystyle h}$, entonces A* es equivalente a la búsqueda primero en amplitud en ese grafo utilizando el algoritmo de Dijkstra. ^{[ 3 ]}

Con una no decreciente${\displaystyle f(N)}$bajo heurísticas consistentes, se puede demostrar que A* alcanza la optimalidad con comprobación de ciclos, es decir, cuando A* expande un nodo${\displaystyle n}$, el camino óptimo hacia${\displaystyle n}$ya se ha encontrado. Supongamos por contradicción que cuando A* se expande${\displaystyle n}$, no se ha encontrado el camino óptimo. Entonces, por la propiedad de separación del grafo, debe existir otro nodo${\displaystyle n'}$en el camino óptimo hacia${\displaystyle n}$en la frontera. Desde${\displaystyle n}$fue seleccionado para la expansión en lugar de${\displaystyle n'}$, esto significaría que${\displaystyle f(n)<f(n')}$Pero dado que los valores f son monótonamente no decrecientes a lo largo de cualquier trayectoria bajo la función heurística consistente${\displaystyle f}$, sabemos que${\displaystyle f(n)\geq f(n')}$desde${\displaystyle n'}$está en camino a${\displaystyle n}$Esto es una contradicción, lo que significa que${\displaystyle n'}$debería haber sido seleccionado para expansión primero en lugar de${\displaystyle n}$. ^{[ 4 ]}

En el caso excepcional de que una heurística admisible no sea consistente, un nodo necesitará una expansión repetida cada vez que se logre un nuevo mejor costo (hasta el momento) para él.

Si la heurística dada${\displaystyle h}$es admisible pero no consistente, se puede forzar artificialmente que los valores heurísticos a lo largo de un camino sean monótonamente no decrecientes mediante el uso

${\displaystyle h'(P)\gets \max(h(P),h'(N)-c(N,P))}$

como el valor heurístico para${\displaystyle P}$en lugar de${\displaystyle h(P)}$, dónde${\displaystyle N}$es el nodo inmediatamente anterior${\displaystyle P}$en el camino y${\displaystyle h'(start)=h(start)}$Esta idea se debe a László Mérō ^{[ 5 ]} y ahora se conoce como pathmax. Contrariamente a la creencia popular, pathmax no convierte una heurística admisible en una heurística consistente. Por ejemplo, si A* utiliza pathmax y una heurística que es admisible pero no consistente, no se garantiza que tenga una ruta óptima a un nodo cuando se expande por primera vez. ^{[ 6 ]}

• Heurística admisible