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

الكتاب: كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 | المادة: الذكاء الإصطناعي | المرحلة: الصف 12 | الفصل الدراسي: 1

الدولة: المملكة العربية السعودية | المنهج: المنهج السعودي - وزارة التعليم

الدرس: أنشئ دالة خوارزمية حل القوة المفرطة لمشكلة البائع المتجول

📚 معلومات الصفحة

الكتاب: كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 | المادة: الذكاء الإصطناعي | المرحلة: الصف 12 | الفصل الدراسي: 1

الدولة: المملكة العربية السعودية | المنهج: المنهج السعودي - وزارة التعليم

نوع المحتوى: تمارين وأسئلة

مستوى الصعوبة: متوسط

📝 ملخص الصفحة

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

يبدأ المقطع البرمجي باستيراد مكتبة itertools لإنشاء التباديل، ثم يحدد دالة brute_force_solver التي تأخذ مصفوفة المسافات ومعرفات المواقع وموقع البداية والنهاية. يجب على الطالب إكمال الأجزاء المتعلقة باستبعاد موقع البداية والنهاية، وتوليد جميع المسارات الممكنة، وحساب المسافات باستخدام المصفوفة.

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

📋 المحتوى المنظم

📖 محتوى تعليمي مفصّل

5

نوع: QUESTION

أنشئ دالة خوارزمية حل القوة المفرطة لمشكلة البائع المتجول، من خلال إكمال المقطع البرمجي التالي بحيث تظهر الدالة المسار الأفضل والمسافة الإجمالية المثلى:

Python Code Snippet for Brute-Force Solver

نوع: محتوى تعليمي

from itertools import permutations def brute_force_solver(dist_matrix, location_ids, startstop): # excludes the startstop location location_ids = ________ - {_________} # generates all possible routes (location permutations) all_routes = _________ (_________ ) best_distance = float('inf') # initializes to the highest possible number best_route = None # best route so far, initialized to None for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc = _________ # current location for next_loc in route: distance += _________ [curr_loc, next_loc] # adds the distance of this step curr_loc = _________ # goes the next location distance += _________ [curr_loc, _________ ] # goes to # back to the startstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route # adds the startstop location at the beginning and end of the best route and returns return [startstop] + list(best_route) + [startstop], best_distance

نوع: METADATA

وزارة التعليم Ministry of Education 2023 - 1447

نوع: METADATA

296

📄 النص الكامل للصفحة

--- SECTION: 5 --- أنشئ دالة خوارزمية حل القوة المفرطة لمشكلة البائع المتجول، من خلال إكمال المقطع البرمجي التالي بحيث تظهر الدالة المسار الأفضل والمسافة الإجمالية المثلى: --- SECTION: Python Code Snippet for Brute-Force Solver --- from itertools import permutations def brute_force_solver(dist_matrix, location_ids, startstop): # excludes the startstop location location_ids = ________ - {_________} # generates all possible routes (location permutations) all_routes = _________ (_________ ) best_distance = float('inf') # initializes to the highest possible number best_route = None # best route so far, initialized to None for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc = _________ # current location for next_loc in route: distance += _________ [curr_loc, next_loc] # adds the distance of this step curr_loc = _________ # goes the next location distance += _________ [curr_loc, _________ ] # goes to # back to the startstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route # adds the startstop location at the beginning and end of the best route and returns return [startstop] + list(best_route) + [startstop], best_distance وزارة التعليم Ministry of Education 2023 - 1447 296

✅ حلول أسئلة الكتاب الرسمية

عدد الأسئلة: 9

سؤال س:(1): location_ids = ________ - {_________}

