ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন

১ · সমস্যার সংজ্ঞা

$n$টি ম্যাট্রিক্স $A_1, A_2, \ldots, A_n$-এর একটি চেইন গুণ করতে হবে, যেখানে $A_i$-এর মাত্রা $p_{i-1} \times p_i$ (একটি অ্যারে $p[0 \ldots n]$ দিয়ে বর্ণিত, যেন পাশাপাশি ম্যাট্রিক্সগুলো গুণনযোগ্য হয়)। ম্যাট্রিক্স গুণন সহযোগী (associative) — $(A_1 A_2) A_3 = A_1 (A_2 A_3)$ — তাই চূড়ান্ত ফলাফল একই থাকে যেভাবেই প্যারেন্থেসাইজ করা হোক না কেন। কিন্তু দুটি ম্যাট্রিক্স ($p \times q$ এবং $q \times r$) গুণ করতে ঠিক $p \cdot q \cdot r$টি স্কেলার গুণন লাগে, এবং প্যারেন্থেসাইজেশনের উপর নির্ভর করে মোট স্কেলার গুণনের সংখ্যা অনেক ভিন্ন হতে পারে। লক্ষ্য: সর্বনিম্ন মোট স্কেলার গুণন প্রয়োজন এমন প্যারেন্থেসাইজেশন খুঁজে বের করা (আমাদের এখানে শুধু সেই সর্বনিম্ন সংখ্যাটিই বের করতে হবে, প্রকৃত গুণন নয়)।

২ · ইন্টারভাল DP রিকারেন্স

$dp[i][j]$ সংজ্ঞায়িত করি $A_i, A_{i+1}, \ldots, A_j$ ($i \le j$) গুণ করার সর্বনিম্ন স্কেলার-গুণন খরচ হিসেবে। বেস কেস $dp[i][i] = 0$ (একটি একক ম্যাট্রিক্স গুণ করার কিছু নেই)।

$$ dp[i][j] = \min_{i \le k < j} \Big(\, dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j \,\Big), \qquad i < j $$

এখানে $k$ হলো "স্প্লিট পয়েন্ট" — চেইনটি $(A_i \cdots A_k)$ এবং $(A_{k+1} \cdots A_j)$ এই দুই ভাগে ভাগ করা হয়, প্রতিটি ভাগ আলাদাভাবে (রিকার্সিভভাবে) সবচেয়ে সস্তায় গুণ করা হয়, এবং শেষে এই দুই ভাগের ফলাফল দুটি ম্যাট্রিক্স (মাত্রা $p_{i-1} \times p_k$ এবং $p_k \times p_j$) হিসেবে গুণ করতে $p_{i-1} \cdot p_k \cdot p_j$ অতিরিক্ত স্কেলার-গুণন লাগে। সব সম্ভাব্য $k$ ($i$ থেকে $j-1$ পর্যন্ত) পরীক্ষা করে সবচেয়ে সস্তাটি বেছে নেওয়া হয়।

অপটিমাল সাবস্ট্রাকচার প্রমাণ: ধরা যাক $A_i \cdots A_j$-এর একটি অপটিমাল প্যারেন্থেসাইজেশনের সবচেয়ে বাইরের গুণনটি ঠিক $k^*$ অবস্থানে ভাগ করে (অর্থাৎ $(A_i \cdots A_{k^*})(A_{k^*+1} \cdots A_j)$)। তাহলে $(A_i \cdots A_{k^*})$-এর নিজস্ব প্যারেন্থেসাইজেশনও অবশ্যই $A_i \cdots A_{k^*}$-এর জন্য অপটিমাল হতে হবে — কারণ যদি এর চেয়ে সস্তা কোনো প্যারেন্থেসাইজেশন থাকত, সেটি বসিয়ে দিলে (বাকি সব অপরিবর্তিত রেখে) পুরো চেইনের মোট খরচ আরও কমে যেত, যা মূল সমাধানের অপটিমাল হওয়ার সাথে সাংঘর্ষিক। একই যুক্তি $(A_{k^*+1} \cdots A_j)$-এর জন্যও প্রযোজ্য। তাই অপটিমাল সমাধান তার দুই সাবচেইনের অপটিমাল সমাধান থেকে গঠিত — অপটিমাল সাবস্ট্রাকচার। আর $dp[i][k]$-এর মতো একই সাবচেইন বহু ভিন্ন বাইরের স্প্লিট পয়েন্টের হিসাবে পুনরায় প্রয়োজন হয় — ওভারল্যাপিং সাবপ্রবলেম।

৩ · যাচাই — নেইভ রিকার্সিভ ব্রুট-ফোর্স বনাম DP

ব্রুট-ফোর্স ভার্সনটি ঠিক উপরের রিকারেন্সের মতোই সব সম্ভাব্য স্প্লিট পয়েন্ট $k$ চেষ্টা করে, কিন্তু কোনো cache ছাড়া — অর্থাৎ এটি প্রকৃতপক্ষে সব সম্ভাব্য প্যারেন্থেসাইজেশন রিকার্সিভভাবে পরীক্ষা করে (মোট সংখ্যা ক্যাটালান সংখ্যা অনুসারে বাড়ে, যা এক্সপোনেনশিয়াল)। ছোট চেইনে ($n \le 6$) এটি এখনও দ্রুত চলে।

import random

def mcm_brute(p, i, j):
    # নেইভ রিকার্সন -- সব সম্ভাব্য স্প্লিট পয়েন্ট, কোনো cache নেই
    if i == j:
        return 0
    best = None
    for k in range(i, j):
        cost = mcm_brute(p, i, k) + mcm_brute(p, k + 1, j) + p[i - 1] * p[k] * p[j]
        if best is None or cost < best:
            best = cost
    return best

def mcm_dp(p):
    # ইন্টারভাল DP -- দৈর্ঘ্য অনুযায়ী ছোট থেকে বড় রেঞ্জ পূরণ
    n = len(p) - 1  # ম্যাট্রিক্স সংখ্যা
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):          # সাবচেইনের দৈর্ঘ্য (কতগুলো ম্যাট্রিক্স)
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                for k in range(i, j)
            )
    return dp[1][n]

rng = random.Random(3)
print(f"{'dims p':>25} | {'brute':>6} | {'dp':>6}")
for trial in range(8):
    n = rng.randint(2, 6)
    p = [rng.randint(2, 20) for _ in range(n + 1)]
    b = mcm_brute(p, 1, n)
    d = mcm_dp(p)
    assert b == d, "মিসম্যাচ!"
    print(f"{str(p):>25} | {b:>6} | {d:>6}")

print("\nক্লাসিক CLRS উদাহরণ (৬টি ম্যাট্রিক্স):")
p = [30, 35, 15, 5, 10, 20, 25]
print("p =", p, "-> সর্বনিম্ন স্কেলার-গুণন:", mcm_dp(p), "(brute:", mcm_brute(p, 1, len(p) - 1), ")")