Controlling Backtracking (Chapter 6)

مقدمة
  • في المحاضرة دي هنتكلم عن الـ Backtracking، اللي هي خاصية في الـ Prolog، وإزاي نتحكم فيها.
  • هنعرف إيه هي مشكلة الـ Backtracking الزيادة (Uncontrolled backtracking) اللي بتسبب عدم كفاءة.
  • هنستخدم الـ Cut (!) عشان نتحكم في الـ Backtracking ونسرّع البرنامج.
  • هنفرق بين الـ Green Cut والـ Red Cut.
  • هنشوف أمثلة كتير زي الـ max، تصنيف الأعداد (موجب/صفر/سالب)، تقسيم الـ Lists، وتصنيف لاعيبة التنس.

1. إيه هو الـ Backtracking؟

  • الـ Backtracking هو خاصية في الـ Prolog. معناه إن الـ Prolog بيرجع ورا خطوه وبيحاول يحقق الـ Goal بطريقة تانية.

مثال:

likes(mary, food).
likes(mary, tea).
likes(john, tea).
likes(john, mary).
  • لما نسأل السؤال ده:
?- likes(mary, X), likes(john, X).
%  عايزين حاجة ماري وجون الاتنين بيحبوها
  • الـ Prolog بيشتغل كالتالي:

Start: likes(mary, X)

X = food

Try: likes(john, food)

❌ Fails!

↩ Backtrack to likes(mary, X)

X = tea

Try: likes(john, tea)

✅ Succeeds!

X = tea ✓

  1. الـخطوه الأول likes(mary, X) ينجح و X = food, يعني ماري بتحب food.
  2. الـخطوه التانية, هنشوف هل جون كمان بيحب food ولا لا : likes(john, food) الاجابه لا.
  3. هنا هنرجع خطوه لورا ونجرب حاجة تانية غير food.
  4. رجعنا للخطوه الاولي وهنجرب الحاجه الي بعدها الي هيا X = tea , لقينا ان ماري بتحب الـ tea فعلا.
  5. الخطوه التانية نشوف هل جون كمان بيحب tea ولا لا, likes(john, tea) هتبقي true يعني هو كمان بيحب tea فعلا.
  6. كده وصلنا خلاص للي عايزينه.
مش لازم تفهم الحته دي عشان تعرف تحل

2. مشكلة الـ Backtracking الزيادة

  • الـ Prolog بيستخدم الـ Backtracking تلقائياً عشان يحقق الـ Goals ، لكن في بعض الأحيان الـ Backtracking ده بيسبب مشاكل ف الاداء (Inefficiency) في البرنامج.
المشكلة

أحياناً بنحاول ندور علي اجابات ونجرب حاجات ملهاش لازمة لأننا عارفين إنها مش هتنجح، لكن الـ Prolog مش عارف كده فبيضيع وقت في الـ Backtracking.

  • الحل: نستخدم الـ Cut عشان نتحكم في الـ Backtracking ونمنعه في الأماكن المناسبة.

3. الـ Cut وانواعها

  • الـ Cut هو Built-in predicate في الـ Prolog وبيتكتب كعلامة !.

انواع الـ Cut: مثال علي دالة f(X, Y)

  • عندنا العلاقة بين X و Y مكونة من تلات قواعد:
    • ا Rule 1: إذا X < 3 يبقى Y = 0
    • ا Rule 2: إذا 3 =< X < 6 يبقى Y = 2
    • ا Rule 3: إذا X >= 6 يبقى Y = 4

أ) بدون Cut:

f(X, 0) :- X < 3.            % Rule 1
f(X, 2) :- 3 =< X, X < 6.    % Rule 2
f(X, 4) :- 6 =< X.           % Rule 3
  • المشكلة: لو X = 1، اول rule هتنجح، بس الـ Prolog بيكمل ويجرب بقيت الـ rules يعني هيكمل ويجرب Rule 2 , 3 رغم اننا عرفنا النتيجه خلاص.

ب) Green Cut (Cut آمن):

f(X, 0) :- X < 3, !.           % Rule 1
f(X, 2) :- 3 =< X, X < 6, !.   % Rule 2
f(X, 4) :- 6 =< X.             % Rule 3
  • هنا احنا مشيلناش او عدلنا اي حاجة في الكود , حطينا بس ! في اخر الكلام , بحيث نقول للبرنامج : لو الـ rule اتحققت يبقي الباقيين اكيد غلط ومتكملش الي بعده.
  • والـ Green cut لو شلته الكود هيشتغل زي ماهو ومفيش أي حاجة هتبوظ، بس البرنامج هيبقى أبطأ شوية لأنه هينزل علي السطور التانية على الفاضي.
  • مكان الـ green cut بيبقي بعد الشروط زي مثلا X < 3 وقبل الـ assignment ( الي هو is او = لو فيه ).

ج) Red Cut ( مش آمن ):

f(X, 0) :- X < 3, !.
f(X, 2) :- X < 6, !.
f(X, 4).
  • اما هنا لو لاحظت احنا غيرنا في الكود نفسه يعني :
    • في السطر التاني : انته مكتبتش إن 3 =< X ، إنت اعتمدت إن البرنامج طالما وصل للسطر التاني ومعداش من السطر الأول، يعني أكيد الـ مش أصغر من 3.
    • وفي السطر التالت : انته مكتبتش أي شروط, انته قلتله لو وصلت هنا يبقى الـ على طول، لأنك واثق إن الـ ! اللي في السطور اللي فوق منعت أي رقم أصغر من 6 إنه يوصل هنا.
  • طبعا النوع ده مش آمن , لانك لو شلت الـ cuts الكود مش هيشتغل او هيطلع نتايج غلط.

