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