Posterior a buscar en diversos repositorios y páginas al final nos hemos encontrado la solución que te enseñamos más adelante.
Solución:
Las heurísticas admisibles no deben sobreestimar el número de movimientos para resolver este problema. Dado que solo puede mover los bloques 1 a la vez y en solo una de las 4 direcciones, el escenario óptimo para cada bloque es que tenga un camino claro y sin obstrucciones hacia su estado objetivo. Este es un MD de 1.
El resto de los estados para un par de bloques es subóptimo, lo que significa que voluntad toma más movimientos que el MD para colocar el bloque en el lugar correcto. Así, la heurística nunca sobreestima y es admisible.
Eliminaré cuando alguien publique una versión correcta y formal de esto.
Prueba formal: Por definición de h, h(s∗) = 0, si s∗ es el estado objetivo. Asumir como prueba por contradicción que C∗ < h(s0) for some initial state s0. Note that, since each action can move only one tile, performing an action can at most reduce h by one. Since the goal can be reached in C∗ actions, we have h(s∗) ≥ h(s0) − C∗ > 0, lo que nos lleva a una contradicción ya que h(s∗) debería ser cero. Por lo tanto, debemos tener h(s0) ≤ C∗ para todo s0, y h es admisible. (Fuente: Universidad de California, Irvine)
Si te sientes estimulado, puedes dejar un tutorial acerca de qué le añadirías a esta sección.