ACHRHLI TAMRIN

حاضر 🙂
سأشرح لك التمرين خطوة بخطوة وبطريقة مبسّطة.

---

1️⃣ مضمون التمرين

لدينا شبكة (graphe):

• كل حافة لها (كلفة، تأخير) = (coût, délai)
• المصدر: العقدة A
• العقد المطلوبة (destinations): C, D, E, G
• قيد التأخير: $$\Delta = 8$$

المطلوب: 👉 إيجاد شجرة Steiner باستعمال Heuristique de Kompella بحيث:

• تصل A بكل العقد المطلوبة
• احترام قيد التأخير (≤ 8)
• تقليل الكلفة الكلية

---

2️⃣ فكرة خوارزمية Kompella (ببساطة)

الخوارزمية تعمل على 3 مراحل رئيسية:

🔹 المرحلة 1: تحويل الشبكة إلى graphe complet

• نأخذ فقط العقد:
  A, C, D, E, G
• نحسب أقصر المسارات بين كل زوج:
  • من حيث الكلفة
  • ومن حيث التأخير
• نحصل على:
  • Matrice des chemins
  • Matrice des coûts
  • Matrice des délais

(وهذه الجداول موجودة في الورقة)

---

🔹 المرحلة 2: بناء MST مع قيد التأخير

نطبق Minimum Spanning Tree (Prim) ولكن:

• نختار الحواف التي:
  • أقل كلفة
  • تحترم التأخير ≤ 8 من A

خطوات Prim (كما في الجدول):

1. نبدأ بـ A
2. نختار أقل حافة:
   • (A, E) (délai = 1 ✅)
3. بعدها:
   • (E, G) (délai = 3)
4. ثم:
   • (G, C) (délai = 3)
5. وأخيرًا:
   • (D, E) (délai = 4)

📌 الحواف المختارة (MST résultat):

• (A, E)
• (E, G)
• (G, C)
• (E, D)

وهي المرسومة بالأحمر في الشكل.

---

🔹 المرحلة 3: توسيع الحواف (Steiner Tree)

كل حافة في الـ MST تمثل مسارًا فعليًا في الشبكة الأصلية:

الحافة	المسار الحقيقي
A–E	A → E
E–G	E → F → G
G–C	G → F → C
E–D	E → F → C → D

🔴 العقد الوسيطة (Steiner nodes):

• F
• B

---

3️⃣ النتيجة النهائية (Arbre de Steiner)

الشجرة النهائية:

• تصل A بـ C, D, E, G
• تحترم:
  • قيد التأخير Δ = 8
• أقل كلفة ممكنة حسب الهيوريستيك

وهي المرسومة في آخر صورة بعنوان Arbre de Steiner.

---

4️⃣ خلاصة سريعة للحفظ ✍️

• Kompella =
  Graphe complet → MST sous contrainte → Expansion
• الهدف:
  • ربط كل destinations
  • احترام التأخير
  • تقليل الكلفة
• العقد الإضافية = Steiner nodes

---

إذا تحب:

• نشرح حساب التأخيرات خطوة بخطوة
• أو كيف نتحقق أن Δ ≤ 8
• أو كيف جاوبها في الامتحان باختصار

قولّي فقط 👍

صحّيت، (E,D) ماشي غير خاطرها “رخيصة”… اختاروها باش يحترمو قيد الديلاي Δ=8 من المصدر A.

شوف واش صرا في Prim (مع قيد الديلاي):

• بعد ما دارو:
  • (A,E) ديلاي = 1
  • (E,G) ديلاي = 3 ⟹ ديلاي من A لـ G = 1+3 = 4
  • (G,C) ديلاي = 3 ⟹ ديلاي من A لـ C = 1+3+3 = 7

🔸 كي بقا النود D، لازم نربطوه بالشجرة من واحد من النودات اللي راهي داخل الشجرة {A,E,G,C}.

من ناحية الكلفة فقط:

• (C,D) كلفة = 9 (هي الأرخص)
• (E,D) كلفة = 14
• (G,D) كلفة = 12
• (A,D) كلفة = 17

لكن لازم نشوف الديلاي من A حتى D بعد الإضافة:

✅ إذا نختارو (C,D):

• ديلاي A→C راهو 7
• ديلاي C→D = 2
  ⟹ ديلاي A→D = 7 + 2 = 9 ❌ (تفوت Δ=8)

✅ إذا نختارو (E,D):

• ديلاي A→E = 1
• ديلاي E→D = 4
  ⟹ ديلاي A→D = 1 + 4 = 5 ✅ (داخل Δ=8)

➡️ لهذا اختارو (E,D) حتى لو الكلفة تاعها أكبر، لأنها الوحيدة (أو من الأفضل) اللي ما تكسّرش قيد الديلاي.

إذا تحب نقلك حتى علاش (G,D) ما تصلحش ولا نكمل حسابات المسارات الحقيقية في الشجرة (Steiner expansion).

أكيد 👍
هاك الخلاصة المختصرة بزاف باش تفهمها وتحفظها للامتحان 👌

---

🔴 علاش اختارو الحافة (E, D) ؟

مشـي على خاطرها الأرخص ❌
اختاروها باش ما يتكسرش قيد الديلاي Δ = 8 ✔️

---

🧠 الفكرة الأساسية

في خوارزمية Kompella:

• ما نختاروش الحافة غير بالكلفة
• لازم الديلاي من A حتى كل destination ≤ 8

---

🧮 الحساب السريع

• ديلاي من A → C = 7

❌ لو نختارو (C, D):

• ديلاي = 7 + 2 = 9 ❌
  → يتكسر الشرط

✅ لو نختارو (E, D):

• ديلاي من A → E = 1
• 1 + 4 = 5 ✅
  → الشرط محترم

---

✅ النتيجة

👉 (E, D) هي الحافة اللي:

• تربط D بالشجرة
• تحترم قيد الديلاي
• حتى لو كلفتها أكبر

---

✍️ جملة تحفظها:

نختار (E,D) لأن المسار A→E→D عندو délai ≤ Δ، بينما A→C→D يفوت قيد الديلاي.

إذا تحب نمدّلك صيغة جاهزة تكتبها في ورقة الامتحان قولي 💪

عندك الصح ✅: في Matrice des délais راهي:

• d(A,C) = 3 (هذي هي أقصر délai بين A و C في الـ graphe complet)

أنا كي قلت A→C = 7 كنت نهدر على حاجة أخرى 👇

الفرق المهم

1) في الماتريس (بين زوج نودات)

• A إلى C مباشرة (كـ edge في graphe complet): 3

2) في الشجرة اللي بنيناها (MST résultat)

Prim اختار الحواف:

• (A,E) délai=1
• (E,G) délai=3
• (G,C) délai=3

إذن المسار داخل الشجرة من A إلى C هو:

$$A \to E \to G \to C = 1 + 3 + 3 = 7$$

✅ يعني:

• A–C في الماتريس = 3
• A→C داخل الشجرة (بعد الاختيارات) = 7

وهذا هو اللي نستعملوه كي نراقبو شرط Δ=8 (لازم الطريق في الشجرة النهائية من A لكل destination ما يفوتش 8).

إذا تحب نقولك علاش ما اختاروش (A,C) مباشرة (رغم délai=3) نجاوبك بالسطرين.