פרק 8: cut ושלילה

8.1 cut

העובדה שפרולוג משתמש ב-backtracking, נסיגה וחיפוש פתרונות חלופיים, מקנה לו כוח רב. אולם לעיתים האפשרות לבצע נסיגה עלולה לגרום לחוסר יעילות, כאשר פרולוג מנסה לבצע חישובים לא מועילים לשווא.

למרבה המזל, פרולוג מאפשר לנו לשלוט במשהו על ביצוע הנסיגות באמצעות מתאר מיוחד ששמו cut. המתאר מסומן ! (סימן קריאה), וניתן להשתמש בו בתוך חוקים:

p(X) :- a1(X),…, an(X), !, b1(X),…, bn(X).

המתאר ! מסמן לפרולוג לוותר על אפשרויות לסגת ולחפש פתרונות נוספים (backtracking). ביתר דיוק, אחרי ביצוע ה-cut:

  1. אי אפשר לנסות חוקים אחרים עבור p.
  2. אי אפשר לחפש פתרונות חלופיים לתת-המטרות שקדמו ל-! בחוק הנוכחי, קרי a1 עד an.

לעומת זאת, כן ניתן לבצע נסיגות בעת חישוב b1 עד bn, וכן ניתן לבצע נסיגות במטרות שקדמו לחישוב p.

נראה דוגמא. נתייחס לתכנית הבאה:

q(X, Y) :- p(X,Y).
q(4,4).

p(X, Y) :- a(X), b(Y).
p(3, 3).

a(1).
a(2).
b(1).
b(2).

בגרסא זו, ללא cut, אנו מקבלים את התוצאה הצפויה:

?- q(U, V).

U = 1
V = 1 ;

U = 1
V = 2 ;

U = 2
V = 1 ;

U = 2
V = 2 ;

U = 3
V = 3 ;

U = 4
V = 4 ;

No

כעת נחליף את החלק הראשון בהגדרת p בגרסא הכוללת cut. כל יתר התכנית ללא שינוי:

q(X, Y) :- p(X,Y).
q(4,4).

p(X, Y) :- a(X), !, b(Y).
p(3, 3).

a(1).
a(2).
b(1).
b(2).
זהו השינוי היחיד בתכנית יחסית לגרסתה הקודמת.
שימו לב לקוד האינטראקטיבי.

תגובת פרולוג לשאילתא משתנה:

?- q(U, V).

U = 1
V = 1 ;

U = 1
V = 2 ;

U = 4
V = 4 ;

No

מה קורה כאן? הסבר מפורט בסרטון הבא:

עכשיו אנו יודעים מה משמעות המתאר !. נשאלת השאלה, כיצד נשפר בעזרתו את היעילות של תכניותינו?

נשלב אותו בתכניות שלנו במקומות שבהם נרצה לחסוך חישובים מיותרים. למשל, נניח מתאר מסוים מוגדר באמצעות שני חוקים אשר לעולם אינם מתקיימים שניהם ביחד. אם חוק א' מתקיים, אז חוק ב' לא מתקיים, ולהפך. במתאר כזה נוכל לשלב cut בסוף החוק הראשון על מנת למנוע ניסיונות מיותרים של בדיקת חוק ב'. דוגמא למקרה כזה היא המתאר gender לבדיקת מינו של אדם:

gender(X,G) :- boy(X), G=male.
gender(X,G) :- girl(X), G=female.

בהנחה שיש רק שתי אפשרויות של הגדרה מגדרית, זכר ונקבה, ושאם אדם הוא זכר אז הוא לא נקבה ולהפך, אפשר לייעל את התכנית שלנו על ידי הוספת cut בסוף החוק הראשון. משמעות הדבר היא שאם מצאנו שאדם מסוים הוא זכר, אז הוא איננו נקבה ואין טעם לנסות להוכיח זאת על ידי החוק השני:

gender(X,G) :- boy(X), G=male,!.
gender(X,G) :- girl(X), G=female.
הורידו את התכנית המכילה את הגדרת gender ומידע על בנים ובנות ונסו בעזרת trace לראות את ההשפעה שיש ל-! על הביצועים.

מבוא

נושאים בסיסיים

נושאים מתקדמים

סיכום

© כל הזכויות שמורות למערכת המידע איתן