Necesito ayuda para encontrar una buena heurística para el siguiente problema:

Se te da unaR-por-C rejilla y un dado de seis caras. Dejarstart yend Serán dos celdas distintas en esta cuadrícula. Encontrar un camino desdestart aend de modo que la suma de las caras de la matriz mirando hacia arriba, a medida que la matriz gira en el camino, es mínima.

La orientación inicial del dado es la siguiente (el "2" está orientado al sur):

La forma en que modelé este problema es considerando el valor de la cara del dado como el costo de un borde en un gráfico. Los vértices de la gráfica son de la forma.(row, col, die) (es decir, una posición en la cuadrícula y el estado / orientación actual del dado). La razón por la que un vértice no es simplemente(row, col) es porque puede terminar en la misma celda con múltiples configuraciones / orientaciones del dado.

Usé A * para encontrar la solución al problema; Las respuestas dadas son correctas, pero no es lo suficientemente eficiente. He determinado que el problema es la heurística que estoy usando. Actualmente estoy usando la distancia de Manhattan, que obviamente es admisible. Si multiplico la heurística por una constante, ya no es admisible: corre mucho más rápido, pero no siempre encuentra la respuesta correcta.

Necesito ayuda para encontrar una mejor heurística que la distancia de Manhattan.