Welcome to Stratos!
Aqui os dejo en PDF lo que se me ha ocurrido, a ver que os parece.
En que no es solamente encontrar UN camino, sino evitar (en lo posible) caminos mas largos de lo necesario. Es decir, en vez de 4,8,5, 2, que no salga 4, 8, 7, 3, 6, 5, 2, que tambien seria valido pero mas largo.
Veamos, el asunto esta en que al calcular el contenido de las tablas precalculadas podemos disponer de mas tiempo, un elemento critico en algoritmos en tiempo real.La idea se basa en: "Si estas en el nodo X y vas al nodo Y, el primer paso es el nodo Z". Y eso es todo lo que nos interesa del camino entre X e Y, porque avanzamos un unico paso. Por tanto, la ruta completa es irrelevante. El ejemplo nos da 8 posibles nodos, hay que encontrar una ruta entre X e Y. Para no caer en bucles infinitos cada nodo solo se puede visitar una vez. Si miramos las taclas de "ramas" y "hojas", se ve que el recorrido del arbol es en profundidad .
LUT para ir de X a Y el siguiente nodo es ZX > Y Z4 > 2 84 > 5 84 > 1 84 > 8 8 4 > 7 74 > 3 7 4 > 6 78 > 2 5...5 > 2 2...
4 > 2 = 88 > 2 = 55 > 2 = 2