sábado, 22 de junio de 2013

Capitulo 5

5. Control del Retroceso (Backtracking).
Hemos visto hasta ahora que el programador puede controlar la ejecución de un programa
ordenando las cláusulas y metas. En este capítulo estudiaremos otra manera de control
conocida como corte (cut).

5.1. Prevención del retroceso.
Prolog realizará automáticamente el retroceso si es necesario para satisfacer una meta. El
retroceso automático es un concepto de programación muy útil porque libera al
programador de la tarea de programar explícitamente los retrocesos. Aunque por otra
parte el retroceso sin control puede ocasionar ineficiencia en un programa. Por lo tanto es
necesario saber prevenir y controlar el retroceso.

la relación entre X y Y puede especificarse con las tres reglas siguientes :
 Regla 1 : if X < 3 then Y = 0
 Regla 2 : if 3 <= X and X < 6 then Y = 2
 Regla 3 : if 6 <= X then Y = 4
lo cual puede escribirse en Prolog como :
 f(X,0) :- X < 3. % Regla 1
 f(X,2) :- 3 =< X, X < 6. % Regla 2
 f(X,4) :- 6 =< X. % Regla 3

?- f(7, Y).
 Y = 4.
Analicemos que ha sucedido. Las tres reglas fueron exploradas antes de que la respuesta
final fuera obtenida. Esto produjo la siguiente secuencia de metas:
regla 1 : 7 < 3 falla, retrocede y trata la regla 2.
regla 2 : 3 ó 7 tiene éxito, enseguida 7 < 6 falla, retrocede y trata la regla 3.
regla 3 : 6 ó 7 tiene éxito.
esta traza nos revela otra fuente de ineficiencia. Primero establece que X < 3 no es cierto
(7<3 3="<" 7="" es="" falla="" la="" meta="" nbsp="" nosotros="" p="" pero="" que="" sabemos="" siguiente="" tiene="" x="" xito="">una vez que la primera prueba ha fallado, la segunda prueba va a realizarse como si fuese
la negación de la primera. Por lo tanto la segunda prueba es redundante y la meta
correspondiente puede omitirse. Lo mismo es verdad acerca de la meta 6 =< X en la regla
3. Esto nos lleva a la siguiente formulación de las tres reglas anteriores:
 if X < 3 then Y = 0,
 de-otro-modo if X < 6 then Y = 2,
 de-otro-modo Y = 4.
lo cual nos lleva a la tercera versión en Prolog :
 f(X,0) :- X < 3, !.
 f(X,2) :- X < 5, !.
 f(X,4).
éste último programa produce los mismos resultados que la versión original pero es la
versión mas eficiente.
Nótese sin embargo que si removemos los símbolos de corte:
 f(X,0) :- X < 3.
 f(X,2) :- X < 5.
 f(X,4).
la ejecución producirá soluciones múltiples y equivocadas. Por ejemplo:
 ?- f(1,Y).
 Y = 0;
 Y = 2;
 Y = 4;
 no.

5.2. Usando el corte.
Cálculo del máximo.
El procedimiento para encontrar el valor máximo de dos números puede programarse
como una relación :
 max(X,Y,Max).
donde Max = X si X es mayor ó igual a Y, y Max es Y si X es menor a Y :
 max(X,Y,X) :- X >= Y.
 max(X,Y,Y) :- X < Y.
estas dos reglas son mutuamente exclusivas; una formulación mejor es :
 if X ó Y then Max = X,
 de-otro-modo Max = Y.
ésto se escribe en Prolog usando el corte como :
 max(X,Y,X) :- X >= Y, !.
 max(X,Y,Y). 

No hay comentarios:

Publicar un comentario