es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Programa de Prolog para enumerar todas las posibles soluciones en un conjunto contable.

28 Jul, 2023 Programación

Estoy escribiendo un programa en Prolog que puede realizar aritmética de Peano.

Tengo definiciones estándar para los números naturales.

nat(n).
nat(s(N)) :-
    nat(N).

Porque quiero enumerar todas las posibles relaciones de adición entre números naturales, he definido una función auxiliar (para definir un orden total sobre el conjunto).

cmp_n(X, Y, lt) :-
    nat(Y),                % generar una secuencia: n s(n) s(s(n)) ...
    cmp_n_helper(X, Y). % da todos los XS más pequeños que Y

cmp_n_helper(s(X), s(Y)) :-
    cmp_n_helper(X, Y).
cmp_n_helper(n, s(Y)) :-
    nat(Y).

Luego, definí la adición.

% necesito usar un envoltorio porque quiero generar (n, n, n) primero
% si no uso este envoltorio, comenzaría desde (n, s(n), s(n))
add_n(X, Y, R) :-
    nat(R),                  % misma razón de antes
    cmp_n(X, R, lt),
    add_n_helper(X, Y, R).

add_n_helper(s(X), Y, s(R)):-
    add_n_helper(X, Y, R).
add_n_helper(n, Y, Y).

Si enumero todas las posibles relaciones sobre esta definición de adición, funciona correctamente. Y cuando se muestran un conjunto finito de respuestas, puede detenerse.

?- add_n(X, Y, R).
X = Y, Y = R, R = n ;
X = R, R = s(n),
Y = n ;
X = n,
Y = R, R = s(n) ;
X = R, R = s(s(n)),
Y = n ;
X = Y, Y = s(n),
R = s(s(n)) ;
X = n,
Y = R, R = s(s(n)) .

?- add_n(X, Y, s(s(s(s(n))))).
X = s(s(s(s(n)))),
Y = n ;
X = s(s(s(n))),
Y = s(n) ;
X = Y, Y = s(s(n)) ;
X = s(n),
Y = s(s(s(n))) ;
X = n,
Y = s(s(s(s(n)))) ;
false.

Esto funcionó bien.

Sin embargo, si hago la evaluación directa regular,

?- add_n(s(s(s(n))), s(s(n)), R).
R = s(s(s(s(s(n))))) .

este programa no puede detenerse.

Me pregunto si hay una manera de:

  1. Para cualquier respuesta finita, dar un resultado finito.
  2. Para cualquier respuesta infinita, elegir una respuesta específica válida, dar esta respuesta específica en tiempo finito.
Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Como experto en TI especializado en Prolog, aquí están mis recomendaciones para abordar las preocupaciones que has planteado en tu pregunta:

    1. Para asegurarte de que el programa se detenga y proporcione un resultado finito para cualquier respuesta finita, puedes utilizar una técnica llamada “tabulación” o “memoización”. La evaluación tabular realiza un seguimiento de todas las soluciones que ya han sido calculadas y las reutiliza cuando se necesitan nuevamente. Esta técnica evita que el programa entre en un bucle infinito o genere soluciones duplicadas. En SWI-Prolog, puedes utilizar la directiva “table” para habilitar la tabulación para un predicado específico.

    Por ejemplo, puedes modificar tu predicado “add_n” para utilizar la tabulación de la siguiente manera:

    :- table add_n/3.

add_n(X, Y, R) :-
    nat(R),
    cmp_n(X, R, lt),
    add_n_helper(X, Y, R).

add_n_helper(s(X), Y, s(R)):-
    add_n_helper(X, Y, R).
add_n_helper(n, Y, Y).
    1. Para corregir una respuesta válida específica para cualquier respuesta infinita, puedes utilizar una técnica llamada “búsqueda acotada”. La búsqueda acotada limita el espacio de búsqueda del programa a un número fijo de soluciones y devuelve la mejor solución encontrada hasta el momento. Esta técnica es útil cuando sabes que el espacio de búsqueda es infinito, pero solo necesitas un número finito de soluciones.

    Por ejemplo, puedes modificar tu predicado “add_n” para utilizar la búsqueda acotada de la siguiente manera:

    add_n(X, Y, R) :-
    bounded_search(add_n_helper(X, Y, R), 0, 10, _, R).

add_n_helper(s(X), Y, s(R)) :-
    add_n_helper(X, Y, R).
add_n_helper(n, Y, Y).

    En este ejemplo, el predicado “bounded_search” limita el espacio de búsqueda a 10 soluciones y devuelve la mejor solución encontrada hasta el momento en el cuarto argumento. Si el espacio de búsqueda no se ha agotado, el quinto argumento se unificará con la siguiente solución.

    Espero que estas técnicas sean útiles para abordar tus preocupaciones. ¡Buena suerte con tu programación en Prolog!

Comments are closed.