Matrix Chain Multiplication

Q: ما التعقيد الزمني لضرب سلسلة المصفوفات؟

يحتوي الجدول على نحو n²/2 مقطعًا، ويحاول كلٌّ منها ما يصل إلى n تقسيمات، لذا يستغرق البرمجة الديناميكية زمنًا قدره O(n³) وتستهلك ذاكرة قدرها O(n²) . أما الاستدعاء الذاتي البسيط من دون تخزين مؤقت، فيُجري 3^(n-1) استدعاءً لـ n مصفوفات.

Q: لماذا يهم ترتيب ضرب المصفوفات؟

ضرب المصفوفات تجميعي، لذا يعطي كلٌّ من (AB)C و A(BC) المصفوفة نفسها، لكن المصفوفات الوسيطة تختلف في الحجم. في المثال الأول، ينتج (AB)C مصفوفة بحجم 4 × 3 وتبلغ كلفته 264، بينما ينتج A(BC) مصفوفة بحجم 10 × 12 وتبلغ كلفته 840.

Q: كيف تجد ترتيب الأقواس الأمثل نفسه؟

خزّن نقطة التقسيم الفائزة في choice[left][right] بجوار best[left][right] . للطباعة، تُطبع المصفوفة المفردة باسمها؛ أما المقطع الأطول فيُطبع بقوس فتح، ثم الجزء حتى choice[left][right] ، ثم الجزء الذي يليه، ثم قوس إغلاق. يضيف هذا O(n²) من الذاكرة.

صعبالبرمجة الديناميكية

+10

تُوصَف سلسلة من المصفوفات بواسطة dims: للمصفوفة i عدد صفوف يساوي dims[i] وعدد أعمدة يساوي dims[i+1]، لذا تلائم كل مصفوفة المصفوفة التالية. يتطلب ضرب مصفوفة أبعادها p × q في مصفوفة أبعادها q × r إجراء p × q × r عملية ضرب قياسية، وينتج مصفوفة أبعادها p × r. تؤدي كل طريقة لوضع الأقواس إلى الناتج النهائي نفسه، ولكن ليس بالتكلفة نفسها. أعدّ أقل عدد من عمليات الضرب القياسية اللازمة لضرب السلسلة بأكملها.

الدالة

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: الأحجام على طول السلسلة: المصفوفة i أبعادها dims[i] × dims[i+1]
تُرجعinteger: أقل عدد من عمليات الضرب القياسي اللازمة لضرب السلسلة بأكملها

القيود

2 ≤ dims.length ≤ 100، لذا تتكوّن السلسلة من 1 إلى 99 مصفوفة.
1 ≤ dims[i] ≤ 100
الإجابة لا تتجاوز 98 × 10⁶، وهي ضمن نطاق الأعداد الصحيحة الموقّعة ذات 32 بت.

أمثلة

المدخلات: dims = [4, 10, 3, 12]
المخرجات: 264
الشرح: يتطلب ضرب المصفوفتين الأوليين 4 × 10 × 3 = 120، وينتج عنه مصفوفة 4 × 3، وضربها في المصفوفة 3 × 12 يضيف 144: فيكون المجموع 264. أما الترتيب الآخر، فيتطلب 360 + 480 = 840.

سؤال إضافي

هل يمكنك أيضًا حساب عدد طرق وضع الأقواس المختلفة التي تحقق أقل تكلفة؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يغيّر الترتيب التكلفة: 264 مقابل 840 في المثال الأول. انظر إلى عملية الضرب الأخيرة. فهي تجمع حاصلَي ضرب جزء أيسر وجزء أيمن من السلسلة، وكل جزء هو المشكلة نفسها على سلسلة أقصر. يحل جدولٌ يغطي مقاطع السلسلة كل مشكلة مرة واحدة، في زمن O(n³).

جرّب كل تقسيم باستخدام الاستدعاء الذاتي البسيط

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

رقّم حدود السلسلة من 0 إلى m-1، حيث m = dims.length: حجم الحد k هو dims[k]. حاصل ضرب المصفوفات بين الحدين left وright هو مصفوفة أبعادها dims[left] × dims[right] بأي ترتيب كان. لذا، إذا قسّمت الخطوة الأخيرة ذلك الجزء عند split، فتكلفتها dims[left] × dims[split] × dims[right]، مهما كان ما حدث داخل الكتلتين. ينبغي بناء كل كتلة بأقل تكلفة ممكنة، لذا فإن cheapest(left, right) هي أصغر مجموع لتكلفتي الكتلتين مضافًا إليه تكلفة تلك الخطوة الأخيرة، عبر كل قيم split. تجربة كل خطوة أخيرة تضمن صحة الحل.

يحلّ الأجزاء نفسها مرارًا وتكرارًا: تتطلب n مصفوفات 3^(n-1) استدعاءً، أي نحو 1.2 × 10^9 استدعاء لـ 20 مصفوفة، بينما لا يوجد سوى نحو m²/2 جزءًا مختلفًا.

الخوارزمية

اكتب cheapest(left, right) للمصفوفات الواقعة بين الحدّين left وright.
إذا كان right - left < 2، فهناك مصفوفة واحدة: أعد 0.
لكل split يقع بينهما تمامًا، أضف cheapest(left, split) وcheapest(split, right) وdims[left] × dims[split] × dims[right].
أعد أصغر مجموع.
الإجابة هي cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

الاستدعاء الذاتي مع التخزين المؤقت

الفكرة

