الخوارزميات، والشبكات، والبرمجة الخطية
مُقدَّم| English | المعنى |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | الشجرة الممتدة الدنيا |
أرخص شبكة أو أقصر مسار؟
- يجب على مدرسة توصيل المباني بالكابلات. المسار الأقصر بين مبنيين ومسألة الشبكة الأرخص ككل هما مشكلتان مختلفتان.
- تدرس هذه الدرس شجرة التغطية الصغرى: شبكة متصلة خالية من الحلقات تربط كل رأس بأقل وزن إجمالي ممكن للأضلاع.
اختر البنية الرياضية
- تختار كروسال أضلاعاً بوزن متزايد مع تجنب الحلقات. يُحدث ديسترا أقصر مسافات مؤقتة من نقطة البداية. البرمجة الخطية تحسن دالة هدف خطية فوق منطقة صالحة؛ افحص الرؤوس والقيود الصحيحة عند الحاجة.
- حدد المدخلات المسموحة والوحدات قبل الحساب. يجب أن يعبر المعادلة عن العلاقة، وليس فقط تسجيل إدخال الآلة الحاسبة.
أعطى كل من خوارزميتي كروسكال وأقصر مسار الإجمالي 6 على الشبكة المثالية. لماذا لا يجعل ذلكهما قابلتين للتبديل؟
Difficulty 1/5 · 100 coins + a small bonus on first completion today
الأهداف مختلفة: شجرة التغطية connects جميع الرؤوس (n-1 حافة، بدون حلقات)، بينما يُمثّل أقصر مسار تحسين مسار واحد بين نقطة البداية والوجهة. تطابق الإجابات هنا عرضي.
اعمل على حالة تم فحصها
- تحقق من النتيجة مقابل الكميات الأولية. عوض في العلاقة الأصلية، أو قارن بين الرسم البياني والإجابة العددية عند الاستلزام.
للمواقع A,B,C,D والأضلاع AB=2، BC=3، AC=4، CD=1، BD=5، تختار كروسال CD، AB، BC لمجموع 6. المسار الأقصر من A إلى D هو A-B-C-D، أيضاً 6، لكن هذا التساوي عرضي. حدّث 3x+2y بشرط x+y≤4، x≤2، x,y≥0: أفضل موقع هو (2,2)، القيمة 10.
الخوارزميات، والشبكات، والبرمجة الخطية
يختار كروسكال الحواف بوزن متزايد مع تجنب وجود حلقات
قارن النموذج بالحالة المحلولة واشرح تغييراً واحداً.
أوجد وزن شجرة التغطية الصغرى للشبكة الموضحة في المثال.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
يختار خوارزمية كروسكال أوزان الحواف 1,2,3 بدون تكوين حلقة، مما يربط كل الرؤوس: المجموع الكلي 6.
اختبر طريقة مختصرة مغرية
- شجرة التغطية لا تحتوي على حلقات وتربط جميع الرؤوس. لا يتم استبعاد أكبر ضلع مفرد تلقائياً من كل حل مثلى. لا يمكن لخوارزمية أقصر مسار أن تستبدل خوارزمية شجرة التغطية الصغرى.
- عندما تفشل طريقة مختصرة، حدد الافتراض الذي تخالفه. احتفظ بالقيمة الدقيقة حتى التحويل النهائي المطلوب.
يجب أن يكون أقصر مسار بين موقعين أيضاً شجرة تغطية صغرى للشبكة بأكملها. هذا الادعاء خاطئ. اشرح أي تعريف أو افتراض يخالفه.
أوجد القيمة القصوى للدالة 3x + 2y لمنطقة الحل الممكنة في المثال.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
تحقق من الرؤوس الممكنة: النقطة (2,2) تعطي 3 × 2 + 2 × 2 = 10، وهي أكبر قيمة للهدف.
أقصر مسار بين رأسين يجب أن يكون أيضاً شجرة تغطية صغرى للشبكة بأكملها.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
شجرة التغطية لا تحتوي على دورات وتربط جميع الرؤوس. الحافة الأحادية الأكبر ليست مستبعدة تلقائياً من كل حل أمثل. لا يمكن لخوارزمية أقصر مسار أن تحل محل خوارزمية شجرة التغطية الصغرى.
تفسير موقف جديد
- للمسارات الحرجة، احسب وقت الحدث الأقدم والأحدث وحدد الأنشطة ذات الفاصلة الصفرية. حدد الوحدات وفسر الأمثل. الأرشيف الحالي لا يحتوي على أزواج D1، لذا لا تؤسس هذه المهام الأصلية بنك أوراق امتحانات D1 مراجعة.
- الحل الكامل يعطي النتيجة الرياضية ويشرح معناها. تحقق من إمكانية حدوثه في السياق المعلن.
كم عدد الحواف التي يحتويها شجرة تغطية تتكون من 4 رأساً؟
Difficulty 2/5 · 140 coins + a small bonus on first completion today
الشجرة ذات n من الرؤوس تحتوي على n-1 حافة، لذا تحتاج أربعة رؤوس إلى ثلاث حواف.
صوّغ كل خوارزمية مع قاعدتها.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
كل خوارزمية دقيقة لفئتها الخاصة من المسائل؛ تتبع القاعدة المذكورة، بما في ذلك التعامل مع التعادلات، هو ما يُمنح عليه الدرجات.
استخدم هذا في مسارك الدراسي
- رياضيات edexcel IAL؛ الوحدة الرسمية D1. يتم تحديد إثراء الوحدات الأخرى في مراجعة النطاق؛ ولا يعتبر شرطًا إضافيًا للدفع.
- قدم الطريقة قبل الإجابة النهائية، واستخدم قواعد الآلة الحاسبة والصيغ الورقية. راجع إجابة خاطئة عن طريق تحديد الخطوة الأولى غير الصالحة.
شبكة متصلة خالية من الدورات تربط كل رأس بأقل مجموع ممكن لأوزان الحواف. اختر العلاقة، ووضح الطريقة، وتحقق من افتراضاتها وتفسير النتيجة.