ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশনের অ্যালগোরিদম একটু বড়। তবে বুঝে গেলে, অনেক সহজ। তাই একে দুটি পর্বে ভাগ করেছি। আশা করি আপনাদের ভাল লাগবে। এটিও ডাইনামিক প্রোগ্রামিং এর অন্তর্ভুক্ত।

কম্পিউটার গ্রাফিক্স এবং আরটিফিশিয়াল ইন্টিলিজেন্স-এ ম্যাট্রিক্স নিয়ে অনেক কাজ করতে হয়। যখন ম্যাট্রিক্স নিয়ে অনেক বড় বড় কাজ করতে হবে, তখন যদি আমরা ম্যাট্রিক্স এর অপারেশনগুলোকে অপটিমাইজ করতে না পারি, তাহলে তো বিপদ হয়ে যাবে।

দুটি ম্যাট্রিক্স কে গুণ করার শর্ত হচ্ছে, প্রথম ম্যাট্রিক্সের কলাম সংখ্যা আর দ্বিতীয় ম্যাট্রিক্সের রো সংখ্যা সমান হতে হবে।

ধরি,  A(10 X 50), B(50 X 30) এবং C(30 X 20)  এই ৩ টি ম্যাট্রিক্স দেয়া আছে।

A ও B কি গুণ করা যাবে? হ্যা যাবে। কারণ A এর কলাম সংখ্যা(50) ও B এর রো সংখ্যা(50) সমান। এখন, আমরা যদি এই ম্যাট্রিক্স তিনটিকে গুণ দিতে চাই, তাহলে অনেকভাবেই গুণ দিতে পারি।

১. (A X B) X C :

এখানে, A X B তে 10 X 50 X 30 = 15000  টি  অপারেশন/গুণ সম্পন্ন হবে।  আবার, (A X B) এর ডিমেনশন হবে 10 X 30। অর্থাৎ;  (A X B) X C তে অপারেশন সম্পন্ন হবে, 15000+10 X 30 X 20 = 21000 টি।

অপর দিকে,

২. A X (B X C) :

B X C তে 50 X 30 X 20 = 30000 টি অপারেশন সম্পন্ন হবে, যার ডিমেনশন হবে 50 X 20। অর্থাৎ;  A X (B X C) তে অপারেশন সম্পন্ন হবে মোট, 30000 + 10 X 50 X 20 = 40000 টি।

১ ও ২ নং এর উত্তর কিন্তু একই আসবে। কিন্তু অপারেশন সংখ্যার পার্থক্য তো অনেক দেখা যাচ্ছে। সুতরাং, প্যারেনথেসাইজেশন, অনেক গুরুত্বপূর্ণ। এখন যদি এমন ১০০ টি ম্যাট্রিক্স কে গুণ করতে বলে? তাহলে ১ম উপায়ে না করে যদি দ্বিতীয় উপায়ে করতাম, অনেক বেশি সময় লাগত। এখন ১০০ টি ম্যাট্রিক্সের ক্ষেত্রে; সবচেয়ে কম সংখ্যক অপারেশনে কিভাবে গুণ করা যায়, তা বের করতে হবে। মোট কথা, গুণ করার অপটিমাল উপায় বের করতে হবে।

এখন, আমরা যদি ব্র্যাকট্যাকিং করি, অর্থাৎ সকল উপায় চেক করে দেখি, এটি অনেক সময় সাপেক্ষ ব্যাপার হবে।  এটিই হল ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন প্রবলেম।

এখন, এই সমস্যা সমাধান করার জন্য আমাদের কাজ গুলোকে কয়েকটি ধাপে ভাগ করে নিতে হবে। নিচে ধাপগুলোর বর্ণনা দেয়া হলঃ

১ম ধাপঃ  অপটিমাল সাবস্ট্রাকচার