الإجابة: set)location_ids(

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** في لغة بايثون، عند استخدام معامل الطرح (-) لاستبعاد عناصر من مجموعة، يجب أن تكون البيانات من نوع "مجموعة" (set).
  2. **الخطوة 2 (التطبيق):** بما أننا نريد طرح نقطة البداية من قائمة المعرفات، يجب أولاً تحويل القائمة الأصلية إلى نوع set لتمكين العمليات المنطقية عليها.
  3. **الخطوة 3 (النتيجة):** لذلك نستخدم الدالة المحولة: **set(location_ids)**

سؤال س:(2): location_ids = ________ - {_________}

الإجابة: startstop

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** الفكرة هنا هي تجهيز قائمة المواقع التي سيتم المرور بها عبر استبعاد نقطة الانطلاق والعودة من القائمة الكلية.
  2. **الخطوة 2 (التطبيق):** المتغير الذي يمثل نقطة البداية والنهاية في الكود هو الذي يجب وضعه داخل أقواس المجموعة ليتم طرحه من المجموعة الكلية.
  3. **الخطوة 3 (النتيجة):** إذن القيمة المطلوبة هي: **startstop**

سؤال س:(3): all_routes = ________(__________)

الإجابة: permutations

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** لإيجاد أقصر مسار في مسائل التوصيل، نحتاج غالباً لتوليد كافة التباديل الممكنة لترتيب الزيارات.
  2. **الخطوة 2 (التطبيق):** في مكتبة itertools البرمجية، الدالة المسؤولة عن إيجاد كافة الترتيبات الممكنة لمجموعة من العناصر تُسمى التباديل.
  3. **الخطوة 3 (النتيجة):** لذلك الكلمة الصحيحة هي: **permutations**

سؤال س:(4): all_routes = ________(__________)

الإجابة: location_ids

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** دالة التباديل تحتاج إلى مدخلات (مجموعة العناصر) لتقوم بتبديل أماكنها وتوليد المسارات.
  2. **الخطوة 2 (التطبيق):** العناصر التي نريد تبديل ترتيبها هي معرفات المواقع التي قمنا بتجهيزها سابقاً في المتغير المخصص لها.
  3. **الخطوة 3 (النتيجة):** إذن المدخل الصحيح للدالة هو: **location_ids**

سؤال س:(5): curr_loc = ________ # current location

الإجابة: startstop

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** قبل البدء في حساب مسافة أي مسار، يجب تحديد نقطة الانطلاق التي سيبدأ منها البرنامج الحساب.
  2. **الخطوة 2 (التطبيق):** الموقع الحالي (curr_loc) في بداية الرحلة يجب أن يكون هو نفسه نقطة البداية المحددة مسبقاً.
  3. **الخطوة 3 (النتيجة):** لذلك الإجابة هي: **startstop**

سؤال س:(6): distance += ________[curr_loc, next_loc] # adds the distance of this step

الإجابة: dist_matrix

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** لحساب المسافة التراكمية، نحتاج للرجوع إلى جدول أو مصفوفة تحتوي على المسافات بين كل نقطتين.
  2. **الخطوة 2 (التطبيق):** يتم الوصول للمسافة بين الموقع الحالي والموقع التالي عن طريق استدعاء المصفوفة التي تخزن هذه البيانات باستخدام الإحداثيات [curr_loc, next_loc].
  3. **الخطوة 3 (النتيجة):** اسم هذه المصفوفة هو: **dist_matrix**

سؤال س:(7): curr_loc = ___________ # goes the next location

الإجابة: next_loc

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** بعد الانتقال من موقع إلى آخر، يجب تحديث قيمة "الموقع الحالي" لكي تصبح هي الموقع الذي وصلنا إليه للتو.
  2. **الخطوة 2 (التطبيق):** بما أننا انتقلنا إلى الموقع التالي (next_loc)، فإنه يصبح هو الموقع الحالي في الخطوة القادمة من الحلقة التكرارية.
  3. **الخطوة 3 (النتيجة):** إذن الإجابة هي: **next_loc**

سؤال س:(8): distance += ____________[curr_loc, ________] # goes to back to the startstop location

الإجابة: dist_matrix

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** في نهاية المسار، يجب إضافة المسافة الأخيرة التي تربط بين آخر موقع تم زيارته وبين نقطة العودة.
  2. **الخطوة 2 (التطبيق):** للحصول على هذه القيمة، نستخدم مرة أخرى مصفوفة المسافات التي تُخزن الأبعاد بين النقاط.
  3. **الخطوة 3 (النتيجة):** لذلك نكتب: **dist_matrix**

سؤال س:(9): distance += ____________[curr_loc, ________] # goes to back to the startstop location

الإجابة: startstop

خطوات الحل:

  1. **الخطوة 1 (المفهوم):** الجزء الأخير من حساب المسافة الكلية هو العودة من آخر موقع (curr_loc) إلى نقطة البداية الأصلية لإغلاق المسار.
  2. **الخطوة 2 (التطبيق):** نقطة العودة النهائية التي بدأنا منها هي المتغير الذي يمثل البداية والنهاية في النظام.
  3. **الخطوة 3 (النتيجة):** إذن القيمة المكملة للمصفوفة هي: **startstop**

📝 أسئلة اختبارية

عدد الأسئلة: 7

سؤال 5: أنشئ دالة خوارزمية حل القوة المفرطة لمشكلة البائع المتجول، من خلال إكمال المقطع البرمجي التالي بحيث تظهر الدالة المسار الأفضل والمسافة الإجمالية المثلى:

الإجابة الصحيحة: انظر الأسئلة الفرعية

الشرح: هذا سؤال رئيسي يحتوي على أسئلة فرعية تتعلق بإكمال الكود البرمجي

تلميح: راجع الأسئلة الفرعية أدناه لإكمال الأجزاء الناقصة في الكود

سؤال 5: location_ids = ________ - {_________}

  • أ) location_ids = location_ids - {startstop}
  • ب) location_ids = location_ids - {0}
  • ج) location_ids = set(location_ids) - {startstop}
  • د) location_ids = location_ids.remove(startstop)

