ডায়নামিক প্রোগ্রামিং৮ মিনিট পড়া

ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix Chain Multiplication)

যে ক্রমে আপনি ম্যাট্রিক্স গুণ করেন তা অত্যন্ত গুরুত্বপূর্ণ — সবচেয়ে কম খরচের বা চিপেস্ট (cheapest) ক্রমটি খুঁজে বের করুন
time:\(O(n^3)\)space:\(O(n^2)\)

ধরুন আপনি অনেকগুলো ধাপে একটি লম্বা দূরপাল্লার ভ্রমণের (long journey) আয়োজন করছেন। আপনি ধাপগুলোকে যেভাবেই সাজান না কেন, আপনার চূড়ান্ত গন্তব্য পরিবর্তন হবে পণ্ডিত — কিন্তু এর রুট বা পথের ক্রমের ওপর নির্ভর করে আপনার জ্বালানি বা বাস ভাড়ার খরচে বিশাল পার্থক্য হতে পারে। ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix chain multiplication) ঠিক এভাবেই কাজ করে: আপনি A × B × C × D কে যেভাবেই বন্ধনী বা প্যারেনথেসিস (parentheses) দিয়ে আবদ্ধ করুন না কেন, চূড়ান্ত গুণফল ম্যাট্রিক্সটি একই থাকবে। কিন্তু এর খরচ বা কস্ট (cost) — অর্থাৎ অ্যারিথমেটিক অপারেশনের সংখ্যা — অনেক গুণ বেড়ে বা কমে যেতে পারে।

একটি (a×b) ম্যাট্রিক্সকে একটি (b×c) ম্যাট্রিক্স দিয়ে গুণ করতে a × b × c সংখ্যক স্কেলার গুণের (scalar multiplications) প্রয়োজন হয় এবং এটি একটি (a×c) ম্যাট্রিক্স তৈরি করে।

একটি বাস্তব উদাহরণ

তিনটি ম্যাট্রিক্স: A(১০×৩০), B(৩০×৫), C(৫×৬০)।

(A×B)×C: A×B এর খরচ ১০×৩০×৫ = ১,৫০০ → (১০×৫); এরপর ×C এর খরচ ১০×৫×৬০ = ৩,০০০। মোট: ৪,৫০০।

A×(B×C): B×C এর খরচ ৩০×৫×৬০ = ৯,০০০ → (৩০×৬০); এরপর A× এর খরচ ১০×৩০×৬০ = ১৮,০০০। মোট: ২৭,০০০।

প্রথম ক্ষেত্রের খরচ ৬ গুণ কম! চেইন যত বড়ো হবে, এই পার্থক্য তত বেশি হবে।

ডাইনামিক প্রোগ্রামিং বা ডিপি (DP) স্টেট

ধরি dp[i][j] = i থেকে j পর্যন্ত ম্যাট্রিক্সগুলোর গুণফল বের করার জন্য প্রয়োজনীয় সর্বনিম্ন স্কেলার মাল্টিপ্লিকেশনের সংখ্যা। ডাইমেনশনগুলোকে একটি dim[] অ্যারে হিসেবে দেওয়া থাকে যেখানে i-তম ম্যাট্রিক্সের আকার হলো dim[i-1] × dim[i]। আমাদের dp[1][n] বের করতে হবে।

রিকারেন্স বা পুনরাবৃত্তি (The Recurrence)

যেকোনো স্প্লিট পয়েন্ট বা বিভাজন বিন্দু k (i ≤ k < j) এর জন্য, আমরা প্রথমে i..k পর্যন্ত ম্যাট্রিক্সগুলো গুণ করি, তারপর k+1..j পর্যন্ত গুণ করি, এবং এরপর এই দুটি গুণফলকে আবার গুণ করি:

যেখানে k এর উপর ভিত্তি করে dp[i][j] = সর্বনিম্ন: dp[i][k] + dp[k+1][j] + dim[i-1] × dim[k] × dim[j]

বেস কেস (Base case): dp[i][i] = 0 (কারণ একটিমাত্র ম্যাট্রিক্স গুণ করার জন্য কোনো অপারেশনের প্রয়োজন হয় না)।

ফিলিং অর্ডার (Fill Order): ছোট চেইন আগে পূরণ করা

