Predicado de Corte

Muchas veces podemos estar interesados en lograr una sola solución para un objetivo dado. Para estos casos se utiliza el predicado cut, que se escribe en Prolog como “!”. LA idea del cut, es cortar el árbol de búsqueda para reducir el número de respuestas que nos dará el intérprete. Veamos un ejemplo. Si realizamos la siguiente consulta:

?-member(X,[1,2]).

Todas las respuestas posibles posibles serían:

X=1;

X=2;

no

Ahora, si cambiamos nuestra consulta a:

?-member(X,[1,2]), !.X=1;no.

Al encontrar el cut, Prolog no vuelve atrás (backtrck) para encontrar otra respuesta. Hemos podado una rama del árbol. Veamos otro ejemplo:

enLasDos(X,L1,L2):-member(X,L1),member(X,L2).

Este predicado será verdadero si X pertenece a ambas listas L1 y L2. Entonces, la siguiente consulta:

?-enLAsDos(X,[1,2,3],[2,3,4]).X=2;X=3;no

O, sea, tendremos la intersección de ambas listas, o bien todos los elementos comunes a ambas listas. Si uno está interesado en una de estas soluciones, digamos, la primera, podríamos hacer el siguiente cambio al predicado:

enLasDos(X,L1,L2):-member(X,L1),!,member(X,L2).

Y entonces, la misma consulta anterior, arroja el siguiente resultado:

?-enLasDos(X,[1,3],[1,2,3,4]).X=1;no

El efecto del cut se resume en lo siguiente:

Podar todas las reglas debajo de él.

Podar todas las alternativas de conjunciones que aparecen a su izquierda.

No afecta la ejecución de los predicados a su derecha.

Hay que tener en cuenta que un mal uso del cut puede llevar a resultados erróneos en la ejecución de un programa lógico. Por ejemplo como el siguiente:

?-enLasDos(2,[1,2,3],[2,3,4]).yes.

?-enLasDos(X,[1,2,3],[2,3,4]).no

O sea, si bien en el primer caso encontró verdadero el hecho que 2 pertenezca a ambas listas, en el segundo caso no puede encontrar ningún valor para X que haga verdadero el predicado. Esto es porque el primermember instancia X en el primer elemento de la primera lista, o sea 1. Luego pasa el cut, lo que hace que el primer member no se vuelva a ejecutar. Luego se ejecuta el segundo member con el 1 y falla, dado que 1 no pertenece a la segunda lista. Como dijimos, el cut impide que se realice backtraking y se vuelva a ejecutar el primer member. Por lo tanto, la respuesta final, aunque incorrecta, es no.

C´alculo del m´aximo

u Programa sin corte

maximo_1(X,Y,X) :- Y =< X.

maximo_1(X,Y,Y) :- X =< Y.

u Programa con corte

maximo_2(X,Y,X) :- Y =< X, !.

maximo_2(X,Y,Y).

u Sesi´on

?- maximo_1(3,5,X).

X = 5 ;

No

?- maximo_2(3,5,X).

X = 5 ;

No

?- maximo_1(3,2,2).

No

?- maximo_2(3,2,2).

Yes

Comentario: eficiencia vs. sem´antica

El corte se utiliza muy frecuentemente, cuanto más diestro es el programador más lo suele usar. Los motivos por los que se usa el corte son, por orden de importancia, los siguientes:1. Para optimizar la ejecución. El corte sirve para evitar que por culpa del backtracking se

exploren puntos de elección que, con toda seguridad, no llevan a otra solución (fallan). Para los entendidos, esto es podar el árbol de búsqueda de posibles soluciones.

2. Para facilitar la legibilidad y comprensión del algoritmo que está siendo programado. A veces se situan cortes en puntos donde, con toda seguridad, no van a existir puntos de elección para eliminar, pero ayuda a entender que la ejecución sólo depende de la cláusula en cuestión.

3. Para implementar algoritmos diferentes según la combinación de argumentos de entrada. Algo similar al comportamiento de las sentencias case en los lenguajes imperativos.

4. Para conseguir que un predicado solamente tenga una solución. Esto nos puede interesar en algún momento. Una vez que el programa encuentra una solución ejecutamos un corte. Así evitamos que Prolog busque otras soluciones aunque sabemos que éstas existen.

Ejemplo:

Base de conocimientos sin utilizar el Corte.

padre(juan, pepe).

padre(juan, luis).

padre(juan, alberto).

hermanodepadre(X,Y):-padre(Z,X), padre(Z,Y).

Objetivo

?.- hermanodepadre(pepe, ana).

no

El proceso de ejecución se observa en la Figura 1.

 

Figura 1

Árbol de ejecución para la base de conocimientos y objetivo del ejemplo que no usa corte

Como se observa en el árbol de ejecución, cuando falla el segundo predicado del

consecuente, al hacerbacktracking, ignoramos la solución obtenida para el primer predicado en la rama anterior, y buscamos una nueva solución, con la esperanza de hallar aquella que, posteriormente, satisfaga al segundo predicado. Sin embargo, nosotros sabemos, a priori, que dicha solución no va a ser posible, porque ya hemos demostrado que juan es el padre de pepe y no lo es de ana, luego ambos no son hermanos de padre, luego, en este caso, no interesa seguir buscando nuevos padres para pepe (esto sería absurdo e ineficiente). Por tanto, no es necesario desarrollar la rama de retroceso representada por la línea discontinua en la Figura 1.

En la Figura 2 se muestra como queda el árbol al introducir en el código, el predicado corte. La rama que no se procesa se representa en color gris, para que sea posible la comparación con el ejemplo anterior.

Ejemplo:

Base de conocimientos utilizando el Corte.

padre(juan, pepe).

padre(juan, luis).

padre(juan, alberto).

hermanodepadre(X,Y):-padre(Z,X), !, padre(Z,Y).

Objetivo

?.- hermanodepadre(pepe, ana).

no

El proceso de ejecución se observa en la Figura 2.

 

Figura 2

Árbol de ejecución utilizando el corte

Dado el siguiente programa en prolog:

p(a).

p(b).

p(c).

q(1).

q(2).

q(3).

r(x). r(y). r(z).

t(X,Y,Z):- p(X) , q(Y) , r(Z).

Sea la siguiente consulta:

?-t(X,Y,Z). 27 soluciones

X = a

X = a

X = a

X = a

.

.

.

X = c

Y = 1

Y = 1

Y = 1

Y = 2

.

.

.

Y = 3

Z = X

Z = Y

Z = Z

Z = X

.

.

.

Z = Z

Se obtienen 27 soluciones, el programa busca todas las posibles

combinaciones de los hechos que satisfagan la regla, en el orden de ejecución como

se muestra en la Figura 2.1 y 2.2

Sean las siguientes reglas:

t(X,Y,Z):- p(X) , q(Y) , r(Z).

t(X,Y,Z):- p(Z) , q(Y) , r(X).

Sea la siguiente consulta:

?-t(X,Y,Z). 27 + 27 = 54 soluciones

Se obtienen 54 soluciones, 27 de la primer regla y 27 de la segunda, entra en

ambas ya que tienen el mismo nombre( t(con tres variables) ), si hubieran mas reglas

con el mismo nombre seguiría entrando en cada una de ellas y el número de

soluciones posibles seria la sumatoria de todas las soluciones.

Figura 2.2 Ejecución de una regla

t(X,Y,Z):- p(X) , q(Y) , r(Z).

F

v v v