SoloCodigo

Programación Específica => Inteligencia Artificial => Mensaje iniciado por: subsoho en Martes 13 de Octubre de 2009, 09:10

Título: backjumping
Publicado por: subsoho en Martes 13 de Octubre de 2009, 09:10

Hola,

Estoy buscando ejemplos de backjumping, es decir la mejora del backtracking. Quiero el problema propuesto con el algoritmo que implementa la solución utilizando backjumping y una explicación clara de los pasos que sigue éste.

Gracias.

Título: Re: backjumping
Publicado por: m0skit0 en Sábado 17 de Octubre de 2009, 01:58

http://www.dcs.gla.ac.uk/publications/P ... er_cbj.pdf (http://www.dcs.gla.ac.uk/publications/PAPERS/8104/prosser_cbj.pdf" onclick="window.open(this.href);return false;)

Título: Re: backjumping
Publicado por: subsoho en Domingo 25 de Octubre de 2009, 10:54

Muchas gracias por tu respuesta, el problema es que los ejemplos que vienen en las hojas que me has pasado son iterativos y yo los necesito recursivos.

Necesito ejemplos de backjumping recursivo para estudiar su funcionamiento
¿Alguien me puede ayudar?

Título: Re: backjumping
Publicado por: Nebire en Domingo 25 de Octubre de 2009, 16:25

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.

Citar

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:

Código: Text

1.  
2. Procedimiento Calculo(ListaParametrosCalculo)
3.      Establecimiento inicial de valores       (a)  
4.  
5.  
6.      Iniciar bucle     comprobar condicionantes de repetición del bucle                                 (b)                
7.           Calcular...                                                                              
8.      fin bucle
9.  
10.  
11.     pasos posteriores, a veces es sólo una devolución.         (c)
12. Fin calculo
13.  
14.  

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:

Código: Text

1.  
2. Procedimiento Calculo(ListaParametrosCalculo)
3.      Establecimiento inicial de valores                        ( a)
4.          llamada a CalculoRecursivo(Listaparametros)        <-------- (b) ahora es una ÚNICA llamada a un procedimiento
5.     pasos posteriores, a veces es sólo una devolución. ( c)
6. Fin Calcculo
7.  
8. Procedimiento CalculoRecursivo(ListaParametros)  (b)
9.         comprobar condicionantes de repetición del bucle        
10.                   calcular...                                                 (b-1)
11.                   CalculoRecursivo(listaparametros)              (b-2)    <--------  ahora es una llamada a si mismo, es iterativo
12.          fin comprobar
13. Fin CalculoRecursivo
14.  
15.  

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.

Título: Re: backjumping
Publicado por: subsoho en Lunes 26 de Octubre de 2009, 08:50

Muchas gracias por tu interés.

Es buena idea implementar el problema de las 8 reinas con backjumping, pero necesito un ejemplo de su funcionamiento para saber si mi implementación es correcta o no.