الإجابة الصحيحة: location_ids = location_ids - {startstop}

الشرح: يجب استبعاد موقع البداية والنهاية من قائمة المواقع المراد ترتيبها، حيث سيتم إضافته في النهاية

تلميح: فكر في أننا نريد توليد جميع التباديل للمواقع باستثناء موقع البداية والنهاية

سؤال 5: all_routes = _________ (_________ )

  • أ) all_routes = permutations(location_ids)
  • ب) all_routes = combinations(location_ids)
  • ج) all_routes = product(location_ids)
  • د) all_routes = list(permutations(location_ids))

الإجابة الصحيحة: all_routes = permutations(location_ids)

الشرح: يتم استخدام دالة permutations من مكتبة itertools لتوليد جميع التباديل الممكنة للمواقع

تلميح: تم استيراد itertools في بداية الكود، فكر في الدالة المناسبة منها

سؤال 5: curr_loc = _________

  • أ) curr_loc = startstop
  • ب) curr_loc = 0
  • ج) curr_loc = route[0]
  • د) curr_loc = location_ids[0]

الإجابة الصحيحة: curr_loc = startstop

الشرح: يبدأ المسار من موقع البداية والنهاية المحدد، ثم ينتقل إلى المواقع الأخرى

تلميح: ما هو الموقع الأول في المسار؟

سؤال 5: distance += _________ [curr_loc, next_loc]

  • أ) distance += dist_matrix[curr_loc, next_loc]
  • ب) distance += distance_matrix[curr_loc, next_loc]
  • ج) distance += matrix[curr_loc][next_loc]
  • د) distance += distances[curr_loc][next_loc]

الإجابة الصحيحة: distance += dist_matrix[curr_loc, next_loc]

الشرح: يتم إضافة المسافة بين الموقع الحالي والموقع التالي من مصفوفة المسافات

تلميح: ما هو المتغير الذي يحتوي على مسافات بين المواقع؟

سؤال 5: curr_loc = _________

  • أ) curr_loc = next_loc
  • ب) curr_loc = curr_loc
  • ج) curr_loc = route[index]
  • د) curr_loc = location_ids[index]

الإجابة الصحيحة: curr_loc = next_loc

الشرح: بعد الانتقال إلى الموقع التالي، يصبح الموقع الحالي هو الموقع التالي للخطوة القادمة

تلميح: ما هو المتغير الذي يمثل الموقع الذي انتقلنا إليه؟

سؤال 5: distance += _________ [curr_loc, _________ ]

  • أ) distance += dist_matrix[curr_loc, startstop]
  • ب) distance += dist_matrix[curr_loc, 0]
  • ج) distance += dist_matrix[curr_loc, route[0]]
  • د) distance += dist_matrix[curr_loc, location_ids[0]]

الإجابة الصحيحة: distance += dist_matrix[curr_loc, startstop]

الشرح: بعد زيارة جميع المواقع، يجب العودة إلى موقع البداية والنهاية، لذا نضيف المسافة من الموقع الأخير إلى startstop

