Cuando se utiliza A * (o cualquier otro algoritmo de búsqueda de mejor ruta), decimos que la heurística utilizada debe ser admisible , es decir, nunca debe sobrestimar la longitud (o movimientos) reales de la ruta de solución.
¿Cómo una heurística admisible garantiza una solución óptima? Preferiblemente estoy buscando una explicación intuitiva.
Si lo desea, puede explicarlo utilizando la heurística de distancia de Manhattan del 8 rompecabezas.
Respuestas:
Si bien la respuesta de Anton es absolutamente perfecta, permítame intentar proporcionar una respuesta alternativa: ser admisible significa que la heurística no sobreestima el esfuerzo para alcanzar la meta, es decir, para todos los n en el espacio de estado (en el 8 rompecabezas, esto significa solo para cualquier permutación de las fichas y el objetivo que está considerando actualmente) donde h ∗ ( n ) es el costo óptimo para alcanzar el objetivo.h(n)≤h∗(n) n h∗(n)
Creo que la respuesta más lógica para ver por qué proporciona soluciones óptimas si h ( n ) es admisible es porque clasifica todos los nodos en ABIERTO en orden ascendente de f ( n ) = g ( n ) + h ( n ) y, también , porque no se detiene al generar el objetivo sino al expandirlo:A∗ h(n) f(n)=g(n)+h(n)
Y esto es, esencialmente, todo lo que encontrará en la prueba original de Nilsson et al.
Espero que esto ayude,
fuente
Si la función heurística no es admisible, entonces podemos tener una estimación que es mayor que el costo real de la ruta de un nodo a un nodo objetivo. Si esta estimación de costo de ruta más alta se encuentra en la ruta de menor costo (que estamos buscando), el algoritmo no la explorará y puede encontrar otra ruta (no menos costosa) hacia la meta.
Mira este sencillo ejemplo.
Deje que y G sean respectivamente los nodos inicial y objetivo . Sea h ( N ) una estimación de la longitud de la ruta desde el nodo N a G , ∀ N en el gráfico. Además, sea c ( N , X i ) la función de costo escalonado desde el nodo N hasta su vecino X i , ∀ N e i = 1 .. m , donde mA G h(N) N G ∀N c(N,Xi) N Xi ∀N i=1..m m es el número de vecinos de (es decir, una función que devuelve el costo del borde entre el nodo N y uno de sus vecinos).N N
Deja que la heurística sea
Esta función heurística no es admisible, porque h ( C ) = 4 > c ( C , G ) = 2H
fuente