আসসালামু আলাইকুম। অনেকদিন পর লিখতে বসলাম আজ। কম্বিনেটরিক্স আমাকে প্রতিনিয়ত অবাক করে এসেছে এর গণনা করার অদ্ভূত ক্ষমতা দিয়ে। তাই আজ ঠিক করেছি কম্বিনেটরিক্সের গুরুত্বপূর্ণ একটা অংশ গ্রিড ট্রাভেলিং ( Grid Travelling ) নিয়ে লিখবো,এর সাথে একেবারেই গৌণভাবে তুলে ধরা হবে ডাইনামিক প্রোগ্রামিং এর কিছু অংশ , প্রবলেম সল্ভিং এবং কাউন্টিং-এ এর ক্ষমতা।

View

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

১) ডানে,বামে,উপরে বা নিচে যেতে পারবে কেবল,এমন।

২) মাঝে হয়তো এমন কিছু পয়েন্ট দেয়া থাকবে,যেসব পথ তোমাকে সবসময় এভয়েড করে চলতে হবে। কারণ সে পথে রয়েছে ডিপজল,আর তুমি অনন্ত জলিল! তবে অনন্ত জলিল হয়ে লাভ নেই,ডিপজলের সাথে তুমি পারবে না!

১ আর ২ নং শর্ত কে আরো সহজ বানিয়ে শুরু করা যাক। ধরে নিই,এখন শর্তগুলো এমনঃ

১) তুমি কেবলমাত্র ডানে এবং উপরের দিকে যেতে পারবে।
২) তোমার এই গ্রিডে কোনো ডিপজল নেই। মানে এমন কোনো পয়েন্ট নেই,যেই পথে তুমি পা দিতে পারবেনা। পুরো গ্রিড জুড়ে অবাধ বিচরণ করতে পারবে।

আমি এই পোস্টে m*n গ্রিড বলতে বোঝাবো x-অক্ষ বরাবর m-সংখ্যক এবং y-অক্ষ বরাবর n-সংখ্যক বর্গাকৃতির বক্স নিয়ে সাজানো গ্রিড।

ওহ আচ্ছা,কোত্থেকে তোমার যাত্রা শুরু হবে তাই তো বলিনি। ধরে নাও তুমি (0,0) পয়েন্টে আছো। তোমাকে 5*5 একটা গ্রিডের (5,5) পয়েন্টে যেতে হবে। ছবিতে যদি দেখাই,তা হবে অনেকটা এমনঃ
2কাজ হচ্ছে A পয়েন্ট থেকে তুমি B পয়েন্টে যাবে। তোমার হাতে অপশন দুইটা। হয় উত্তর দিকে ( উপরে ) যাও,না হয় পূর্ব দিকে ( ডানে ) যাও।   এ ছাড়া অন্য কোনো মুভ দেয়া যাবে না। কতভাবে যেতে পারো সেটাই বের করতে হবে।

এই প্রব্লেমটা আমরা দুইভাবে সল্ভ করার চিন্তাভাবনা করতে পারি। প্রথমে অপেক্ষাকৃত সহজ উপায়টা দেখিঃ

প্রথম পদ্ধতিঃ
একটা জিনিস খেয়াল করে দেখো,তোমাকে A পয়েন্ট থেকে B পয়েন্টে যেতে হলে ৫ বার ডানে এবং ৫ বার উপরে উঠতেই হবে,এর কোনো বিকল্প কি আছে? তুমি জেদ ধরে বললা, ” না ভাইয়া,আমি ৪ বার উপরে উঠবো,আর ৬ বার ডানে যাবো,এভাবেই আমি আমার লক্ষ্যে পৌঁছে যাব” । আসলেই কি এই জেদ তোমাকে B তে নিয়ে যেতে পারবে? পারবে না। কারণ তুমি যদি ৪ বার উপরে উঠো,তাহলে তুমি ৪ নম্বর Horizontal লাইনেই ঘুরাফেরা করতে পারবে ডানে যেতে যেতে,৫ নম্বর লাইনে আর উঠা লাগবেনা। তুমি যদি বলো আবার জেদ করে যে ”ভাইয়া,আমি ৫ বার উপরে উঠবো,আর ৬ বার ডানে যাবো,এভাবেই আমি আমার লক্ষ্যে পৌঁছে যাব” । এই কথা বললে তুমি হয়তো লক্ষ্যে শুধু পৌঁছাবেই না,লক্ষ্য অতিক্রম করে আরো দূরে চলে যাবে। যেটা আমরা চাইনি। তাহলে এখন তুমি তোমার সব জেদ ঝেড়ে ফেলে বললেঃ

” না ভাইয়া,আমি ৫ বার উপরে আর ৫ বার ডানে গিয়েই আমার লক্ষ্যে পৌঁছে যাব 🙁 “

