[ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। এই লেখাটার নতুন ভার্সন পাওয়া যাবে এখানে]
আশা করি তুমি এখন lis,knapsack,coin-change প্রবলেম সলভ করতে পারো খুব সহজেই, ডিপির সলিউশন প্রিন্ট করতেও তোমার সমস্যা হয়না। এখন আমরা একটু অন্যরকম ডিপি দেখবো যেটার নাম বিটমাস্ক ডিপি। নামটা শুনে ভয় লাগলেও জিনিসটা সহজ, অনেক ক্ষেত্রেই বিটমাস্ক ডিপি প্রবলেম পড়ার সাথে সাথে সলিউশন মাথায় চলে আসে। তবে এই পর্বটা পড়ার আগে তোমাকে বিট নিয়ে কাজ করা শিখতে হবে, যেমন কোনো নির্দিষ্ট পজিশনের বিট অন করা/অফ করা ইত্যাদি। এজন্য তুমি এই চমৎকার টিউটোরিয়ালটা দেখতে পারো, পুরোটা খুবই ভালো করে পড়বে কারণ এটা তোমাদের অনেক জায়গায় কাজে লাগবে। আমি এই টিউটোরিয়ালে বিট অপারেশন নিয়ে লিখছিনা কারণ অপ্রাসঙ্গিক হয়ে যাবে।
আমরা শুরুতেই ৩টি ফাংশন ডিফাইন করি।
|
1 2 3 |
int Set(int N,int pos){return N=N | (1<<pos);} int reset(int N,int pos){return N= N & ~(1<<pos);} bool check(int N,int pos){return (bool)(N & (1<<pos));} |
Set ফাংশনটি N সংখ্যাটির pos তম পজিশনের বিট ১ করে দেয়, reset ফাংশনটি 0 করে দেয় এবং check ফাংশনটি pos তম বিটে কি আছে সেটা রিটার্ণ করে। যেকোনো বিটমাস্ক ডিপি প্রবলেমে ফাংশন ৩টি দরকার হবে, বিশেষ করে Set এবং check।
আমরা একটা প্রবলেম দিয়ে শুরু করি। মনে করো তোমাকে nটা দোকান থেকে n টা জিনিস কিনতে হবে। জিনিসগুলো কিনতে তোমার a0,a1,a2,…,a(n-1) টাকা লাগে। তোমার শহরটা খুব অদ্ভূত,তুমি যখন একটা জিনিস কিনে আরেক দোকানে যাও তখন সেই দোকানদার তোমার আগের কেনা জিনিসগুলো দেখে তার দোকানের জিনিসের দাম বাড়িয়ে দেয়!! কত দাম বাড়াবে সেটা নির্ভর করবে তুমি আগে আগে কোন কোন দোকানে গিয়েছো সেটার উপর। ধরো n=2, তাহলে তোমাকে নিচের মতো একটা ম্যাট্রিক্স দেয়া থাকবে:
10 10
90 10
এখন,
যদি (i==j) হয় তাহলে matrix[i][j]=matrix[i][i]=i’তম জিনিসটির আসল দাম।
যদি (i!=j) হয় তাহলে matrix[i][j]=j’তম জিনিসটি আগে কিনলে i’তম জিনিসটির সাথে যোগ হওয়া বাড়তি দাম।
তুমি যদি শুরুতে ০ তম জিনিসটা কিনো তাহলে দাম পড়বে ১০টাকা, এরপর ১নম্বর জিনিসটা কিনলে সেটার দাম হবে ১০+৯০ টাকা, কারণ matrix[1][0]=০ নম্বর জিনিসের আগে ১ নম্বর জিনিস কিনলে যোগ হওয়া বাড়তি দাম=৯০ আর ১ নম্বর জিনিসের আসল দাম=১০, তাহলে মোট খরচ ১০+(১০+৯০)=১১০। কিন্তু তুমি যদি ১নম্বর জিনিসটা আগে কিনো তাহলে মোট খরচ ১০+(১০+১০)=৩০ টাকা।
বুঝতেই পারছো তোমার কাজ হলো খরচ মিনিমাইজ করা। n এর মান সর্বোচ্চ ১৫।
[ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। এই লেখাটার নতুন ভার্সন পাওয়া যাবে এখানে]
n এর মান খুব কম বলে বিটমাস্ক ডিপি দিয়ে প্রবলেমটি সহজেই সলভ করা যাবে। ডিপিতে আমাদের প্রথম কাজ হলো স্টেট নির্ণয় করা। এই কেনাকাটার যেকোনো সময় আমাদের অবস্থা কি কি তথ্য দিয়ে প্রকাশ করা যায়? “এখন পর্যন্ত কোন কোন জিনিস কেনা হয়েছে” এই তথ্যটাই যথেষ্ট, তাইনা? এটা জানলে আমরা পরবর্তি আরেকটি জিনিস কেনার সময় বাড়তি কত খরচ যোগ হবে জানতে পারবো, পরবর্তিতে যেই জিনিসটা কিনলে মোট খরচ কম হবে সেটা আমরা কিনবো। মনে করি এখন কথা হলো স্টেটটা রাখবো কি ভাবে?
একটা উপায় হলো $n$ টি জিনিসের জন্য এভাবে nটা স্টেট রাখা function(a0,a1,a1,….an-1), কিন্তু n এর মান বদলালে তুমি প্যারামিটার সংখ্যা বদলাবে কি ভাবে? আর ১৫টি প্যারামিটার নিয়ে কাজ করলে কোডটা ভয়াবহ জটিল হয়ে যাবে।
২য় উপায় হলো বিটমাস্ক। একটি ইন্টিজারে ৩২টি বিট থাকে। আমরা সেই সুবিধাটাই নিবো। ১ নম্বর বিট 1 হলে আমরা ১ নম্বর জিনিসটা নিয়েছি, ০ হলে নেইনি। ৩ নম্বর বিট $1$ হলে আমরা ৩ নম্বর জিনিসটা নিয়েছি, ০ হলে নেইনি। ১ এবং ৩ নম্বর বিট দুইটাই 1 হলে আমরা ২টা জিনিসই নিয়েছি।
শুরুতে আমাদের স্টেট থাকবে 0 বা বাইনারিতে “000000”। তারমানে আমরা কোনো জিনিস এখনও কিনিনি। ০তম এবং ১তম জিনিস কেনা হয়ে গেলে স্টেট হবে $3$ বা “000011” এবং $n=2$ এর জন্য এটাই আমাদের base case। n=4 এর জন্য base case হলো 15 বা “0001111”। leading zero নিয়ে চিন্তা করা দরকার নেই, এটা বোঝার সুবিধার্থে দেয়া হয়েছে। একটু চিন্তা করলেই বুঝতে পারবে mask=(2^n)-1 হলে সেটা হবে base case কারণ তখন বাইনারিতে প্রথম $n$ টা বিট ১ থাকবে, আমরা তখন শুন্য রিটার্ণ করে দিবো তখন কারণ আর কোনো জিনিস কেনা বাকি নেই।
|
1 2 3 4 5 6 7 8 9 |
int dp[(1 << 15) + 2]; int call(int mask) { if (mask == (1 << n) - 1) return 0; if (dp[mask] != -1) return dp[mask]; //Rest of the calculation } |
বেসকেস বুঝলাম, এরপরে আমাদের কাজ হবে যেসব জিনিস কেনা হয়নি সেগুলা নিয়ে চেষ্টা করে দেখা। mask এর $i$ তম পজিশনে যদি $0$ থাকে তাহলে $i$ তম জিনিসটি কেনা এখনও বাকি আছে।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
int dp[(1 << 15) + 2]; int call(int mask) { if (mask == (1 << n) - 1) return 0; if (dp[mask] != -1) return dp[mask]; //Rest of the calculation int ans = 1 << 28; //Infinite, a large value for (int i = 0; i < n; i++) { if (check(mask, i) == 0) { //Rest of the code } } return dp[mask] = ans; } |
আমরা $n$ পর্যন্ত লুপ চালিয়ে বের করে নিলাম কোনটা কোনটা নেয়া বাকি আছে। এখন $i$ তম জিনিসটার আসল দাম হলো $price=w[i][i]$। এই price এর সাথে $w[i][j]$ যোগ হবে যদি $i!=j$ হয় এবং $j$ নম্বর জিনিসটা আগেই কেনা হয়ে থাকে। $mask$ এর $j$ তম বিট চেক করে আমরা বলতে পারি $j$ তম জিনিসটা কেনা হয়েছে নাকি।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int dp[(1 << 14) + 2]; int call(int mask) { if (mask == (1 << n) - 1) return 0; if (dp[mask] != -1) return dp[mask]; int ans = 1 << 28; for (int i = 0; i < n; i++) { if (check(mask, i) == 0) { int price = w[i][i]; for (int j = 0; j < n; j++) if (i != j and check(mask, j) != 0) price += w[i][j]; int ret = price + call(Set(mask, i)); ans = min(ans, ret); } } return dp[mask] = ans; } |
j এর লুপটা দিয়ে আমরা মোট দাম বের করে নিলাম। এখন i তম জিনিসটি কিনলে পরবর্তি স্টেট কি হবে? শুধু mask এর i তম বিটটি 1 করে দিতে হবে। আমরা call(Set(mask,i)) এভাবে i তম জিনিস কিনে পরবর্তি স্টেটে চলে গেলাম। এভাবে প্রতিটি জিনিস কিনে যেটায় দাম মিনিমাম হয় সেটা রিটার্ণ করে দিলাম। কাজ শেষ! সম্পূর্ণ কোড:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
int w[20][20]; int n; int dp[(1 << 15) + 2]; int call(int mask) { if (mask == (1 << n) - 1) return 0; if (dp[mask] != -1) return dp[mask]; int mn = 1 << 28; for (int i = 0; i < n; i++) { if (check(mask, i) == 0) { int price = w[i][i]; for (int j = 0; j < n; j++) { if (i != j and check(mask, j) != 0) { price += w[i][j]; } } int ret = price + call(Set(mask, i)); mn = min(mn, ret); } } return dp[mask] = mn; } int main() { mem(dp, -1); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &w[i][j]); } } int ret = call(0); printf("%d\n", ret); return 0; } |
আমাদের call ফাংশনটি কয়টি ভিন্ন স্টেটে থাকতে পারে? n টি বিটের প্রতিটি হয় ০ হবে নাহয় ১ হবে, তাহলে স্টেট থাকতে পারে $2^15$ টি। আর ভিতরে একটা $n^2$ লুপ চলছে তাই মোট complexity (2^n)*(n^2)।
বিটমাস্ক ডিপি চেনার সবথেকে সহজ উপায় $n$ এর মান দেখা। $n$ এর মান ১৬ বা তার কম হলে খুব ভালো সম্ভাবনা আছে যে প্রবলেমটিকে বিটমাস্ক ডিপি দিয়ে সলভ করা যাবে।
বিটমাস্ক ডিপি কখন ব্যবহার করবো? বিটমাস্ক লাগবে আমাদের তখনই যখন আগের স্টেটে কোন কোন জিনিস/ডিজিট/নোড ইত্যাদি ব্যবহার করা হয়েছে সে তথ্যটি আমার বর্তমান স্টেটে লাগবে। সেই তথ্য অনুযায়ী আমরা বর্তমান স্টেট থেকে নতুন ডিজিট/নোড ইত্যাদি নিবো এবং সেই বিটটি অন করে দিয়ে সামনের স্টেটে যাবো। যখন $n$ টি বিট অন হয়ে যাবে তখন বেসকেস রিটার্ণ করে দিবো।
আমার সলভ করা প্রথম বিটমাস্ক ডিপি হলো uva 10651। আশা করি প্রবলেমটি এখন সহজেই করতে পারবে। প্রবলেমটায় একটি মাস্কের সাহায্যে কোনো সময় বোর্ডের কি অবস্থা সেই তথ্যটা রাখবে, এবং সে অবস্থায় যতগুলো চাল দেয়া সম্ভব সবগুলো দিয়ে মিনিমামটা রিটার্ণ করে দিবে।
আপাতত এগুলোই ছিলো বিটমাস্ক ডিপির বেসিক। সামনের পর্বগুলোতে আরো বিস্তারিত আলোচনার চেষ্টা করবো। এখন নিচের প্রবলেমগুলো সলভ করার চেষ্টা করো, ১ম প্রবলেমটি নিয়ে এই পর্বে আলোচনা করেছি:
Pimp My Ride
False Mirror
Agent 47
Painful Bases
[ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। এই লেখাটার নতুন ভার্সন পাওয়া যাবে এখানে]
ফেসবুকে মন্তব্য
Powered by Facebook Comments
অনেক দিন বসে ছিলাম এটার জন্য 🙂
Thanks bro…:D
বরাবরের মত অনেক সুন্দর হইছে লেখাটা। আপনার লেখাগুলার জন্য অপেক্ষা করে থাকি। তবে ভাইয়া, বিটমাস্ক ডিপি আমরা কেন ব্যবহার করবো একটু বললে ভাল হত। মেমরী বাচানো ছাড়া আর সুবিধাগুলা কি? আর বিটমাস্কিং ছাড়া কি প্রবলেমটা অন্যকোন ভাবে সল্ভ করা যেত না?
ভালো প্রশ্ন। প্রবলেমটায় n টি জিনিসের জন্য এভাবে nটা স্টেট রাখা function(a0,a1,a1,….an-1) যায়, কিন্তু n এর মান বদলালে তুমি প্যারামিটার সংখ্যা বদলাবে কি ভাবে? আর ১৫টি প্যারামিটার নিয়ে কাজ করলে কোডটা ভয়াবহ জটিল হয়ে যাবে। বিটমাস্ক লাগবে আমাদের তখনই যখন আগের স্টেটে কোন কোন জিনিস/ডিজিট/নোড ইত্যাদি ব্যবহার করা হয়েছে সে তথ্যটি আমার বর্তমান স্টেটে লাগবে। বিটমাস্ক ছাড়া একটা মাত্র ভ্যারিয়েবলের সাহায্যে ইনফরমেশনগুলা পাস করা যাবেনা।
মূল লেখায় কথাগুলো যোগ করে দিলাম।
মেমরী বাচানো ছাড়া আর সুবিধাগুলা কি? – Bitwise অপারেশন এর এক্সিকিউসন টাইম অনেক কম এবং অনেক বেশি মেমরি এফিসিয়েন্ট। তাই যদিও function(a0,a1,a1,….an-1) এর সমস্যাগুলো function(a[]) (প্যারামিটার a একটি ইন্টিজার Array) দ্বারা সমাধান করা সম্ভব, কিন্তু এটি অনেক ভালো অ্যালগোরিদম-এর পারফরমেন্সও অনেক বেশি কমিয়ে আনবে। @শাফায়েত – অনেক ভালো হয়েছে টিউটোরিয়ালটি।
ডিপিতে আমরা প্রতিটা স্টেট একটা টেবিলে সেভ করে রাখি, অ্যারে টেবিলে সেভ করবে কিভাবে? ম্যাপিং করা যেতে পারে কিন্তু তাহলে প্রতিবার টেবিল access করতে logn টাইম লাগবে, কোড নিশ্চিতভাবে tle দিবে।
ধন্যবাদ।
টেবিল (matrix) একটা Data Structure যেটা আমাদেরকে আগের সেভ করা তথ্য গুলো দ্রুত খুঁজে পেতে (Lookup) সাহায্য করবে – তাই না? টেবিল যে সবসময় একটা 2D Integer Array হতে হবে এমন তো না – আমার ইমপ্লিমেন্টেশন এ হয়ত আমি matrix Array টার ডাইমেনশন বাড়িয়ে নিতে পারি (Java-তে একটা Array কিন্তু একটা Object)। আমি আসলে শুধুমাত্র এই লাইন এর জন্য, “বিটমাস্ক ছাড়া একটা মাত্র ভ্যারিয়েবলের সাহায্যে ইনফরমেশনগুলা পাস করা যাবেনা” আমার আগের কমেন্টটা করেছিলাম। ধন্যবাদ।
আসলে একটি ভ্যারিয়েবল বলতে আমি একটি single integer বুঝিয়েছিলাম, array তো একটা collection of variable তাইনা? জাভাতে আপনি একটি অ্যারেকে টেবিল থেকে O(1) এ খুজে বের করতে পারবেন? আমার জানার ভুল হতে পারে তবে আমার মনে হয় পারবেননা, অবজেক্টকে টেবিলে রাখতে হলে হ্যাশটেবিলে রাখতে হবে, যেখান থেকে খুজতে logn সময় লাগে। সি তেও আপনি একটা ক্লাস বা স্ট্রাকচার অ্যারে রেখে সেটাকে অবজেক্ট বানিয়ে টেবিলে রাখতে পারেন, তখনও হ্যাশটেবিল ব্যবহার করতে হবে।
ভুল বললে ধরিয়ে দিতে পারেন, আলোচনা সবসময়ই শিখতে সাহায্য করে :)।
এডিট: জাভাতে হ্যাশম্যাপ থেকে অ্যাভারেজে O(1) সময়ে অবজেক্ট খুজে পাওয়া সম্ভব। সি++ এ ম্যাপে bst ব্যবহার করা যেটায় logn এ সার্চ করতে হয় কিন্তু জাভার hashtable এ অ্যাভারেজে O(1) এ সার্চ করে তবে worst case এ সেটা O(n) এ চলে যায়।
Don’t Get Me Wrong 🙂 – আমি আসলে ভুল ধরিয়ে দিতে চাচ্ছিনা। একটা Function এ Parameter পাঠানোর সমস্যার চেয়ে Memory এবং Runtime Efficiency কে আমার কাছে গুরুত্বপূর্ণ মনে হয়েছে। কারণ প্রথম সমস্যাটা অনেক বেশি Language Specific.
আর Java – Array – Object নিয়ে আমি যা বলতে চেয়েছি সেটা নিচের লিংক এক্সপ্লোর করলে জানা যাবে (জাভাতে আপনি একটি অ্যারেকে টেবিল থেকে O(1) এ খুজে বের করতে পারবেন? – সম্ভব) –
১। Java Language Specification – Chapter 10. Arrays.
২। Is An Array an Object in Java.
ধন্যবাদ 🙂
O(1) এ খুজে বের করা যাবে এই কথা specifically কোথায় লেখা আছে বলতে পারবেন? অ্যারে অবজেক্ট সেটা অবশ্যই ঠিক আছে, একটা অবজেক্টকে identify করতে হলে একটা হ্যাশভ্যালু ক্যালকুলেট করা দরকার, তারপর সেটাকে হ্যাশটেবিল থেকে বের করতে হবে। আপনি একটু specific ভাবে দেখান কোথায় লেখা আছে সেটা, লিংকগুলোতে আমি তেমন কিছু পাইনি। অথবা আপনি সেরকম কোনো কোড পোস্ট করতে পারেন।
আমি নেটে সার্চ করলাম একটু, কিছু নতুন তথ্য জানলাম যেগুলো জানা ছিলোনা। “Hash tables are O(1) average and amortized case complexity, however is suffers from O(n) worst case time complexity. ” এরকম লেখা পেলাম। আমি ধারণা করেছিলাম জাভার হ্যাশটেবিল সি++ এর ম্যাপের মতোই logn এ সার্চ করে। তারমানে জাভাতে অবজেক্ট average কেসে কেস এ O(1) এ খুজে পাওয়া সম্ভব। ধন্যবাদ আপনাকে।
Check this code, http://pastebin.com/2pAwtuJx, specially line number 19 and 23/27 where previously stored values were being retrieved.
হ্যা আমিও নেটে খুজে পেয়েছি, উপরে আরেকটি কমেন্ট করেছি।
দারুন হইছে ভাইয়া …… 🙂