elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Prolog generador de código con swap y move
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Prolog generador de código con swap y move  (Leído 3,633 veces)
fileteruso

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Prolog generador de código con swap y move
« en: 3 Mayo 2020, 12:18 pm »

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:
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:
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:
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.


« Última modificación: 3 Mayo 2020, 12:33 pm por fileteruso » En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Prolog generador de código con swap y move
« Respuesta #1 en: 4 Mayo 2020, 16:51 pm »

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.


En línea

fileteruso

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Re: Prolog generador de código con swap y move
« Respuesta #2 en: 10 Mayo 2020, 17:43 pm »

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:
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:
?- 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.
« Última modificación: 10 Mayo 2020, 17:52 pm por fileteruso » En línea

fileteruso

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Re: Prolog generador de código con swap y move
« Respuesta #3 en: 11 Mayo 2020, 16:24 pm »

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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
<move>Como conectar la PC a la TV por el puerto del monitor???</move>
Electrónica
Rywshan 1 3,413 Último mensaje 30 Diciembre 2004, 06:47 am
por botboat
[move]AYUDA!!![/move]
Diseño Gráfico
Wicho 1 1,954 Último mensaje 28 Marzo 2005, 16:10 pm
por _the_master_36
Generador de codigo jsp con Java
Java
arcannum_arcandrum 0 3,880 Último mensaje 29 Abril 2005, 01:50 am
por arcannum_arcandrum
Generador codigo QR
Software
vipamon 3 2,097 Último mensaje 3 Marzo 2013, 17:34 pm
por vipamon
Generador de codigo QR
.NET (C#, VB.NET, ASP)
almita 0 1,766 Último mensaje 7 Junio 2013, 21:05 pm
por almita
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines