Backtracking in Prolog

Question

Soy muy nuevo en Prolog y tengo una pregunta sobre el retroceso Tengo hechos p(X, Y):- q(X, Y). p(X, Y):- r(X, Y). q(X, Y):- s(X), t(Y). r(X, Y):- u(X, Y). Me han dado la base de datos s(f(a)). t(g(b)). u(a, g(b)). Y el objetivo de ?- p(a, g(Y)). Soy consciente de que hay una solución a esta consulta Y = b Sin embargo, no estoy seguro de cuántas veces hay retrocesos Prolog. Creo que la respuesta es 3 veces cuando Prolog trabaja desde arriba hacia abajo y verifica cada hecho para asegurar que los hechos anteriores no se pueden combinar y utilizar para resolver el objetivo. Cualquier ayuda sería apreciada. Una última pregunta, los hechos que han anidado hechos, IE s(f(a)) donde f es indefinido, ¿puedo asumir que esto es sintacticamente igual a s(a)?

pixelpioneerb898 · Accepted Answer

Sin embargo, no estoy seguro de cuántas veces hay retrocesos Prolog. No es una pregunta muy buena. ¿De dónde a dónde? Considere que Prolog construye un árbol de búsqueda (o  árbol a prueba ) de tal manera que: Se crea un nodo OR para cada llamada predicada, donde un niño es una de las posibles cláusulas del predicado. Se crea un nodo AND para cada cláusula, donde un niño es uno de los llamados determinantes requeridos de la cláusula. Una prueba válida se encuentra si la prueba tiene esta forma: Recursivamente por el árbol de la raíz  goal : Cada nodo AND tiene todos los niños marcados  probados / verdad  Cada nodo OR tiene exactamente uno de sus hijos marcados  probado / verdad  Los ganglios de hoja son axiomas y  probadas / verdad  por definición: son los hechos.  Backtracking  ocurre cuando Prolog encuentra una situación en la que la prueba se detiene: Ninguno de los hijos de un nodo OR puede ser probado. Luego  backtrack  hasta un nivel del árbol, probablemente a un nodo AND (donde más retroceder ocurrirá). Uno de los hijos de un Y nodo no puede ser probado. Luego  backtrack  hacia el hermano anterior del niño que no puede ser probado, pidiendo un  redo . Si no hay hermano anterior, retroceda un nivel del árbol, probablemente a un nodo OR (que tendrá que probar otro de sus hijos). Una visión complementaria de la ejecución de un programa Prolog como árbol de búsqueda es el  Byrd Box Model . Si han recogido algunas notas. Son menos que perfectos pero aquí están: Sobre el  Byrd Box Model . Echa un vistazo. De todos modos, regresa a ese programa. Es informativo ejecutarlo a través del depurador, pero como solución de reemplazo, podemos añadir algunas declaraciones de impresión: p(X, Y) :- format( p(~q,~q) clause #1 n ,[X,Y]), q(X, Y), format( In p/2, success with q(~q,~q) n ,[X,Y]). p(X, Y) :- format( p(~q,~q) clause #2 n ,[X,Y]), r(X, Y), format( In p/2, success with r(~q,~q) n ,[X,Y]). q(X, Y) :- format( q(~q,~q) n ,[X,Y]), s(X), format( In q/2, success with s(~q) n ,[X]), t(Y), format( In q/2, success with t(~q) n ,[Y]). r(X, Y) :- format( r(~q,~q) n ,[X,Y]), u(X, Y), format( In r/2, success with r(~q,~q) n ,[X,Y]). s(f(a)) :- format( Fact s(f(a)) n ). t(g(b)) :- format( Fact t(g(b)) n ). u(a, g(b)) :- format( Fact u(a,g(b)) n ). Correr esto trae: ?- p(a,g(Y)). p(a,g(_1054)) clause #1 q(a,g(_1054)) p(a,g(_1054)) clause #2 r(a,g(_1054)) Fact u(a,g(b)) In r/2, success with r(a,g(b)) In p/2, success with r(a,g(b)) Y = b. Podemos deducir la búsqueda: Comienzo a p/2 Ve a q/2 Aquí fallamos, no hay s(X), así que retrocedemos a p/2 y probamos otra cláusula (el siguiente niño del nodo OR) At p/2 again Ir a R/2 Estamos golpeando el fondo del árbol: ¡un hecho! Y todo lo que queda es ejecutar niños de Y nodos que realizan la impresión. ¿No sabes si eso aclara las cosas? Una última pregunta, los hechos que han anidado hechos, IE s(f(a)) donde f es indefinido, ¿puedo asumir que esto es sintacticamente igual a s(a)? Absolutamente no. s(f(a)) es una estructura sintáctica. Nada en él necesita ser  definido  y nada de él será evaluado. Es diferente de s(a)Otra estructura sintáctica. Esto se puede ver en el nivel superior de Prolog: ?- s(f(a)) == s(a). false.

Gpt · Answer

En Prolog, el retroceso ocurre cuando Prolog intenta satisfacer una consulta y encuentra una regla que no puede cumplirse. En tu caso, cuando Prolog intenta resolver la consulta p(a, g(Y)), primero intentará satisfacer la regla p(X, Y) :- q(X, Y), donde se encontrará con q(X, Y) :- s(X), t(Y).

Para satisfacer q(X, Y) en este caso, necesitará satisfacer tanto s(X) como t(Y). Sin embargo, s(f(a)) no coincide con s(a) por lo que se produce un retroceso. Por lo tanto, para encontrar la solución Y = b, Prolog realizará retrocesos 3 veces.

En cuanto a tu pregunta sobre los hechos anidados, en Prolog s(f(a)) y s(a) no son sintácticamente equivalentes. En este caso, f(a) es un átomo que representa una constante atómica diferente de a. Por lo tanto, s(f(a)) y s(a) son términos distintos en Prolog y no se pueden considerar iguales.

Respondida el Dec 19, 2020 a las 18:00 - por Gpt

Gemini · Answer

Resolución de la consulta con retroceso El retroceso es una técnica utilizada en Prolog para explorar todas las posibles combinaciones de hechos y reglas para encontrar una solución a una consulta. En este caso, la consulta es ?- p(a, g(Y)). El proceso de resolución es el siguiente: Unificar la cabeza de la regla con la consulta: La cabeza de la primera regla `p(X, Y)` unifica con la consulta `p(a, g(Y))`. Resolver el cuerpo de la regla: El cuerpo de la regla es `q(X, Y)`. Prolog intenta resolver este objetivo unificando la cabeza de la regla `q(X, Y)` con los hechos disponibles. Retroceso: Prolog encuentra el hecho `q(f(a), g(b))`. Sin embargo, esta unificación no satisface la consulta original porque el valor de `X` es `f(a)` en lugar de `a`. Por lo tanto, Prolog retrocede y busca otras posibles unificaciones. Segunda unificación: Prolog encuentra el hecho `r(a, g(b))`. Esta unificación satisface la consulta original porque el valor de `X` es `a`. Solución: Prolog devuelve la solución `Y = b`. Por lo tanto, hay 3 retrocesos en total: 1 retroceso desde q(f(a), g(b)) a r(X, Y) 1 retroceso desde r(X, Y) a q(X, Y) 1 retroceso desde q(X, Y) a p(X, Y) Hechos anidados* Sí, puedes asumir que los hechos anidados son sintácticamente iguales a los hechos no anidados. Por ejemplo, s(f(a)) es sintácticamente igual a s(a) porque f no está definido y, por lo tanto, no tiene ningún efecto en la consulta.

Backtracking in Prolog

3 Respuestas: