El backjumping es un algoritmo derivado del backtracking, de hecho la principal diferencia (y por tanto su ventaja) radica en que el backtracking cuando falla, retrocede un nivel para continuar la búsqueda, mientras que backjumping puede retroceder varios niveles. Esta diferencia se percibe en un rendimiento mayor en el espacio de búsqueda.
el problema es que los ejemplos que vienen en las hojas que me has pasado son iterativos y yo los necesito recursivos.
Si tienes el algoritmo iterativo, no debería serte difícil convertirlo a recursivo.
El resto del post incide en esto.
Un algoritmo iterativo guarda referencias antes de entrar en el bucle, al salir del bucle puede asignar la referencia localizada en el bucle o desestimar y quedarse con la referencia previa. Entonces para convertirlo en iterativo lo que necesitamos es poder utilizar esta capacidad fuera de la llamada, para esto lo más adecuado es disponer de una función adicional que envuelve a esta, es decir el código dentro del bucle sería lo que exclusivamente formaría la función y lo que está fuera del bucle (delante y detrás) es lo que queda en la función principal de la llamada.
Intentaré reflerjarlo en un sencillo esquema:
Sea un procedimiento que se invoca para realizar un cálculo cualquiera, que necesita un recorrido (en el sentido de repetir) para arrojar el resultado. siendo iterativo sería algo como esto:
Procedimiento Calculo(ListaParametrosCalculo)
Establecimiento inicial de valores (a)
Iniciar bucle comprobar condicionantes de repetición del bucle (b)
Calcular...
fin bucle
pasos posteriores, a veces es sólo una devolución. (c)
Fin calculo
Como se ve hay 3 elementos claramente diferenciados: (a) - Establecer valores para las variables del entorno antes de nada, normalmente lo mínimo, es validar los parámetros de entrada. (b) - realizar el bucle (si procede) calculando y comprobando si persiste la iteración. Y (c) - tratamiento posterior a la salida del bucle. Esta parte, puede o no, existir y en muchos casos se reduce a una simple asignación de devolución (quizás formateando el datov quizás comparandolo con el dato previo al bucle ).
Para recrear el algoritmo de forma recursiva necesitamos (haciéndolo del modo más simple y claro) 2 procedimientos en vez de uno. La razón es que al llamarse a si mismo, no debe cambiar estados ajenos al interior del bucle, por eso un procedimiento es el paso (b) del procedimiento iterativo y otro los pasos (a) y (c) del procedimiento iterativo. en medio de estos pasos se hace una única llamada al paso (b), por tanto conserva extactamente los mismos pasos... luego es (b) quien se reinvoca a si misma las veces que precise.
El esquema sería por tanto este:
Procedimiento Calculo(ListaParametrosCalculo)
Establecimiento inicial de valores ( a)
llamada a CalculoRecursivo(Listaparametros) <-------- (b) ahora es una ÚNICA llamada a un procedimiento
pasos posteriores, a veces es sólo una devolución. ( c)
Fin Calcculo
Procedimiento CalculoRecursivo(ListaParametros) (b)
comprobar condicionantes de repetición del bucle
calcular... (b-1)
CalculoRecursivo(listaparametros) (b-2) <-------- ahora es una llamada a si mismo, es iterativo
fin comprobar
Fin CalculoRecursivo
No es necesario que te señale que el comrpobante de recursión o iteración pueden ir tanto delante, detrás como en medio, conforme se precise para el estado interno de las variables.
Con estas indicaciones deberías ser capaz de convertir cualquier procedimiento iterativo en recursivo y viceversa.
p.d.: Para comprender bien el algoritmo backjumping, yo te sugeriría que lo aplicaras por ejemplo al problema de las 8 reinas... Con posiciones prefijadas, para facilitar entender como evoluciona.
