تمرينات مشكلة التباطؤ الموزون للآلة الواحدة - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

سؤال 1: صف استراتيجيتين مُختلفتين (مبادلة، انعكاس، تحويل، إلخ) لأسلوب البحث المحلي لحل مشكلة التباطؤ الموزون للآلة الواحدة.

الإجابة: س1: المبادلة (Swap): تبديل مهمتين. التحويل (Insertion): نقل مهمة.

خطوات الحل:

1. **الشرح:** لنفهم هذا السؤال. يتحدث عن مشكلة جدولة في بحوث العمليات، وهي مشكلة التباطؤ الموزون للآلة الواحدة. الفكرة هنا هي أن لدينا مجموعة من المهام (أو الوظائف) التي يجب جدولتها على آلة واحدة، والهدف هو تقليل مجموع التكاليف المرتبطة بتأخير إنجاز هذه المهام. أسلوب البحث المحلي هو طريقة لحل مثل هذه المشكلات، حيث نبدأ بجدول أولي ثم نحاول تحسينه خطوة بخطوة عن طريق إجراء تغييرات صغيرة عليه. السؤال يطلب وصف استراتيجيتين مختلفتين لهذا الأسلوب. إحدى الاستراتيجيات الشائعة هي **المبادلة (Swap)**. في هذه الاستراتيجية، نأخذ جدولاً ونقوم بتبديل مواقع مهمتين فيه. على سبيل المثال، إذا كان الجدول هو [المهمة أ، المهمة ب، المهمة ج]، فقد نقوم بتبديل المهمة أ مع المهمة ج لنحصل على جدول جديد [المهمة ج، المهمة ب، المهمة أ]. ثم نقارن أداء الجدول الجديد بالجدول القديم لنرى إذا كان أفضل. استراتيجية أخرى هي **التحويل (Insertion)**. هنا، نأخذ مهمة من موضعها في الجدول وننقلها إلى موضع آخر. مثلاً، في الجدول [أ، ب، ج، د]، قد نأخذ المهمة ج ونضعها بين أ وب، لتصبح [أ، ج، ب، د]. هذا يخلق جدولاً جديداً مختلفاً عن مجرد التبديل البسيط. إذن، الإجابة هي: **المبادلة (Swap): تبديل مهمتين. التحويل (Insertion): نقل مهمة.**

سؤال 2: كم عدد الجداول الممكنة (الحلول) لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام؟

الإجابة: س2: عدد الترتيبات = !9 = 362880 جدولاً.

خطوات الحل:

1. **الخطوة 1 (المفهوم):** نتذكر أن مشكلة التباطؤ الموزون للآلة الواحدة تتطلب ترتيب (أو جدولة) مجموعة من المهام على آلة واحدة. كل جدول ممكن يمثل ترتيباً معيناً لهذه المهام. **الخطوة 2 (التطبيق):** وبتطبيق هذا على السؤال، لدينا تسع مهام متميزة. السؤال يسأل عن عدد الجداول الممكنة (أي عدد الحلول أو الترتيبات الممكنة) لهذه المهام التسع. في الرياضيات، عدد الطرق لترتيب (n) عناصر متميزة هو معامل المضروب (Factorial)، ويرمز له ب (n!). **الخطوة 3 (الحل):** لذلك، عدد الترتيبات الممكنة لتسع مهام هو 9! (تسعة مضروب). لنحسب: 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 لنحسب خطوة بخطوة: 9 × 8 = 72 72 × 7 = 504 504 × 6 = 3024 3024 × 5 = 15120 15120 × 4 = 60480 60480 × 3 = 181440 181440 × 2 = 362880 362880 × 1 = 362880 **الخطوة 4 (النتيجة):** إذن، عدد الجداول الممكنة = **362880 جدولاً**.

سؤال 1: صف استراتيجيتين مختلفتين (مبادلة، انعكاس، تحويل، إلخ) لأسلوب البحث المحلي لحل مشكلة التباطؤ الموزون للآلة الواحدة.

