المهارات الرقمية 12 فصل ثاني

الثاني عشر خطة جديدة

icon
الشرحالملخصأوراق العملحل اسئلة الدرسالنتاجاتالملفات

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

العناوين الرئيسة في هذا الدرس :

  • مفهوم الاقتران الاستدلالي
  • بناء اقترانات تقييمية للألعاب
  • تطبِيق خوارزمية البحث الشامل بالأفضلية (A* Search ) على لعبة لغز( الأرقام الثمانية ) 8 Puzzle

مفهوم الاقتران الاستدلالي (Heuristic Function)

  • يُرمز له بالرمز h(n) وهو اقتران يُستخدم لتقدير تكلفة المسار من الحالة الحالية إلى حالة الهدف.

  • يساعد هذا الاقتران خوارزمية البحث في اتخاذ قرارات ذكية من خلال اختيار المسار الذي يبدو أقرب للحل، بدلاً من البحث العشوائي

  • في الألعاب، يُستخدم لتقييم "جودة" الحالة الحالية ومدى قربها من الفوز. 

2. بناء الاقترانات التقييمية للألعاب

  • تُصمم هذه الاقترانات بناءً على خصائص اللعبة لتقدير المسافة المتبقية للوصول للهدف.

  • أمثلة على مقاييس التقييم (خاصة في لغز الأرقام)

  1. عدد البلاطات في غير مكانها الصحيح (Hamming Distance): حساب عدد الأرقام التي لا توجد في موقعها النهائي المفترض.
  2.  مسافة مانهاتن (Manhattan Distance): مجموع المسافات (أفقيًا ورأسيًا) التي يجب أن تتحركها كل بلاطة للوصول لمكانها الصحيح.

 

3. خوارزمية البحث الشامل بالأفضلية (A* Search)

تُعد من أكفأ خوارزميات البحث لأنها تجمع بين ميزتين:

1. تكلفة الوصول للحالة الحالية والتقدير الاستدلالي للوصول للهدف.

2. يعتمد الخوارزمية على المعادلة التالية لحساب الأولوية لكل عقدة:

f(n) = g(n) + h(n)

  • حيث أن g(n) هي التكلفة الفعلية من نقطة البداية إلى العقدة الحالية.

  • و h(n) هي القيمة التقديرية (الاستدلالية) من العقدة الحالية إلى الهدف.

تختار الخوارزمية دائماً العقدة التي تمتلك أقل قيمة لـ f(n) لتوسيعها.

4. تطبيق (A* Search)  على لعبة لغز الأرقام الثمانية (8-Puzzle)

تمثيل اللعبة: لوحة 3 \times 3 تحتوي على 8 أرقام ومربع فارغ، والهدف هو ترتيب الأرقام بالتسلسل الصحيح.

  • آلية العمل:

    1. تبدأ الخوارزمية من الحالة الابتدائية المبعثرة.

    2. تولد جميع التحركات الممكنة للمربع الفارغ (أعلى، أسفل، يمين، يسار).

    3. تحسب قيمة f(n) لكل تحرك ناتج باستخدام اقتران استدلالي (مثل مسافة مانهاتن)

    4. تنتقل للحالة التي تعطي أقل تكلفة إجمالية وتكرر العملية حتى الوصول لشكل اللوحة النهائي.

  • النتيجة: تضمن خوارزمية A* Search الوصول للحل بأقل عدد ممكن من الخطوات (المسار الأمثل) إذا كان الاقتران الاستدلالي دقيقاً.

( خوارزمية A* Search مثل الشخص الذي يستخدم "GPS"؛ فهو لا يعرف الطريق بالتفصيل، لكنه يمتلك دائماً تقديراً للوقت المتبقي ويختار أسرع مسار!)