يعتمد الاستدعاء فقط على left وright. احفظ نتيجته في memo[left][right]، مع بدء كل خلية بالقيمة -1، وهي قيمة لا يمكن أن تمثل أي تكلفة فعلية، ثم تقرأ الاستدعاءات اللاحقة الخلية بدلًا من تنفيذ الاستدعاء递归يًا. يُحل كل زوج من الأزواج البالغ عددها نحو m²/2 مرة واحدة، مع أقل من m انقسامات: O(n³)، أو 161,700 عملية تحقق من الانقسام لـ 99 مصفوفة. لا يتجاوز عمق الاستدعاء عمق السلسلة، لذا تتسع مكدسة الاستدعاءات في أي نظام لتخزين 100 حد.

الخوارزمية

أنشئ memo بـ m صفوف وm أعمدة، واجعل قيمة كل خلية -1.
في cheapest(left, right)، تُعيد سلسلة من مصفوفة واحدة القيمة 0، وتُعيد الخلية التي لا تساوي -1 تكلفتها المحفوظة.
وإلا، احسب تكلفة كل split تمامًا كما يفعل الاستدعاء الذاتي البسيط، وخذ القيمة الصغرى.
اكتب هذه القيمة الصغرى في memo[left][right] قبل إعادتها.
الإجابة هي cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

املأ الجدول بتمديد العرض

الفكرة

تعتمد كل خلية فقط على مقاطع أضيق، لذا يمكن للحلقات ملء best[left][right] من الأضيق إلى الأوسع. العرض 1 يعني مصفوفة واحدة وتبقى القيمة 0؛ وعندما تصل إلى مقطع أوسع، يكون الجزآن لكل تقسيم قد حُسبا بالفعل. مع dims = [6, 2, 7, 3, 5]:

العرض 2: best[0][2] = 84، وbest[1][3] = 42، وbest[2][4] = 105.
العرض 3: قيمة best[0][3] هي 78 (التقسيم 1: 0 + 42 + 36)، وقيمة best[1][4] هي 72 (التقسيم 3: 42 + 0 + 30).
العرض 4: تعطي التقسيمات 1 و2 و3 القيم 0 + 72 + 60 = 132، و84 + 105 + 210 = 399، و78 + 0 + 90 = 168، لذا best[0][4] = 132.

يعني التقسيم العلوي عند الحد 1 أن المصفوفة 6 × 2 تُضم أخيرًا، كما في المثال الثاني. يتطابق الزمن واستهلاك الذاكرة مع نسخة التخزين المؤقت، من دون استدعاء递ي.

الخوارزمية

لتكن m = dims.length، وخصّص جدولًا m × m باسم best مملوءًا بالأصفار.
كرّر width من 2 إلى m-1. وداخل ذلك، كرّر left تصاعديًا بدءًا من 0 ما دام right = left + width لا يزال ضمن الحدود.
لهذا المدى، احسب best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] لكل split من left+1 إلى right-1، وخزّن القيمة الصغرى في best[left][right].
الإجابة في best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

أخطاء شائعة وحالات حدّية

ضرب الزوج الأرخص أولًا. في [10, 10, 1, 9] يكون الزوج الأخير هو الأرخص (90)، لكن الخطوة التي تليه تكلف 900، ليصبح المجموع 990. أما ضرب الزوج الأول أولًا فيكلف 190.
قراءة الإجابة من الخانة الخاطئة. يحتوي dims على عنصر واحد أكثر من عدد المصفوفات، لذا تكون الإجابة best[0][m-1]، وليس best[0][m].
زيادة left في الحلقة الخارجية. عندها يقرأ الصف left القيمة best[split][right] من صف لاحق لا تزال قيمته 0. اجعل العرض في الحلقة الخارجية، أو أنقص left.
إغفال حالة المصفوفة الواحدة. يجب أن تُرجع [3, 7] القيمة 0، وفي R تصبح الحلقة 2:(m-1) هي 2:1 وتعمل بالعكس، لذا أضف شرطًا يحميها.

أسئلة شائعة3

ما التعقيد الزمني لضرب سلسلة المصفوفات؟

يحتوي الجدول على نحو n²/2 مقطعًا، ويحاول كلٌّ منها ما يصل إلى n تقسيمات، لذا يستغرق البرمجة الديناميكية زمنًا قدره O(n³) وتستهلك ذاكرة قدرها O(n²). أما الاستدعاء الذاتي البسيط من دون تخزين مؤقت، فيُجري 3^(n-1) استدعاءً لـ n مصفوفات.

لماذا يهم ترتيب ضرب المصفوفات؟

ضرب المصفوفات تجميعي، لذا يعطي كلٌّ من (AB)C وA(BC) المصفوفة نفسها، لكن المصفوفات الوسيطة تختلف في الحجم. في المثال الأول، ينتج (AB)C مصفوفة بحجم 4 × 3 وتبلغ كلفته 264، بينما ينتج A(BC) مصفوفة بحجم 10 × 12 وتبلغ كلفته 840.

كيف تجد ترتيب الأقواس الأمثل نفسه؟

خزّن نقطة التقسيم الفائزة في choice[left][right] بجوار best[left][right]. للطباعة، تُطبع المصفوفة المفردة باسمها؛ أما المقطع الأطول فيُطبع بقوس فتح، ثم الجزء حتى choice[left][right]، ثم الجزء الذي يليه، ثم قوس إغلاق. يضيف هذا O(n²) من الذاكرة.

def matrixChainOrder(dims):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

dims = [4, 10, 3, 12]

الإخراج المتوقع

Matrix Chain Multiplication

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كل تقسيم باستخدام الاستدعاء الذاتي البسيط

الاستدعاء الذاتي مع التخزين المؤقت

املأ الجدول بتمديد العرض

أخطاء شائعة وحالات حدّية

أسئلة شائعة3

مسائل مشابهة