تلميح: إلى أي موقع يجب العودة في نهاية المسار؟

🎴 بطاقات تعليمية للمراجعة

عدد البطاقات: 5 بطاقة لهذه الصفحة

ما هو الغرض الأساسي من دالة `brute_force_solver`؟

الإجابة: الغرض الأساسي هو إيجاد أقصر مسار ممكن لزيارة جميع المواقع المحددة مرة واحدة فقط، والعودة إلى نقطة البداية، باستخدام خوارزمية القوة المفرطة (Brute-Force).

الشرح: تُستخدم هذه الدالة لحل مشكلة البائع المتجول عن طريق تجربة جميع المسارات الممكنة واختيار الأقصر. هذا هو جوهر ما تفعله الخوارزمية.

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

اشرح كيفية عمل الجزء `location_ids = ________ - {_________}` في الدالة `brute_force_solver`.

الإجابة: يقوم هذا الجزء باستبعاد موقع البداية/النهاية (`startstop`) من مجموعة المواقع التي يجب زيارتها. ذلك لأن البائع يبدأ وينتهي في نفس الموقع، ولا يحتاج إلى توليد مسارات تشمله كجزء من الرحلة الداخلية.

الشرح: خوارزمية القوة المفرطة هنا تركز على توليد الترتيبات الممكنة للمواقع بين نقطة البداية والنهاية. استبعاد `startstop` يمنع تكرار حساب المسافات ويجعل عملية توليد المسارات أكثر كفاءة.

تلميح: ما هو الهدف من توليد جميع المسارات الممكنة؟ وما هو الموقع الذي يتم البدء والانتهاء منه في النهاية؟

ماذا تعني `all_routes = _________ (_________ )` في الدالة `brute_force_solver`؟

الإجابة: تعني هذه العبارة توليد جميع التباديل (الترتيبات الممكنة) للمواقع المتبقية بعد استبعاد موقع البداية/النهاية. هذه التباديل تمثل جميع المسارات المحتملة لزيارة المواقع.

الشرح: مكتبة `itertools`، وتحديداً دالة `permutations`، تُستخدم لتوليد جميع الترتيبات الممكنة لعناصر قابلة للتكرار. في هذا السياق، هي تولد كل المسارات الممكنة بين المواقع.

تلميح: ما هي الوظيفة التي توفرها مكتبة `itertools` لتوليد جميع الترتيبات الممكنة لعناصر مجموعة؟

اشرح الخطوات التي تحدث داخل حلقة `for route in all_routes:` لحساب مسافة كل مسار.

الإجابة: لكل مسار، يتم تهيئة المسافة الكلية بصفر. ثم يتم المرور على كل موقع تالٍ في المسار، وتُضاف المسافة بين الموقع الحالي والموقع التالي إلى المسافة الكلية. بعد زيارة جميع المواقع في المسار، تُضاف المسافة للعودة إلى موقع البداية/النهاية.

الشرح: تتبع الدالة المسار الحالي (curr_loc) وتنتقل إلى الموقع التالي (next_loc)، وتستخدم مصفوفة المسافات (`dist_matrix`) لحساب وتجميع المسافة لكل انتقال. هذه العملية تتكرر حتى اكتمال المسار والعودة إلى البداية.

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

ما هي القيمة الأولية للمتغير `best_distance` ولماذا؟

الإجابة: القيمة الأولية هي `float('inf')` (اللانهاية)، وذلك لضمان أن المسافة الأولى المحسوبة لأي مسار ستكون بالتأكيد أقل منها، مما يجعلها المسافة الأفضل الأولية. هذا يضمن أن أي مسار يتم تقييمه سيكون أفضل في البداية.

الشرح: تبدأ `best_distance` بقيمة كبيرة جداً (لانهاية) حتى يتمكن أي مسار يتم حسابه من أن يكون 'أفضل' منه في أول مقارنة. هذا يسمح للبرنامج بالبدء في تسجيل أقصر المسافات بشكل صحيح.

تلميح: عند البحث عن 'أفضل' شيء (مثل أقصر مسافة)، ما هي القيمة التي يجب أن تبدأ بها لتتأكد أن أي قيمة حقيقية ستكون أفضل منها؟