ডাইনামিক প্রোগ্রামিং (Dynamic Programming) একটি অ্যালগরিদমিক কৌশল যা জটিল সমস্যাকে ছোট উপ-সমস্যায় ভাগ করে সমাধান করে। এই পদ্ধতিতে উপ-সমস্যাগুলোর সমাধান সংরক্ষণ করে রাখা হয় যাতে একই সমস্যার পুনরাবৃত্তি এড়ানো যায়। ডাইনামিক প্রোগ্রামিং ব্যবহার করে টাইম কমপ্লেক্সিটি উল্লেখযোগ্যভাবে কমানো যায়, বিশেষত যেখানে সমস্যার সমাধান পুনরাবৃত্তিমূলকভাবে করতে হয়।
ডাইনামিক প্রোগ্রামিংয়ের প্রধান দুটি বৈশিষ্ট্য:
১. অপটিমাল সাবস্ট্রাকচার (Optimal Substructure): সমস্যার উপ-সমস্যাগুলোর সমাধান ব্যবহার করে মূল সমস্যার সমাধান বের করা সম্ভব হলে অপটিমাল সাবস্ট্রাকচার বৈশিষ্ট্য রয়েছে। উদাহরণস্বরূপ, ফিবোনাচি সিরিজের \( F(n) = F(n-1) + F(n-2) \) ফর্মুলাটি উপ-সমস্যাগুলোর সমাধান দিয়ে তৈরি হয়।
২. ওভারল্যাপিং সাব-প্রব্লেমস (Overlapping Subproblems): সমস্যার সমাধান করতে একই উপ-সমস্যার সমাধান বারবার করতে হয়। ডাইনামিক প্রোগ্রামিং এই উপ-সমস্যাগুলোর সমাধান সংরক্ষণ করে রেখে পুনরায় সমাধান করা থেকে বিরত রাখে।
ডাইনামিক প্রোগ্রামিংয়ের দুইটি কৌশল:
১. মেমোইজেশন (Memoization): মেমোইজেশন একটি টপ-ডাউন (Top-Down) পদ্ধতি যেখানে উপ-সমস্যাগুলোর সমাধান সংরক্ষণ করা হয় এবং প্রয়োজন অনুযায়ী পুনরায় ব্যবহার করা হয়। প্রতিবার উপ-সমস্যা সমাধানের আগে দেখা হয় সমাধানটি আগে করা হয়েছে কি না। যদি আগে করা থাকে তবে সেই সমাধানই নেওয়া হয়।
২. ট্যাবুলেশন (Tabulation): ট্যাবুলেশন একটি বটম-আপ (Bottom-Up) পদ্ধতি যেখানে ছোট উপ-সমস্যাগুলো সমাধান করে তাদের ফলাফল টেবিল আকারে সংরক্ষণ করা হয় এবং পরে বড় সমস্যার সমাধান দেওয়া হয়।
উদাহরণসমূহ:
১. ফিবোনাচি সিরিজ (Fibonacci Series)
ফিবোনাচি সিরিজের জন্য ডাইনামিক প্রোগ্রামিং ব্যবহার করা হলে মেমোইজেশন পদ্ধতিতে প্রতিটি ফিবোনাচি মান সংরক্ষণ করা হয় এবং বারবার পুনরাবৃত্তি এড়ানো হয়।
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
২. কাঁধে ব্যাগ সমস্যা (Knapsack Problem)
একটি নির্দিষ্ট ওজন এবং মান সহ অনেক আইটেম রয়েছে, এবং একটি ব্যাগে সর্বাধিক ওজন নিয়ে সর্বোচ্চ মানের আইটেম নির্বাচন করতে হবে।
def knapsack(weight, value, capacity, n):
dp = [[0 for x in range(capacity + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(capacity + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weight[i-1] <= w:
dp[i][w] = max(value[i-1] + dp[i-1][w-weight[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
৩. লংগেস্ট কমন সাবসিকুয়েন্স (Longest Common Subsequence - LCS)
দুটি স্ট্রিংয়ে সর্বোচ্চ দৈর্ঘ্যের কমন সাবসিকুয়েন্স বের করা।
def lcs(X, Y):
m = len(X)
n = len(Y)
dp = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
dp[i][j] = 0
elif X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
ডাইনামিক প্রোগ্রামিংয়ের সুবিধা ও অসুবিধা:
সুবিধা:
- পুনরাবৃত্তি সমস্যা সমাধানে কার্যকরী।
- টাইম কমপ্লেক্সিটি কমানো যায়।
- পুনরাবৃত্তি এড়ানো যায়।
অসুবিধা:
- অতিরিক্ত মেমোরি ব্যবহার হয়।
- ট্যাবুলেশন বা মেমোইজেশন বোঝা একটু জটিল হতে পারে।
ডাইনামিক প্রোগ্রামিং সমস্যা সমাধানে খুবই শক্তিশালী একটি টুল, বিশেষ করে যেখানে পুনরাবৃত্তিমূলক সমাধানের প্রয়োজন হয়।
ডাইনামিক প্রোগ্রামিং (Dynamic Programming) একটি অ্যালগরিদম ডিজাইন কৌশল, যা বড় সমস্যাকে ছোট উপ-সমস্যায় বিভক্ত করে এবং পূর্বে সমাধান করা উপ-সমস্যার ফলাফল সংরক্ষণ করে পরবর্তীতে পুনরায় ব্যবহারের মাধ্যমে কার্যক্ষমতা বৃদ্ধি করে। সাধারণত, পুনরাবৃত্ত উপ-সমস্যাগুলি সঞ্চিত করে আবার সমাধান করতে না হওয়ায় ডাইনামিক প্রোগ্রামিং অনেক সময় এবং মেমরি সাশ্রয়ী হয়।
ডাইনামিক প্রোগ্রামিং এর ধারণা
ডাইনামিক প্রোগ্রামিংয়ের মূল ধারণা হল সমস্যা সমাধানের সময় ছোট ছোট উপ-সমস্যার সমাধান সংরক্ষণ করা এবং প্রয়োজন হলে সেই ফলাফল পুনরায় ব্যবহার করা। এতে করে একই কাজ বারবার না করেও দ্রুত ফলাফল পাওয়া যায়। ডাইনামিক প্রোগ্রামিং দুটি উপায়ে কাজ করতে পারে:
- টপ-ডাউন (Top-Down) পদ্ধতি বা মেমোইজেশন: এতে রিকার্সিভ পদ্ধতিতে কাজ করা হয়, যেখানে একটি সমস্যার সমাধান প্রথমে বৃহৎ আকারে শুরু করে ধীরে ধীরে ছোট উপ-সমস্যায় বিভক্ত করা হয় এবং প্রতিটি উপ-সমস্যার সমাধান একটি ডেটা স্ট্রাকচারে সংরক্ষণ করা হয়।
- বটম-আপ (Bottom-Up) পদ্ধতি বা ট্যাবুলেশন: এখানে ছোট উপ-সমস্যাগুলি প্রথমে সমাধান করা হয় এবং তাদের ফলাফল ক্রমান্বয়ে বড় সমস্যায় ব্যবহার করা হয়।
ডাইনামিক প্রোগ্রামিং প্রয়োজনীয়তা
ডাইনামিক প্রোগ্রামিং তখনই প্রয়োজন হয় যখন একটি বড় সমস্যার সমাধানের জন্য পূর্বে সমাধান করা উপ-সমস্যাগুলি বারবার ব্যবহার করা হয়। নিচে ডাইনামিক প্রোগ্রামিং ব্যবহারের কিছু গুরুত্বপূর্ণ প্রয়োজনীয়তা দেওয়া হলো:
অপ্টিমাল সাবস্ট্রাকচার (Optimal Substructure): যদি একটি বড় সমস্যার সমাধান তার উপ-সমস্যাগুলোর সমাধান দ্বারা নির্ধারণ করা যায়, তাহলে সেখানে ডাইনামিক প্রোগ্রামিং ব্যবহার করা যেতে পারে। অর্থাৎ, একটি বড় সমস্যার সমাধান প্রাপ্তি ছোট উপ-সমস্যাগুলোর সমাধান দ্বারা সম্ভব।
ওভারল্যাপিং সাব-প্রব্লেম (Overlapping Subproblems): যখন একই উপ-সমস্যা বারবার সমাধান করতে হয়, তখন ডাইনামিক প্রোগ্রামিং কার্যকর হয়। এতে করে পুরনো ফলাফল সংরক্ষণ করে সময় সাশ্রয় করা যায়।
ডাইনামিক প্রোগ্রামিং-এর উদাহরণ
১. ফিবোনাচি সিরিজ
ফিবোনাচি সিরিজের সংখ্যা নির্ণয়ে একটি উপাদান বারবার প্রয়োজন হয়, তাই ডাইনামিক প্রোগ্রামিং ব্যবহার করে দ্রুত সমাধান পাওয়া যায়।
টপ-ডাউন পদ্ধতি (মেমোইজেশন):
def fibonacci(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
বটম-আপ পদ্ধতি (ট্যাবুলেশন):
def fibonacci(n):
fib_table = [0] * (n + 1)
fib_table[1] = 1
for i in range(2, n + 1):
fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
return fib_table[n]
২. নাইভসেক (Knapsack Problem)
Knapsack সমস্যা হলো ডাইনামিক প্রোগ্রামিংয়ের আরেকটি উদাহরণ, যেখানে বিভিন্ন আকার ও মূল্যসম্পন্ন বস্তু থেকে নির্দিষ্ট আকারের একটি ব্যাগে সর্বাধিক মূল্যের বস্তু নির্বাচন করতে হয়।
ডাইনামিক প্রোগ্রামিং এর সুবিধা
- সময় সাশ্রয়ী: ডাইনামিক প্রোগ্রামিং একই উপ-সমস্যাকে বারবার সমাধান না করে তার ফলাফল সংরক্ষণ করে দ্রুত ফলাফল প্রদান করে।
- জটিল সমস্যা সমাধানে সহায়ক: ডাইনামিক প্রোগ্রামিং বড় এবং জটিল সমস্যা যেমন, গ্রাফ, কন্ট্রোল সিস্টেম ডিজাইন, বায়োইনফরমেটিক্স এবং ফিনান্সিয়াল মডেলিং এ প্রয়োগ করা হয়।
ডাইনামিক প্রোগ্রামিং-এর সীমাবদ্ধতা
- মেমরি ব্যবহার বেশি হতে পারে: বড় ডেটাসেটের জন্য, সঞ্চিত ফলাফল অনেক মেমরি নিতে পারে।
- সঠিক উপযুক্ততা না থাকলে অপ্রয়োজনীয়: সব সমস্যায় ডাইনামিক প্রোগ্রামিং উপযোগী নয়; যেখানে উপ-সমস্যাগুলি পুনরাবৃত্ত হয় না, সেখানে এটি কার্যকর নয়।
ডাইনামিক প্রোগ্রামিং বিভিন্ন পুনরাবৃত্ত এবং অপ্টিমাইজেশন সমস্যার ক্ষেত্রে একটি শক্তিশালী সমাধান কৌশল, যা বড় সমস্যা সমাধানকে দ্রুত এবং কার্যকরভাবে সম্পন্ন করতে সহায়তা করে।
Longest Common Subsequence এবং 0/1 Knapsack Problem উভয়ই কম্পিউটার বিজ্ঞানে বিখ্যাত বেসিক সমস্যা যা ডায়নামিক প্রোগ্রামিংয়ের মাধ্যমে সমাধান করা হয়। নিচে প্রতিটি সমস্যার বিশ্লেষণ এবং উদাহরণ দেয়া হলো:
১. Longest Common Subsequence (LCS)
Longest Common Subsequence সমস্যায় দুটি স্ট্রিং দেয়া থাকে, এবং আমাদের কাজ হলো সবচেয়ে বড় সাবসিকোয়েন্সটি খুঁজে বের করা, যা উভয় স্ট্রিংয়ে উপস্থিত থাকে।
উদাহরণ
যদি আমাদের দুটি স্ট্রিং থাকে:
X = "ABCBDAB"Y = "BDCAB"
তাহলে এই দুটি স্ট্রিংয়ের মধ্যে Longest Common Subsequence হবে BDAB, যার দৈর্ঘ্য ৪।
সমাধান পদ্ধতি
আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করে এই সমস্যাটি সমাধান করতে পারি। প্রথমে একটি টেবিল তৈরি করি, যেখানে LCS[i][j] মানে হলো X এর প্রথম i অক্ষর এবং Y এর প্রথম j অক্ষরের মধ্যে Longest Common Subsequence এর দৈর্ঘ্য।
- যদি
X[i-1] == Y[j-1], তাহলেLCS[i][j] = LCS[i-1][j-1] + 1 - অন্যথায়,
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
কোড (Python):
def lcs(X, Y):
m, n = len(X), len(Y)
LCS = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])
return LCS[m][n]
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(m * n), যেখানে
mএবংnযথাক্রমেXএবংYএর দৈর্ঘ্য। - স্পেস কমপ্লেক্সিটি: O(m * n), কারণ টেবিল সংরক্ষণ করতে অতিরিক্ত মেমোরি লাগে।
২. 0/1 Knapsack Problem
0/1 Knapsack Problem সমস্যায় একটি ব্যাগের নির্দিষ্ট ওজন সীমা দেয়া থাকে এবং বিভিন্ন আইটেম দেয়া থাকে। প্রতিটি আইটেমের ওজন এবং মান (value) দেয়া থাকে। আমাদের কাজ হলো ব্যাগটি ওজন সীমা পূরণ না করেই আইটেমগুলোর মূল্য সর্বাধিক করা। এখানে 0/1 বলতে বোঝায়, প্রতিটি আইটেম হয় ব্যাগে থাকবে না হয় থাকবে না (ভগ্নাংশ নয়)।
উদাহরণ
ধরা যাক আমাদের কাছে ৪টি আইটেম আছে:
- আইটেম:
[{weight: 1, value: 10}, {weight: 3, value: 40}, {weight: 4, value: 50}, {weight: 5, value: 70}] - ব্যাগের সর্বোচ্চ ওজন:
8
এই ক্ষেত্রে, সর্বাধিক মূল্য অর্জন করতে ব্যাগে কিছু নির্দিষ্ট আইটেম রাখতে হবে।
সমাধান পদ্ধতি
ডায়নামিক প্রোগ্রামিং ব্যবহার করে এই সমস্যাটি সমাধান করা যায়। প্রথমে একটি টেবিল তৈরি করি, যেখানে dp[i][w] অর্থাৎ প্রথম i আইটেম এবং ব্যাগের ওজন w এর মধ্যে সর্বাধিক মূল্য।
- যদি
weight[i] > wঅর্থাৎ আইটেমের ওজনwএর বেশি হয়, তাহলেdp[i][w] = dp[i-1][w] - অন্যথায়,
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])
কোড (Python):
def knapsack(weights, values, W):
n = len(values)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(n * W), যেখানে
nহলো আইটেমের সংখ্যা এবংWহলো ব্যাগের সর্বোচ্চ ওজন। - স্পেস কমপ্লেক্সিটি: O(n * W), কারণ টেবিল সংরক্ষণ করতে অতিরিক্ত মেমোরি প্রয়োজন।
উপসংহার
- Longest Common Subsequence: দুটি স্ট্রিংয়ের মধ্যে সবচেয়ে বড় মিল খুঁজতে ব্যবহৃত হয়।
- 0/1 Knapsack Problem: সর্বাধিক মূল্য অর্জনের জন্য নির্দিষ্ট ওজন সীমার মধ্যে আইটেম বাছাই করতে ব্যবহৃত হয়।
দুটি সমস্যাই ডায়নামিক প্রোগ্রামিংয়ের গুরুত্বপূর্ণ সমস্যা এবং বিভিন্ন ক্ষেত্রে প্রয়োজনীয় সমাধান প্রদান করতে সক্ষম।
মেমোইজেশন এবং ট্যাবুলেশন হলো ডায়নামিক প্রোগ্রামিং (DP) এর দুটি গুরুত্বপূর্ণ কৌশল, যা পুনরাবৃত্ত সমস্যাগুলির কার্যকারিতা বাড়াতে ব্যবহৃত হয়। এ দুটি কৌশল একই ধরনের সমস্যা সমাধানে ভিন্ন ভিন্ন পন্থা ব্যবহার করে।
১. মেমোইজেশন (Memoization)
মেমোইজেশন হলো টপ-ডাউন পদ্ধতির একটি কৌশল, যেখানে একটি ফাংশন কোনো সমস্যা সমাধান করার সময় ফলাফলগুলো ক্যাশ করে রাখে। যদি আবার সেই একই সাব-প্রবলেম সমাধানের প্রয়োজন হয়, তাহলে আগের ফলাফলটি সরাসরি ব্যবহার করা হয়। এতে করে পুনরাবৃত্ত সাব-প্রবলেমগুলো বারবার সমাধান করতে হয় না, ফলে টাইম কমপ্লেক্সিটি কমে যায়।
কিভাবে মেমোইজেশন কাজ করে:
- কোনো ফাংশন প্রথমবার একটি সাব-প্রবলেম সমাধান করলে সেই ফলাফলটি একটি ডেটা স্ট্রাকচারে (যেমন অ্যারে বা ডিকশনারি) সংরক্ষণ করে।
- যদি পরবর্তীতে আবার একই সাব-প্রবলেম সমাধানের প্রয়োজন হয়, তাহলে ক্যাশ থেকে সরাসরি ফলাফলটি ব্যবহার করা হয়।
উদাহরণ: ফিবোনাচ্চি সিরিজ গণনা
পুনরাবৃত্তভাবে ফিবোনাচ্চি সিরিজ গণনা করলে অনেকবার একই মান বের করতে হয়, ফলে টাইম কমপ্লেক্সিটি বৃদ্ধি পায়। কিন্তু মেমোইজেশন ব্যবহারে আমরা একবার গণনা করা মান সংরক্ষণ করে রাখতে পারি।
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
টাইম কমপ্লেক্সিটি: O(n) (কারণ প্রতিটি মান একবার করে ক্যালকুলেট করা হয় এবং ক্যাশ থেকে পড়া হয়)
২. ট্যাবুলেশন (Tabulation)
ট্যাবুলেশন হলো বটম-আপ পদ্ধতির একটি কৌশল, যেখানে সমস্যাটি ছোট ছোট সাব-প্রবলেমে ভাগ করা হয় এবং প্রতিটি সাব-প্রবলেমের সমাধান একটি টেবিলে সংরক্ষণ করা হয়। পরে সাব-প্রবলেমগুলোর সাহায্যে মূল সমস্যার সমাধান বের করা হয়।
কিভাবে ট্যাবুলেশন কাজ করে:
- প্রথমে ছোট ছোট সাব-প্রবলেমগুলো সমাধান করা হয় এবং ফলাফলগুলো একটি টেবিলে সংরক্ষণ করা হয়।
- টেবিল থেকে ধীরে ধীরে বড় সমস্যার সমাধান বের করা হয়।
উদাহরণ: ফিবোনাচ্চি সিরিজ গণনা (ট্যাবুলেশন)
def fib(n):
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
টাইম কমপ্লেক্সিটি: O(n) এবং স্পেস কমপ্লেক্সিটি O(n) (তবে স্পেস কমপ্লেক্সিটি কমানোর জন্য শুধুমাত্র দুটি ভেরিয়েবল ব্যবহার করে করা সম্ভব)
মেমোইজেশন বনাম ট্যাবুলেশন
| বৈশিষ্ট্য | মেমোইজেশন | ট্যাবুলেশন |
|---|---|---|
| পদ্ধতি | টপ-ডাউন | বটম-আপ |
| ব্যবহার | রিকার্সিভ ফাংশন | লুপ ভিত্তিক সমাধান |
| ফলাফল সংরক্ষণ | প্রয়োজনীয় সাব-প্রবলেমের জন্য | প্রতিটি সাব-প্রবলেমের জন্য |
| টাইম কমপ্লেক্সিটি | O(n) | O(n) |
| কোডের জটিলতা | তুলনামূলক কম | কিছুটা বেশি |
| উপযুক্ত ক্ষেত্র | যখন বড় সমস্যা সাব-প্রবলেমে বিভক্ত | নির্দিষ্ট ধাপে সমস্যা সমাধান |
সারসংক্ষেপ
- মেমোইজেশন টপ-ডাউন পদ্ধতি যেখানে রিকার্সন ব্যবহার করে সমাধান করা হয় এবং প্রয়োজনীয় সাব-প্রবলেম ক্যাশ করা হয়।
- ট্যাবুলেশন বটম-আপ পদ্ধতি যেখানে লুপের মাধ্যমে ছোট সাব-প্রবলেমগুলোর সমাধান করে মূল সমস্যার সমাধান বের করা হয়।
দুইটি কৌশলই কার্যকর, তবে নির্দিষ্ট সমস্যার ধরণ এবং কোডিং স্টাইল অনুযায়ী একটিকে বেছে নেওয়া হয়।
Read more