• أ) استراتيجية المبادلة العشوائية و استراتيجية الانعكاس
• ب) استراتيجية الإدراج و استراتيجية الحذف
• ج) استراتيجية التقسيم و استراتيجية الدمج
• د) استراتيجية التبديل و استراتيجية الاستبدال

الإجابة الصحيحة: استراتيجية المبادلة العشوائية: تبادل مواقع مهمتين عشوائياً في الجدول الزمني لاستكشاف حلول جديدة. استراتيجية الانعكاس: عكس ترتيب مجموعة متتالية من المهام في الجدول الزمني لتغيير الترتيب المحلي.

الشرح: استراتيجية المبادلة العشوائية تقوم بتبديل موقعي مهمتين عشوائياً في تسلسل الجدول الزمني، مما يسمح باستكشاف مناطق جديدة من فضاء الحلول. استراتيجية الانعكاس تقلب ترتيب مجموعة متجاورة من المهام، مما يمكن أن يحسن التباطؤ الموزون عن طريق إعادة ترتيب المهام ذات الأوزان والمواعيد النهائية المختلفة.

تلميح: فكر في كيفية تعديل ترتيب المهام في جدول زمني لتحسين التباطؤ الموزون.

سؤال 2: كم عدد الجداول الممكنة (الحلول) لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام؟

• أ) 362880 جدولاً
• ب) 81 جدولاً
• ج) 512 جدولاً
• د) 40320 جدولاً

الإجابة الصحيحة: 362880 جدولاً ممكناً (9! = 362880).

الشرح: عدد الجداول الممكنة لتسع مهام يساوي عدد التباديل (الترتيبات) المختلفة لتسع مهام متميزة، وهو 9 عاملي (9!) = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362880. كل جدول يمثل ترتيباً فريداً للمهام على الآلة الواحدة.

تلميح: تذكر أن كل مهمة يجب أن تكون في موضع واحد فقط في الجدول، ولا يمكن تكرار المهام.

اذكر استراتيجيتين مختلفتين (مثل مبادلة، انعكاس، تحويل) لحل مشكلة التباطؤ الموزون للآلة الواحدة في سياق البحث المحلي.

الإجابة: من الاستراتيجيات الممكنة لحل مشكلة التباطؤ الموزون للآلة الواحدة باستخدام البحث المحلي: 1. استراتيجية المبادلة (Swapping): حيث يتم تبديل ترتيب مهمتين متجاورتين إذا كان ذلك يؤدي إلى تحسين في دالة الهدف. 2. استراتيجية الانعكاس (Reversing): حيث يتم عكس تسلسل مجموعة من المهام المتجاورة في الجدول إذا كان ذلك يحسن دالة الهدف.

الشرح: البحث المحلي هو تقنية لحل مشاكل التحسين تتضمن البدء من حل أولي وإجراء تغييرات صغيرة تدريجياً للاقتراب من الحل الأمثل. استراتيجيتي المبادلة والانعكاس هما من الأساليب الشائعة لإحداث هذه التغييرات في سياق جدولة المهام.

تلميح: فكر في التغييرات التي يمكن إجراؤها على ترتيب المهام لتحسين التباطؤ الكلي.

كم عدد الجداول الممكنة (الحلول) لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام؟

الإجابة: عدد الجداول الممكنة (الحلول) لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام هو 9! (تسعة مضروب)، والذي يساوي 362,880 جدولاً ممكناً.

الشرح: في مشكلة التباطؤ الموزون للآلة الواحدة، الهدف هو إيجاد الترتيب الأمثل للمهام. عدد الترتيبات المختلفة لتسع مهام على آلة واحدة هو ببساطة عدد التباديل الممكنة لهذه المهام، والذي يُحسب باستخدام المضروب.

تلميح: تذكر أن عدد الطرق لترتيب 'ن' من العناصر المختلفة هو 'ن' مضروب (n!).