الدرس 6 من 9

تلخيص درس اشتقاق الاقترانات الاستدلالية للعبة الأرقام ومزايا A* وعيوبها

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

نتعمّق هنا في كيف تُشتق الاقترانات الاستدلالية للعبة الأرقام الثمانية من تبسيط المشكلة (إزالة بعض القيود أو كلها)، ثم نحصر مزايا خوارزمية A* وعيوبها.

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

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

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

أهم الأفكار

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

H1 وH2 في لعبة الأرقام

في اللعبة تتحرك المربعات بحركة واحدة في اتجاه مجاور للمربع الفارغ. للحالة الابتدائية (7 2 4 / 5 _ 6 / 8 3 1) والهدف (_ 1 2 / 3 4 5 / 6 7 8): H1 = عدد المربعات الخاطئة الموضع = 8 لأنها كلها خارج موضعها، وهو مقبول لأن كل مربع يحتاج حركة واحدة على الأقل. وH2 = مجموع مسافات المربعات: 3+1+2+2+2+3+3+2 = 18، وهو مقبول أيضًا لأن كل حركة تقرّب مربعًا واحدًا خطوة واحدة. الحل الفعلي يتطلب 26 حركة، فكلاهما أقل منه، لكن H2 أقرب.

اشتقاق الاقتران من تبسيط المشكلة

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

إزالة جميع القيود

إذا أزيلت كل القيود (يتحرك أي مربع إلى أي موضع في حركة واحدة) فإن كل مربع غير موضعه يحتاج حركة واحدة بالضبط، فنتيجة الاقتران هي عدد المربعات الخاطئة، أي H1، وتصير هي التكلفة الفعلية للمشكلة المبسَّطة (8 في مثالنا). أما H2 فيحسب مسافات عدة حركات لكل مربع فلا يمثل هذه المشكلة، وتبقى القيمة 8 أبعد عن التكلفة الأصلية (26) من 18، فتفحص الخوارزمية عقدًا أكثر. فالمسألة الأبسط تعطي تقديرًا أضعف.

مزايا A* وعيوبها

المزايا: من أكثر خوارزميات البحث استخدامًا وكفاءة؛ تجمع التكلفة الفعلية والمقدّرة (f = g + h) فتقلّل تكلفة الحل الإجمالية؛ تجد الحل الأمثل إذا كان h مقبولًا ومتسقًا؛ تُستخدم في أنظمة الملاحة وحل الألغاز والألعاب والبحث في البيانات الضخمة. العيوب: تحتاج اقترانًا استدلاليًّا جيدًا لا يبالغ في التقدير؛ تكلفة البحث الشامل قد تتفجّر (في لعبة الأرقام تبلغ نحو 3.1×10^10 حالة عند عمق 22)؛ وتحتفظ بعدد كبير من العقد، ولذلك طُوّرت IDA* لتستهلك ذاكرة أقل.

أمثلة محلولة

مثال 1: حساب H1 وH2

للحالة الابتدائية 7 2 4 / 5 _ 6 / 8 3 1 والهدف _ 1 2 / 3 4 5 / 6 7 8، احسب H1 وH2.

اعرض الحل
  1. H1: كل المربعات الثمانية في غير موضعها فتساوي 8.
  2. H2: مسافات المربعات 1 إلى 8 هي 3 و1 و2 و2 و2 و3 و3 و2 فمجموعها 18.
  3. الفعلي 26 وكلاهما أقل منه.

الجواب: H1 = 8، H2 = 18

اختبر حالك

1. ما قيمة H1 للحالة 7 2 4 / 5 _ 6 / 8 3 1 مع الهدف _ 1 2 / 3 4 5 / 6 7 8؟

2. ما الخوارزمية المحسَّنة التي تستهلك ذاكرة أقل من A*؟

3. ما الشرط الذي يجعل A* تجد الحل الأمثل؟

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

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

جاهز تتدرّب؟

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

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