Prolog generador de código con swap y move

[fileteruso]

Buenos días,

tengo que hacer un programa como práctica para la universidad y no se me ocurre ninguna solución posible a priori, si alguien puede ayudarme le estaría muy agradecido.

Tengo que hacer en Prolog una representación de una CPU anular con registros. Los registros se representan de la siguiente forma: regs/n donde n es cualquier número mayor o igual que 2. Los registros pueden llevar en su interior cualquier tipo de carácter, un ejemplo:

Código [Seleccionar] Expandir


regs(a,b,c,d).


En la CPU hay 2 tipos de intrucciones swap/2 y move/1, y al ejecutarlas resulta lo siguiente:

Código [Seleccionar] Expandir


ejecutar_instruccion(regs(a,b,c,d),swap(1,3),R).
R = regs(c,b,a,d).

ejecutar_instruccion(regs(a,b,c,d),move(2),R).
R = regs(a,b,b,d).


Este predicado ya lo he hecho, ahora me piden realizar un generador de código que te lleve de un estado inicial a un final de la siguiente manera:

Código [Seleccionar] Expandir


generador_codigo(regs(a,b,c,d),regs(a,a,d,b),R).
R = [swap(2,3), move(1), swap(3,4)].


Resultando el número mínimo de instrucciones necesarias para alcanzar el estado final. No se me ocurre manera alguna de programarlo. Si alguien me pudiese ayudar y decirme algún algoritmo (no código como tal) que lo solucione le estaría muy agradecido.

Muchas gracias a todos de antemano.

[Serapis]

No queda claro cuales son todas las restricciones.

La idea básica para lograrlo es la recursión del backtracking que provee prolog.
Dado que move(X), borrará alguna de las variables, el primer paso debería ser buscar los valores no repetidos en el estado final, y usar swap(X,Y...) al caso... determina la condición final de cuando se alcanza este semiestado es lo que te debe hacer pensar un poquito.

Y solo cuando se hayan completado esta submeta es cuando procede hacer los move(X) que fueren precisos. Not que por ejemplo para una entrdada: ... regs(A,A,A,A), R). no habría lugar a los swap, si no solo a los move, igualmente en una entrada como: ...regs(D,B,A,C), R). no habría lugar a los move, si no solo a los swap.

[fileteruso]

Debido a que no consigo el camino mínimo estoy intentando conseguir el primer camino que se encuentre.
Como bien dices la clave está en usar el backtracking de Prolog, la cosa es que para valores con 2 o 3 registros solo (regs(x,x) o regs(x,x,x)) funciona perfectamente: si encuentra un camino, lo devuelve, y si, después de recorrer todas la opciones recursivamente, no encuentra ningún camino que lleve al estado final, devuelve false y acaba. Sin embargo, para valores mayores ocurre que solo devuelve aquellos casos en los que se encuentra una solución en las primeras ramas recorridas. El código que he hecho hasta ahora es el siguiente:

Código [Seleccionar] Expandir


generar_codigo(EstadoInicial,EstadoFinal,ListaDeInstrucciones) :-
   functor(EstadoInicial,regs,NumCaracteres),
   functor(EstadoFinal,regs,NumCaracteres),
   ListaParcial = [no_instr],
   generar_codigo(EstadoInicial,EstadoFinal,ListaParcial,ListaInversa,NumCaracteres,[EstadoInicial]),
   reverse(ListaInversa,ListaDeInstrucciones).

generar_codigo(EstadoActual,EstadoActual,ListaParcial,ListaParcial,NumCaracteres,_) :- !.
generar_codigo(EstadoActual,EstadoFinal,ListaParcial,ListaDeInstrucciones,NumCaracteres,EstadosVisitados) :-
   get_cabeza(ListaParcial,InstrAnterior),
   instrs_posibles(EstadoActual,1,NumCaracteres,InstrAnterior,InstrAEjecutar),
   ejecutar_instruccion(EstadoActual,InstrAEjecutar,EstadoSig),
   \+ member(EstadoSig,EstadosVisitados),
   generar_codigo(EstadoSig,EstadoFinal,[InstrAEjecutar|ListaParcial],ListaDeInstrucciones,NumCaracteres,[EstadoSig|EstadosVisitados]).



get_cabeza(L,E) devuelve en E el primer elemento de la lista L y reverse(LI,LF) devuelve en LF la lista LI invertida.

El predicado instrs_posibles/5 devuelve una instrucción (InstrAEjecutar) que se puede realizar pasado un estado (EstadoActual) y si tras devolver esa solución se piden más devuelve el resto hasta que no encuentra más:

Código [Seleccionar] Expandir


?- instrs_posibles(regs(a,b,c),1,3,no_instr,Instr).

Instr = move(1) ? ;

Instr = swap(1,2) ? ;

Instr = swap(1,3) ? ;

Instr = move(2) ? ;

Instr = swap(2,3) ? ;

Instr = move(3) ? ;

false
?-



Lo que no llego a entender es por qué hay ocasiones en las cuales se queda en un bucle infinito, si, como he comentado antes, en los casos en los que hay 2 o 3 registros máximos acaba perfectamente y si los ejecuto con el debugger se ve claramente como recorre todas las opciones posibles.

Gracias de nuevo por la ayuda.

[fileteruso]

Al final he conseguido que funcione. Por si a alguien más le interesa, era simplemente añadir un parámetro más que indique el número de instrucciones que se pueden ejecutar de forma que primero ejecuta todos los caminos posibles con una instrucción, después con dos, y así sucesivamente, encontrando siempre el número mínimo de instrucciones necesarias.