المهارات الرقمية، الصف الثاني عشر · الذكاء الاصطناعي

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

أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.

أهم الأفكار

  1. 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 أقرب.
  2. اشتقاق الاقتران من تبسيط المشكلة تُستمدّ الاقترانات الاستدلالية من النماذج المبسَّطة للمشكلة الأصلية: نزيل قيدًا فتصبح المشكلة أسهل، ثم نأخذ تكلفة حلّها تقديرًا للتكلفة الأصلية. في اللعبة الأصلية لا يتحرك المربع إلا إلى مكان مجاور فارغ. إذا أزلنا شرط الانتقال إلى مكان مجاور فقط (يبقى أن يكون المكان فارغًا) أمكن تحريك المربع إلى أي مكان بحركة واحدة، فتصير كل حركة تضع مربعًا واحدًا في الفراغ، ولا يقل عدد الحركات عن عدد المربعات التي ليست في مواضعها، أي H1. وفي مثالنا تساوي التكلفة 8، وهي قيمة H1 نفسها.
  3. إزالة جميع القيود إذا أزيلت كل القيود (يتحرك أي مربع إلى أي موضع في حركة واحدة) فإن كل مربع غير موضعه يحتاج حركة واحدة بالضبط، فنتيجة الاقتران هي عدد المربعات الخاطئة، أي H1، وتصير هي التكلفة الفعلية للمشكلة المبسَّطة (8 في مثالنا). أما H2 فيحسب مسافات عدة حركات لكل مربع فلا يمثل هذه المشكلة، وتبقى القيمة 8 أبعد عن التكلفة الأصلية (26) من 18، فتفحص الخوارزمية عقدًا أكثر. فالمسألة الأبسط تعطي تقديرًا أضعف.
  4. مزايا A* وعيوبها المزايا: من أكثر خوارزميات البحث استخدامًا وكفاءة؛ تجمع التكلفة الفعلية والمقدّرة (f = g + h) فتقلّل تكلفة الحل الإجمالية؛ تجد الحل الأمثل إذا كان h مقبولًا ومتسقًا؛ تُستخدم في أنظمة الملاحة وحل الألغاز والألعاب والبحث في البيانات الضخمة. العيوب: تحتاج اقترانًا استدلاليًّا جيدًا لا يبالغ في التقدير؛ تكلفة البحث الشامل قد تتفجّر (في لعبة الأرقام تبلغ نحو 3.1×10^10 حالة عند عمق 22)؛ وتحتفظ بعدد كبير من العقد، ولذلك طُوّرت IDA* لتستهلك ذاكرة أقل.

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

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

من اُدرُس: odrosai.com/ar/subjects/JO-DIGI-G12/units/4/digi12-u4_l3_heuristic_astar_more

بدك تتأكد إنك فاهم؟

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