5. دالة الـ max مع وبدون Cut

من غير Cut:

max(X, Y, Max) :- X >= Y, Max = X.
max(X, Y, Max) :- X < Y, Max = Y.
  • القاعدتين Mutually Exclusive (واحدة بس هي اللي هتشتغل).

بـ Red Cut:

max(X, Y, Max) :- X >= Y, !, Max = X.
max(X, Y, Max) :- Max = Y.
  • هنا شيلنا الشرط X < Y من القاعدة التانية، واعتمدنا على الـ Cut إنه يمنع الوصول للقاعدة التانية لو X >= Y كانت صحيحة.
  • لاحظ هنا مكان الـ ! كان بعد الشرط X >= Y وقبل الـ assignment الي هو Max = X

6. دوال شرطية (Conditional Functions)

مثال 1: Y = 3X لو X ≤ 5، و Y = X² + 5 لو X > 5

بدون Cut:

f(X, Y) :- X =< 5, Y is 3 * X.
f(X, Y) :- X > 5, Y is X ** 2 + 5.

باستخدام Cut:

f(X, Y) :- X =< 5, !, Y is 3 * X.
f(X, Y) :- Y is X ** 2 + 5.

مثال 2: تصنيف الأعداد (موجب/صفر/سالب)

% لو الرقم اكبر من صفر يبقي موجب ومتكملش
class(Number, positive) :- Number > 0, !.
 % لو الرقم صفر يبقي الناتج زيرو مفيش حاجة تعملها
class(0, zero) :- !.   
% لو وصلت لهنا يبقي مش موجب ومش صفر يبقي اكيد الرقم سالب
class(Number, negative).
ملاحظة

القاعدة التالتة مالهاش شرط (No condition) لأنها الـ Default. لو الرقم مش أكبر من 0 ومش 0، يبقى هو سالب أكيد.

7. تقسيم split List

الدالة split(Numbers, Positives, Negatives) بتقسم List الأرقام لـ List اللي فيها الموجبين (فيها الصفر) و List اللي فيها السالبين.

split([], [], []).
split([X|L], [X|L1], L2) :- X >= 0, !, split(L, L1, L2).
split([X|L], L1, [X|L2]) :- split(L, L1, L2).

تجربة:

?- split([3, -1, 0, 5, -2], Pos, Neg).
Pos = [3, 0, 5],
Neg = [-1, -2].

9. تصنيف لاعيبة التنس (Tennis Player Classification)

عندنا Database لماتشات تنس:

beat(tom, jim).
beat(ann, tom).
beat(pat, jim).

وعايزين نصنف كل لاعب لواحدة من تلات فئات:

  • Winner: كسب كل الماتشات اللي لعبها
  • Fighter: كسب وكمان خسر ماتشات
  • Sportsman: خسر كل الماتشات اللي لعبها
class(X, fighter) :- beat(X, _), beat(_, X), !.
class(X, winner) :- beat(X, _), !.
class(X, sportsman) :- beat(_, X).

تجارب:

?- class(tom, C).   % Tom beat(jim) and beat(ann,tom) ➔ C = fighter
?- class(ann, C).   % Ann beat(tom) no one beat(ann) ➔ C = winner
?- class(jim, C).   % Jim no one beat(jim) و beat(pat,jim) و beat(tom,jim) ➔ C = sportsman

10. member و member1 (Single-Solution Membership)

ا member (بتطلع كل الحلول):

member(X, [X|L]).
member(X, [Y|L]) :- member(X, L).

?- member(X, [a, b, c]).
X = a ;
X = b ;
X = c.

ا member1 (باستخدام Cut - بتطلع أول حل بس):

member1(X, [X|L]) :- !.
member1(X, [Y|L]) :- member(X, L).

?- member1(X, [a, b, c]).
X = a ;
no
الفرق
  • ا member1 بتستخدم Cut عشان توقف البحث بعد أول حل. مفيدة لو عايزين بس نعرف إن العنصر موجود، مش محتاجين كل الأماكن اللي هو موجود فيها.

11. إضافة عنصر بدون تكرار (add مع Cut)

عايزين دالة add(X, L, L1) تضيف العنصر X للـ List L. لو X موجود أصلاً، متضفش ومترجعش نفس الـ List.

add(X, L, L) :- member(X, L), !.
add(X, L, [X|L]).

تجارب:

?- add(a, [b, c], L).       % a مش موجود ➔ L = [a, b, c]
?- add(X, [b, c], L).       % X = b, L = [b, c]
?- add(a, [b, c, X], L).    % X = a, L = [b, c, a]
?- add(a, [a, b, c], L).    % a موجود ➔ L = [a, b, c]

لو شيلنا الـ Cut (Duplicate):

?- add(a, [a, b, c], L).
L = [a, b, c] ;     % الأول: ممنوعش التكرار
L = [a, a, b, c].   % التاني: أضاف العنصر عادي
قبل ما تدخل علي الامتحان حل امثلة المحاضرة والسكاشن من هنا : Chapter 6 - Practice

Nour Eldeen Mahmoud