الدرس 5 من 9

تلخيص درس الاقتران الاستدلالي

الدرس باختصار

عندما تكون الحالات التي يمكن أن يمر بها البرنامج كثيرة جدًّا، لا يكفي أن نجرّب كل الاحتمالات واحدًا بعد الآخر. الاقتران الاستدلالي (Heuristic Function) يعطي كل حالة رقمًا يقدّر مدى قربها من الهدف، فيُوجَّه البحث نحو المسارات الواعدة ويوفَّر الوقت والذاكرة. نتعلم كيف يُستعمل مع خوارزمية البحث بالأفضلية (A* Search) ومع لعبة الأرقام الثمانية (8-Puzzle) والألعاب بين لاعبين.

مصطلحات الدرس

كل مصطلحات الدرس بصفحة وحدة · راجعها ببطاقات

الاقتران الاستدلالي (Heuristic Function)
اقتران يحوّل حالة في المشكلة إلى رقم يقدّر مدى جودتها أو قربها من الهدف، ويُستعمل لتوجيه البحث.
التكلفة الفعلية g(n)
تكلفة المسار الذي قُطع فعلًا من الحالة الابتدائية (الجذر) إلى العقدة n.
التكلفة المقدّرة h(n)
تقدير لتكلفة أرخص مسار من العقدة n إلى العقدة الهدف، وتساوي صفرًا عند الهدف نفسه.
اقتران التقييم f(n)
f(n)=g(n)+h(n)f(n)=g(n)+h(n): التكلفة المقدّرة لأرخص مسار يمر بالعقدة n.
القبول (Admissibility)
شرط أن لا يبالغ h(n) في تقدير التكلفة الحقيقية للوصول إلى الهدف، أي أن يكون تقديرًا متفائلًا.
الاتساق (Consistency)
شرط أقوى من القبول (ويسمى الاطّراد Monotonicity): تقدير العقدة لا يزيد على تكلفة الانتقال إلى ابنها مضافًا إليها تقدير الابن.
MAX و MIN
في الألعاب بين لاعبين، يحاول MAX رفع قيمة الاقتران التقييمي، ويحاول MIN خفضها.

أهم الأفكار

ورقة مراجعة للطباعة

فكرة الاستدلال وفائدته

الاستدلال نصيحة تكون غالبًا فعّالة: نحوّل الحالة إلى رقم، ثم نختار المسارات التي يبدو أن فرصة نجاحها أكبر. هذا يقلّل عدد الحالات التي نفحصها ويوفّر الوقت والذاكرة، ويسمح بتجاهل (تقليم) أجزاء من شجرة البحث لا تغيّر القرار النهائي. مثال: الروبوت في المتاهة من دون استدلال يوسّع العقد في كل الاتجاهات، ومعه يتجه نحو الأقرب إلى الهدف.

ثلاثة أنواع من المشكلات

المشكلات التي تحتاج إلى بحث استدلالي ثلاثة أنواع: إيجاد مسار بوكيل واحد من الحالة الابتدائية إلى الهدف بأقصر مسار، والألعاب التي يتنافس فيها طرفان، ومشكلات إرضاء القيود (Constraint-Satisfaction) التي نبحث فيها عن حالة تحقق مجموعة قيود.

خوارزمية A* واقتران التقييم

في كل خطوة نحسب لكل عقدة مرشحة f(n)=g(n)+h(n)f(n)=g(n)+h(n)، ثم نكمل من العقدة التي لها أصغر f بين كل العقد المفتوحة (وليس بين أبناء العقدة الأخيرة فقط). إذا ظهرت عقدة ميتة (لا أبناء لها) أو عقدة زُرتها سابقًا تجاهلناها، وعدنا إلى أصغر f بين العقد المتبقية. ننتهي عند الوصول إلى الهدف، وتكون f عنده تساوي g لأن h=0h=0.

شرطا الحل الأمثل

للحصول على المسار الأمثل يجب أن يكون الاقتران h مقبولًا (لا يبالغ في تقدير التكلفة، كالخط المستقيم بين نقطتين فهو أقصر مسار ممكن بينهما) ومتسقًا. في لعبة الأرقام الثمانية يُحسب h بطريقتين: H1 عدد المربعات الموجودة في أماكن خاطئة، وH2 مجموع المسافات الأفقية والعمودية (دون القُطرية) لكل مربع عن موضعه الهدف. كلتاهما مقبولتان لأن كل مربع يحتاج إلى حركة واحدة على الأقل، لكن H2 أقرب إلى التكلفة الحقيقية.

الألعاب بين لاعبين

في الشطرنج و XO يقيّم الاقتران وضع اللوحة برقم، فمثلًا يمكن طرح مجموع قيم قطع الخصم من مجموع قيم قطع الحاسوب مع إعطاء القطع أهمية مختلفة (الوزير أعلى من الجندي). القيم الموجبة الكبيرة تعني موقفًا قويًّا للاعب MAX، والقيم السالبة الكبيرة موقفًا قويًّا للاعب MIN.

أمثلة محلولة

مثال 1: حساب f للمدينتين الأوليين

تنتقل ندى من المدينة I إلى المدينة الهدف T. يمكن الذهاب من I إلى A بتكلفة 2 أو إلى B بتكلفة 5، وتقدير h للمدينة A هو 10.4 وللمدينة B هو 8.9. أيهما تختار A* أولًا؟ احسب f للمدينة A.

اعرض الحل
  1. نحسب f(A)=g(A)+h(A)=2+10.4=12.4f(A)=g(A)+h(A)=2+10.4=12.4.
  2. نحسب f(B)=5+8.9=13.9f(B)=5+8.9=13.9.
  3. نقارن: 12.4 أقل من 13.9، فنكمل من المدينة A.

الجواب: f(A)=12.4f(A)=12.4 وهي الأصغر، فنكمل من A

اختبر حالك

1. في A*، عقدة g(n)=10 و h(n)=3.0. ما قيمة f(n)؟

2. في لعبة الأرقام الثمانية بهدف: الفراغ ثم 1 و2 في الصف الأول، ثم 3 و4 و5، ثم 6 و7 و8. وُضع الصف الأخير في حالة معينة هكذا: 7 ثم 8 ثم 6، وباقي المربعات في مواضعها. ما قيمة H2 (مجموع المسافات الأفقية والعمودية)؟

3. في الحالة نفسها للسؤال السابق، ما قيمة H1 (عدد المربعات الموجودة في أماكن خاطئة)؟

4. ما اسم الشرط الذي يعني أن الاقتران h لا يبالغ في تقدير تكلفة الوصول إلى الهدف؟

باقي الدرس للمسجّلين، ومجاناً

  • 3 أمثلة محلولة كمان
  • 4 أخطاء شائعة وكيف تتجنّبها
  • إجابات «اختبر حالك» مع الشرح
سجّل مجاناً وشوف الدرس كامل

جاهز تتدرّب؟

11 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.

تدرّب على 11 سؤال من هالدرس مجانًا