তোমাকে আশীর্বাদ দিতে দিতে আমি মুচকি হাসি হেসে নিলাম। চোখ বেয়ে আনন্দ অশ্রু নেমে আসলো। :’)

আচ্ছা,এবার বলত,মোট কতগুলা স্টেপ লাগবে তোমাকে (৫,৫) পয়েন্টে যেতে? যেভাবেই যাও না কেন,৫+৫ = ১০ টা স্টেপ ছাড়া কিন্তু তুমি কোনোভাবেই B পয়েন্টে যেতে পারবে না। ওই যে,৫ বার উপরে আর ৫ বার ডানে যে তোমাকে যেতেই হবে! কম ও পারবেনা,বেশিও না! প্রতিটা মুভ একটা একটা করে স্টেপ!

উপরে উঠার স্টেপকে আমি ধরলাম U , আর ডানে যাওয়ার স্টেপকে আমি নাম দিলাম R.

তাহলে এবার আমি যদি বলি,৫+৫ = ১০ টা অক্ষর নিয়ে কতগুলি শব্দ বানানো যায়,যেখানে EXACTLY ৫ টা U এবং ৫ টা R থাকবে? খুব সহজ না? পারমুটেশন কম্বিনেশন জানলে এই প্রবলেম তোমাদের কাছে কোনো ব্যাপার!

১০ টা ঘরে ৫টা R বসিয়ে দাও। কয়ভাবে বসাতে পারবে? 10C5 ভাবে,তাইনা? এবার বাকি ৫টা ঘরে ৫টা U বসিয়ে দাও। এটা কয়ভাবে করা যায়? 5C5 = 1 ভাবে। তাহলে মোট ১০ টা অক্ষর নিয়ে কতগুলি শব্দ বানানো যায়,যেখানে EXACTLY ৫ টা U এবং ৫ টা R থাকবে? উত্তরঃ 10C5 * 5C5 = 252

তার মানে,এরকম ২৫২টা শব্দ আছে ,যেখানে Exactly ৫টা R এবং ৫টা U আছে! 😀

তার মানে,A থেকে B তে তুমি এই ২৫২ ভাবেই যেতে পারবে! দারুণ না? 😀

এখন তোমাকে যদি (৫,৫) এর বদলে (n,n) বলা হতো,তখন? উত্তরটা সহজ। তখন 2n সংখ্যক অক্ষর নিয়ে কতগুলো শব্দ বানানো যায়,যেখানে EXACTLY n টা R এবং n টা U থাকবে , সেটা বের করে ফেললেই হয়ে যায়। উত্তর হবে যথারীতিঃ

3

কেননা nCn = 1

তাহলে আমরা একটি বর্গাকৃতির গ্রিডের ক্ষেত্রে উত্তর পেয়ে গেলাম! ঘরটি যদি m * n হতো,তাহলেও কাজ প্রায় একই! আমরা 2n পেয়েছিলাম n+n থেকে,এখানে n+m হবে। তাই m*n একটা গ্রিডের (০,০) থেকে (m,n) পয়েন্টে যেতে চাইলে ( শর্ত হচ্ছে কেবল ডানে-উপরে যেতে পারবে ) তুমি সেটা (m+n)C(m) অথবা (m+n)C(n) উপায়ে করতে পারবে। দু’টোই সমান,যেটা খুশি ব্যবহার করতে পারো।

4

অদ্ভূত না? একটা কঠিন প্রব্লেমকে চিরচেনা ফর্মে কনভার্ট করে কত সহজে সল্ভ করে ফেলা যায়!

দ্বিতীয় পদ্ধতিঃ

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

চিন্তা করো,তুমি একটা পয়েন্টে আছো যেই পয়েন্টের স্থানাংক (a,b) । এই (a,b) পয়েন্টে তুমি কোন কোন জায়গা থেকে আসতে পারবে একটু চিন্তা করে বলতে পারবে?

আমি ছবি এঁকে বলে দিঃ

5

দেখো তো,তুমি যদি জানো যে (a,b-1) পয়েন্টে কত ভাবে আসা যায় এবং (a-1,b) পয়েন্টে কতভাবে আসা যায়,তাহলে কি তুমি বলতে পারবে না (a,b) পয়েন্টে কতভাবে আসা যায়? এটা সহজ,ওই দুইপয়েন্টে যতভাবে আসা যায়,তার যোগফলটাই হবে উত্তর! কারণ তুমি কেবলমাত্র এই দুই পয়েন্ট থেকেই (a,b) পয়েন্টে আসতে পারবে,অন্য কোনো উপায়ে পারবে না।

তাহলে আমরা যদি একটা রিকারসিভ ফাংশন লিখি এইভাবে , তাহলে আমরা যেকোনো পয়েন্ট (a,b) তে কতভাবে আসা যায় সেটি পেয়ে যাবঃ
5

