نختار أقواس ضرب السلسلة لتقليل العمليات مع ثبات ترتيب المصفوفات. [1]
سنستعمل أربع مصفوفات بأبعاد صغيرة، ونحسب البدائل الخمسة كاملة. ثم نبني جدولًا يصل إلى أفضلها من مسائل أقصر. بهذه الطريقة تستطيع مراجعة الخطة قبل تنفيذ أي ضرب لعناصر المصفوفات، وفهم سبب القرار بدل الاكتفاء باسم دالة تختاره لك.
الخلاصة السريعة
- أبعاد مثالنا هي A:6×2، B:2×7، C:7×3، D:3×5، وترتيبها ثابت.
- الخطة A((BC)D) تحتاج 132 ضربة عددية في الحساب المدرسي؛ التجميع اليساري يحتاج 300.
- أرخص خطوة أولى في المثال هي ضرب BC، لكن اختيار هذه الخطوة وحده لا يحدد بقية الخطة.
- حصر البرنامج البدائل الخمسة، وفحص الجدول على 124 سلسلة أبعاد أخرى.
- نفذنا الضرب الفعلي بأعداد صحيحة وفق البدائل الخمسة؛ اتفقت المصفوفات الناتجة، واختلف عد العمليات.
حدد ما الذي تعدّه قبل المقارنة
ضرب مصفوفة r×k في k×c يكلف rkc ضربات عددية في نموذج الحساب المباشر. تعرض وثائق NumPy هذا العد لمقارنة الأقواس. [2]
لذلك كلفة AB عندنا 6×2×7=84، ويكون الناتج 6×7. أما BC فكلفته 2×7×3=42 وناتجه 2×3. وتكلف CD مقدار 7×3×5=105 وتعطي 7×5.
كل مقارنة في المقال تعد الضرب فقط: لا نضيف الجمع أو النسخ أو تخصيص الذاكرة. لم نقس زمن مكتبة على معالج معين. والأبعاد ليست أسماء قابلة للتبديل: نقل D إلى البداية يغير التعبير، وربما يجعل ضربًا لاحقًا غير صالح أصلًا. الذي نغيره هنا هو موضع الأقواس داخل السلسلة نفسها.
افتح البدائل الخمسة قبل اختصار البحث
ابدأ بالتجميع اليساري ((AB)C)D. تدفع 84 لضرب الزوج الأول. الناتج 6×7 يضرب في 7×3 بكلفة 126، ثم يضرب 6×3 في 3×5 بكلفة 90. المجموع 300.
في الخطة الأفضل نبدأ بـBC فننتج 2×3 بكلفة 42. نضرب الناتج في D بكلفة 2×3×5=30، فيصبح 2×5. أخيرًا نضربه من اليسار في A بكلفة 6×2×5=60. إذن 42+30+60=132.
| الأقواس | الكلفة |
|---|---|
| (A(B(CD))) | 235 |
| (A((BC)D)) | 132 |
| ((AB)(CD)) | 399 |
| ((A(BC))D) | 168 |
| (((AB)C)D) | 300 |
لاحظ أن (A(BC))D يبدأ أيضًا بالزوج الأرخص BC، لكنه ينتهي إلى 168 بدل 132. الفرق في القرار التالي: هل نضرب الناتج في D أم نضربه أولًا في A؟ هذا يكفي ليبين أن عبارة «ابدأ بالزوج الأرخص» لا تصف خطة كاملة للمثال.
ابنِ الجدول من السلاسل القصيرة
تمثل m(i,j) أقل كلفة للجزء i..j. جرّب كل فاصل واجمع كلفتي الجزأين وضربهما؛ كلفة المصفوفة المفردة صفر. [1]
نرقم الأبعاد d=[6,2,7,3,5] من الصفر، والمصفوفات من الواحد. الصيغة التي نملأ بها الجدول هي:
m(i,j) = min over i ≤ k < j:
m(i,k) + m(k+1,j) + d[i-1]*d[k]*d[j]
ضع صفرًا على القطر لأن خلية مثل m(2,2) تمثل B كما هي. ثم املأ طول اثنين بالقيم 84،42،105. عند طول ثلاثة، لسلسلة ABC خياران: A(BC) يكلف 42+36=78، و(AB)C يكلف 84+126=210. نخزن 78.
وللسلسلة BCD نحصل على B(CD):105+70=175، مقابل (BC)D:42+30=72. نخزن 72. الخانات الأقصر المطلوبة أصبحت جاهزة قبل الانتقال إلى السلسلة كاملة.
| البداية / النهاية | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 84 | 78 | 132 |
| B | — | 0 | 42 | 72 |
| C | — | — | 0 | 105 |
| D | — | — | — | 0 |
ثلاث مقارنات تحسم الضربة الأخيرة
الفاصل بعد A يقارن A مع أفضل خطة للجزء BCD. الفاصل بعد B يقارن AB مع CD. والفاصل بعد C يقارن أفضل ABC مع D. هذا فاصل الضربة الأخيرة، وليس بالضرورة أول خطوة تنفيذ.
| الفاصل بعد | الجزء الأول | الجزء الثاني | دمج الناتجين | المجموع |
|---|---|---|---|---|
| A | 0 | 72 | 60 | 132 |
| B | 84 | 105 | 210 | 399 |
| C | 78 | 0 | 90 | 168 |
استبدال خطة جزء بخطة أرخص يحفظ أبعاد ناتجه؛ لذلك نخزن أقل كلفة لكل جزء. [1]
لا تحتفظ بالعدد 132 وحده إن كنت تريد التنفيذ. احفظ معه الفاصل الأول: بعد A. وفي الجزء BCD احفظ الفاصل بعد C، وفي BC الفاصل بعد B. استعادة هذه القرارات تعطينا A((BC)D)، ثم ننفذ من الأقواس الداخلية إلى الخارجية.
افحص الخطة بطريقتين مستقلتين
ولد البرنامج كل شجرة أقواس لأربعة عوامل دون استعمال جدول التخطيط، ثم حسب كلفتها من أبعاد ناتجي كل عقدة. نتجت الخيارات الخمسة في الجدول. وفي فحص أوسع، جرب جميع متجهات الأبعاد المؤلفة من اثنين وثلاثة، لسلاسل من عامل واحد إلى خمسة: 4+8+16+32+64=124 حالة. وافق الحد الأدنى المحصور كلفة الجدول في كل حالة، وأعادت خطة الفواصل المحفوظة تلك الكلفة نفسها.
للتأكد من أن الأقواس تستعمل عواملنا نفسها، أنشأنا عناصر صحيحة بالقاعدة M_i[r,c]=((i+2)*(r+1)+3*c)%7-2، مع بدء فهارس العامل والصف والعمود من صفر. نفذنا الخيارات الخمسة بحلقات ضرب وجمع فعلية. اتفقت النتائج خانة بخانة، بالشكل 6×5؛ أول خانة 63 وآخرها −441، ومجموع الخانات 567. وافق عداد الضرب الفعلي الكلف الخمس المحسوبة.
رفضنا أيضًا خمسة مدخلات غير صالحة، منها الأبعاد الصفرية والسالبة وغير الصحيحة وغياب مصفوفة. لا يثبت الاختبار المنتهي كل سلسلة ممكنة، لكنه يفصل خطأ الفهرسة في تنفيذنا عن حجة بناء الجدول. ولا يضمن اتفاق الحساب الصحيح تطابق مسارات الحساب العائم؛ يشرح مثال multi_dot وتغير الأقواس هذه المسألة العددية المنفصلة.
المصادر
الأمثلة العددية والرسوم والاختبارات أصلية لهذا المقال ومنفذة برمجيًا. أُعدت الصياغة والمراجعة الأولية بمساعدة الذكاء الاصطناعي، دون ادعاء مراجعة بشرية مستقلة.