প্রথমে আমাদের অপটিমাল সাবস্ট্রাকচার বের করতে হবে। এর জন্য অপটিমাল সাবস্ট্রাকচার হচ্ছে প্যারেনথেসাইযেশন। আমাদের মূল সমস্যা ছিল, A_1.n  পর্যন্ত মাল্টিপ্লিকেশন এর সিকুয়েন্স বের করা। কিন্তু সাবপ্রবলেম হবে, A_i.j  এর জন্য এমন সিকুয়েন্স বের করা, যেন স্কেলার মাল্টিপ্লিকেশন(অপারেশন) সংখ্যা মিনিমাইজড থাকে।

A_i.j পর্যন্ত ম্যাট্রিক্স গুলো যখন আমরা গুণ করব, তখন এর সর্বশেষ ধাপে দুইটি মাত্র ম্যাট্রিক্স অবশিষ্ট থাকবে।

A_i.j = (A_i ……A_k) (A_k+1 . A_j) = A_i.k A_k+1.j

উদাহরণঃ

A_3.6  = (A₃(A₄ A₅)) (A₆) = A_3.5 ……. A_6…6

যেখানে, k=5

এখন, আমাদেরকে জানতে হবে, চেইন টিকে স্প্লিট কিভাবে করব। এটি নির্ভর করবে k এর মান এর উপর। আর সবপ্রবলেগুলো(A_i…k  এবং A_k+1…j) এমনভাবে থাকবে, যেন এরা অপটিমাল হয়।

২য় ধাপঃ অপটিমাল সলিউশনের মান, রিকার্সিভলি বের করা

min[i, j]=0 if i=j

min[i, j] = min_i<=k<j  (m[i, k]+m[k+1, j]+p_i-1 p_k p_j)

এখানে p হচ্ছে ম্যাট্রিক্সের ডাইমেনশন। এখানে আমরা প্রত্যেকটি গুণ এর অপটিমাল সলিউশন নিয়ে এর মিনিমাম টি নিব।  আবার, m[i, k] হচ্ছে এখানে, i থেকে  k পর্যন্ত ম্যাট্রিক্স গুলো গুণ করতে যে পরিমাণ অপারেশন সম্পন্ন হয়েছে, অর্থাৎ যতগুলো গুণ করতে হয়েছে। m[i, j] এর ডাইমেনশন হবে p_i-1 থেকে p­_k পর্যন্ত, আর  m[k+1, j] এর ডাইমেনশন হবে p_k  থেকে  p_j  পর্যন্ত।

এখন যেহেতু, i<=k<j, তাই, k এর সম্ভাব্য মান হবে j-i সংখ্যক। যেমন, i=5 এবং  j=10 হলে, k এর সম্ভাব্য মান হবে ৫টি (5, 6, 7, 8, 9)। এই সম্ভাব্য মানগুলো নিয়ে আমরা সবচেইয়ে ছোট মান টি নিব।

৩য় ধাপঃ বটম-আপ অ্যাপ্রোচ এ অপটিমাল সলিউশন টি বের করতে হবে

যেহেতু ডিপি এর ব্যাপার এসে গেছে, তার মানে এখানে টেবিল তৈরীর ব্যাপার ও এসে গেছে। তাই, যেহেতু প্রোগ্রামিং এ টেবিল তৈরী করা যায় না, আমরা একটি 2-Dimensional অ্যারে (A[i.n, j…n])  ডিফাইন করব। যেখানে অবশ্যই  i<=j হতে হবে।

বাকি অংশ  দ্বিতীয় অর্থাৎ শেষ পর্বে আসছে। শেষ পর্বে এর কোড সম্পর্কেও বিষদ আলোচনা করা হবে।  আজ এ পর্যন্তই থাক। ওহ! আর শেষ পর্ব কিন্তু ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশনের। ডাইনামিক প্রোগ্রামিং এর নয়। সেটা বহু গল্পেও শেষ হবে না। তাই ওটা নিয়ে সামনে লিখা হবে। এখন তো মাত্র শুরু হল।