তো প্রতিটা রিকারশনের তো একটা Base Case থাকে তাইনা? আমাদের এই রিকারশনের বেইজ কেস কি হবে বলতে পারো? যখন a অথবা b দুইটোর একটি অন্ততঃপক্ষে শূণ্য হয়ে যাবে,তখন ১ রিটার্ন করে দিতে হবে। কেন না,তুমি গ্রিডের গা ঘেঁষে যেকোনো পয়েন্টে একভাবেই যেতে পারো। সেটা X-Axis এর উপরে হলে ডানে যেতে যেতে পেয়ে যাবে,অথবা Y-Axis এর উপরে হলে উপরে উঠতে উঠতেই পেয়ে যাবে। তাই ঐ পয়েন্টটায় যেতে তোমাকে ১টি পথই অবলম্বন করতে হবে।

মজার ব্যাপার হচ্ছে,আমাদের এই রিকারশনে ওভারল্যাপিং সাবপ্রবলেম আছে। তার মানে একই ফাংশন একই প্যারামিটারে অনেকবার কল চলে আসে। আমরা যদি একটা স্পেসিফিক প্যারামিটারের জন্য ফাংশন কত ভ্যালু রিটার্ন করবে,সেটা আগে থেকে আরেকটা ২-ডি অ্যারেতে সেইভ করে রাখি,তাহলে কি সুবিধা হয়না? বার বার কল আসলে,আমরা সেটা বারবার ক্যালকুলেট না করে আগে থেকে সেইভ করা মানটা ব্যবহার করে দিবো। এইটাই ডাইনামিক প্রোগ্রামিং! তোমরা যারা এটা নিয়ে শুরু থেকে পড়াশোনা করতে চাও,তারা শাফায়েত ভাইয়ের ব্লগ দেখে আসতে পারো। লিংক এখানে

 

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

উত্তরঃ O(2^n)

আমরা যদি f(3,3) কল দিতাম,তাহলে আমাদের রিকারশন ট্রি টা দেখতে কেমন হত? চলো ছবির সাহায্যে দেখে আসি! সেই সাথে ওভারল্যাপিং সাবপ্রবলেমস গুলোও দেখে আসা যাবে!

চিত্রঃ১

এখানে অসংখ্য ওভারল্যাপিং সাবপ্রব্লেমস আছে,যেগুলো আমরা চাইলে প্রথমে ক্যালকুলেট করে রেখে পরবর্তী কলের জন্য ঐ মানটা ব্যবহার করেই ট্রি এর ডেনসিটি কমিয়ে ফেলতে পারতাম! রানটাইম ও কমে যেত অনেক! এটাই মূলত ডাইনামিক প্রোগ্রামিং! 😀

আচ্ছা,যদি ওভারল্যাপিং সাবপ্রবলেম গুলোর মান আমরা আগে থেকে সেইভ করে রাখতাম,তাহলে ট্রি টার চেহারা কেমন হত?

চলো দেখে আসি!

চিত্রঃ২

 

নিজের কাছে দেখলেই কত স্বচ্ছ-সুন্দর পরিপাটি মনে হচ্ছে! একটু খানি মেমরীর ব্যবহার , প্রব্লেম এর সল্যুশনকে কত সুন্দর করে দিতে পারে!

তাহলে ফাংশনটিকে একটি কোডে ইমপ্লিমেন্ট করে দিঃ

#include <stdio.h>
#include <string.h>
long long dp[21][21];
long long solve(long long m,long long n)
{
    if(m==0 || n==0) return 1;
    if(dp[m][n]!=-1) return dp[m][n]; // agei jodi calculate kore thaki,tahole notun kore ar calculate korbona. Return kore dibo.

    else
    {
        dp[m][n] = solve(m-1,n)+ solve(m,n-1);
        return dp[m][n];
    }
}
int main()
{
    memset(dp,-1,sizeof(dp)); // puro dp array ta ke -1 diye initialize kore dilam.
    long long m,n;
    scanf("%lld%lld",&m,&n);
    printf("%lld\n",solve(m,n));

    return 0;
}

এতটুকে বুঝতে কোনো সমস্যা থাকলে আমাকে জানাতে ভুল করো না! কমেন্ট বক্স সবসময় খোলা। এতটুকে যদি বুঝতে কোনো সমস্যা না থাকে,তাহলে ঠিক পরের পর্বেই আলোচনা করবো শর্ত যদি আরেকটু কঠিন হয়,ডিপজল চলে আসে এবং ডানে-উপরের পাশাপাশি কর্ণ বরাবর যদি নড়াচড়া করা যায়,তাহলে ব্যাপারটা কেমন ঘটবে! সাথে থাকবে চমৎকার কিছু প্র্যাকটিস প্রবলেম! আশা করি সাথেই থাকবে!