dp[i][j] বের করার জন্য dp[i][k] এবং dp[k+1][j] প্রয়োজন — যেগুলো আসলে তুলনামূলক ছোট চেইন। তাই এগুলোকে চেইন ল্যান্থ বা চেইনের দৈর্ঘ্য ক্রমানুসারে বাড়িয়ে পূরণ করুন: প্রথমে l = 1 (বেস কেস), তারপর l = 2 (জোড়া), এভাবে l = n পর্যন্ত। প্রতিটি ল্যান্থ বা দৈর্ঘ্যের জন্য, সকল বৈধ শুরুর অবস্থান i (যেখানে j = i + l - 1) এর ওপর ইটারেট (iterate) করুন।

অপ্টিমাল প্যারেনথেসাইজেশন (Optimal Parenthesization) পুনরুদ্ধার করা

dp[i][j] এর সাথে সেরা বা অপ্টিমাল স্প্লিট পয়েন্ট s[i][j] সংরক্ষণ করুন। তারপর রিকার্সিভলি (recursively) বন্ধনীর অবস্থানগুলো পড়ুন: s[1][n] একেবারে উপরের লেভেলের স্প্লিটটি দেয়; এরপর [1, s[1][n]] এবং [s[1][n]+1, n] এর মধ্যে রিকার্সন প্রয়োগ করুন।

দ্রষ্টব্য: n সংখ্যক ম্যাট্রিক্সকে বন্ধনী বা প্যারেনথেসিস (parenthesize) দিয়ে আবদ্ধ করার উপায় সংখ্যা হলো (n-1)-তম ক্যাটালান নম্বর (Catalan number) — যা এক্সপোনেনশিয়ালি (exponentially) বৃদ্ধি পায়। n=10 টি ম্যাট্রিক্সের জন্য, ৪,৮৬২ টি উপায়ে বন্ধনী সাজানো সম্ভব। ডাইনামিক প্রোগ্রামিং (DP) সবগুলোকে একে একে চেষ্টা করার পরিবর্তে \(O(n^3)\) সময়েই সবথেকে সেরা উপায়টি বের করে দেয়।

ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন — ন্যূনতম খরচ (minimum cost)

def matrix_chain(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0]*n for _ in range(n)]
    # fill by increasing chain length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]


# dims[i-1] x dims[i] is matrix i's shape
print(matrix_chain([10, 30, 5, 60]))   # 4500
print(matrix_chain([40, 20, 30, 10, 30]))  # 26000
Output
4500
26000

Complexity

⏱️ সময় বা টাইম (Time)
\(O(n^2)\) সংখ্যক ইন্টারভ্যাল × প্রতিটি ইন্টারভ্যালে \(O(n)\) সংখ্যক স্প্লিট পয়েন্ট
কিউবিক বা ত্রিঘাত (Cubic) \(O(n^3)\)
📊 মেমরি বা স্পেস (DP + স্প্লিট টেবিল)
উভয় ক্ষেত্রেই — খরচের জন্য dp[n][n] এবং সেরা স্প্লিট পয়েন্টের জন্য s[n][n]
কোয়াড্রেটিক বা দ্বিঘাত (Quadratic) \(O(n^2)\)
🐌 ব্রুট ফোর্স (Brute force)
প্যারেনথেসাইজেশনের সংখ্যা ক্যাটালান নম্বর হিসেবে বৃদ্ধি পায় — যা n এর সাপেক্ষে এক্সপোনেনশিয়াল (exponential)
ক্যাটালান সংখ্যা গণনা (Catalan number count) \(O(4^n / n^{1.5})\)
🔍 রিকনস্ট্রাকশন (Reconstruction)
স্প্লিট-পয়েন্ট টেবিল অনুসরণ করে রিকার্সিভলি (recursively) চলুন — সর্বোচ্চ n-1 সংখ্যক স্প্লিট বা বিভাজন হবে
লিনিয়ার (Linear) \(O(n)\)

ছোট কুইজ

ম্যাট্রিক্স A(২×৩), B(৩×৪), C(৪×২)। কোন প্যারেনথেসাইজেশনটির খরচ সবচেয়ে কম?

পড়া চালিয়ে যান