গ্রিডি অ্যালগরিদম হলো এমন একটি পদ্ধতি যেখানে সমস্যার প্রতিটি ধাপে সর্বোত্তম স্থানীয় সমাধান বেছে নিয়ে চূড়ান্ত সমাধানে পৌঁছানো হয়। এখানে গ্রিডি ভিত্তিক দুটি বিখ্যাত সমস্যার উদাহরণ দেয়া হলো: Fractional Knapsack এবং Huffman Coding।
১. Fractional Knapsack Problem
Fractional Knapsack Problem হলো একটি গ্রিডি সমস্যা যেখানে একটি নির্দিষ্ট ওজন সীমার ব্যাগ থাকে এবং বিভিন্ন আইটেমের ওজন ও মূল্য দেয়া থাকে। আমরা চাই ব্যাগে কতটুকু আইটেম রাখতে পারি, যাতে মূল্য সর্বাধিক হয়। এখানে প্রতিটি আইটেমকে ভগ্নাংশ আকারে নেয়া যায়, অর্থাৎ সম্পূর্ণ না নিয়েও অর্ধেক বা যেকোনো অংশ রাখা যায়।
উদাহরণ
ধরা যাক আমাদের কাছে ৩টি আইটেম আছে:
- আইটেম ১:
{weight: 10, value: 60} - আইটেম ২:
{weight: 20, value: 100} - আইটেম ৩:
{weight: 30, value: 120} - ব্যাগের সর্বোচ্চ ওজন:
50
এই ক্ষেত্রে আমাদের লক্ষ্য হলো ব্যাগের মধ্যে সর্বাধিক মূল্যপূর্ণ আইটেমের ভগ্নাংশ রাখা।
সমাধান পদ্ধতি
- প্রতিটি আইটেমের মূল্য-ওজন অনুপাত (
value/weight) হিসাব করা হয়। - অনুপাত অনুযায়ী আইটেমগুলোকে সাজানো হয়, সর্বোচ্চ অনুপাতটি প্রথমে আসে।
- প্রতিটি আইটেমকে ওজন সীমা পর্যন্ত ব্যাগে রাখা হয়। যদি পুরো ওজন না নিতে পারা যায়, তাহলে প্রয়োজন অনুযায়ী ভগ্নাংশ নেয়া হয়।
উদাহরণ কোড (Python):
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.ratio = value / weight
def fractional_knapsack(items, W):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if W >= item.weight:
W -= item.weight
total_value += item.value
else:
total_value += item.ratio * W
break
return total_value
# উদাহরণ ব্যবহার
items = [Item(10, 60), Item(20, 100), Item(30, 120)]
max_weight = 50
print("Maximum value:", fractional_knapsack(items, max_weight))
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(n log n) (সাজানোর জন্য), যেখানে
nহলো আইটেম সংখ্যা। - স্পেস কমপ্লেক্সিটি: O(1), কারণ অতিরিক্ত মেমোরি প্রয়োজন নেই।
ব্যবহার:
Fractional Knapsack বাস্তবজীবনে প্রয়োজনীয় যেমন পোর্টফোলিও অপ্টিমাইজেশন, লগিস্টিক্স, এবং অন্যান্য ক্ষেত্রে কার্যকর।
২. Huffman Coding
Huffman Coding হলো একটি গ্রিডি অ্যালগরিদম, যা ডেটা কম্প্রেশন বা এনকোডিংয়ে ব্যবহৃত হয়। এটি এমন একটি এনকোডিং পদ্ধতি যা চরিত্রগুলোর ফ্রিকোয়েন্সির উপর ভিত্তি করে ছোট বা দীর্ঘ বিট এনকোড তৈরি করে, ফলে ডেটা কম্প্রেশন সহজ হয়।
উদাহরণ
ধরা যাক একটি স্ট্রিং আছে: ABRACADABRA প্রতিটি চরিত্রের ফ্রিকোয়েন্সি নিচে দেয়া হলো:
A= 5 বারB= 2 বারR= 2 বারC= 1 বারD= 1 বার
এই ফ্রিকোয়েন্সির ভিত্তিতে Huffman Tree তৈরি করে প্রতিটি চরিত্রের জন্য একটি ছোট বিট এনকোড তৈরি করা হবে।
সমাধান পদ্ধতি
- প্রতিটি চরিত্রকে একটি লিফ নোড হিসেবে নিয়ে একটি মিনি-হিপে যুক্ত করা হয়।
- ফ্রিকোয়েন্সি অনুযায়ী নোডগুলোকে সাজানো হয়। সবচেয়ে কম ফ্রিকোয়েন্সি দুইটি নোড একত্রে নিয়ে নতুন নোড তৈরি করা হয় এবং হিপে আবার যুক্ত করা হয়।
- এই প্রক্রিয়া পুনরাবৃত্তি হয় যতক্ষণ না একটি একক রুট নোড পাওয়া যায়, যা Huffman Tree এর শীর্ষে থাকে।
- প্রতিটি লিফ নোডে বাঁ দিকে
0এবং ডানে1চিহ্নিত করে প্রতিটি চরিত্রের বিট এনকোড নির্ধারণ করা হয়।
উদাহরণ কোড (Python):
import heapq
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_encoding(frequencies):
heap = [Node(char, freq) for char, freq in frequencies.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
root = heap[0]
codes = {}
create_codes(root, "", codes)
return codes
def create_codes(node, code, codes):
if node:
if node.char:
codes[node.char] = code
create_codes(node.left, code + "0", codes)
create_codes(node.right, code + "1", codes)
# উদাহরণ ব্যবহার
frequencies = {'A': 5, 'B': 2, 'R': 2, 'C': 1, 'D': 1}
codes = huffman_encoding(frequencies)
print("Huffman Codes:", codes)
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(n log n), যেখানে
nহলো ইউনিক চরিত্রের সংখ্যা, কারণ হিপে অপারেশন এবং ট্রি নির্মাণের জন্য। - স্পেস কমপ্লেক্সিটি: O(n), কারণ ট্রি গঠনে অতিরিক্ত মেমোরি প্রয়োজন হয়।
ব্যবহার:
Huffman Coding টেক্সট কম্প্রেশন, ফাইল এনকোডিং এবং ডেটা ট্রান্সমিশন প্রোটোকলে ব্যাপকভাবে ব্যবহৃত হয়, যেমন ZIP ফাইল ফরম্যাট, JPEG ইমেজ কম্প্রেশন।
উপসংহার
- Fractional Knapsack সমস্যা সর্বোচ্চ মূল্য অর্জনের জন্য সহজে গ্রিডি অ্যালগরিদম ব্যবহার করে, যেখানে ভগ্নাংশের অনুমতি দেয়া হয়।
- Huffman Coding ডেটা কম্প্রেশন সমস্যার জন্য অত্যন্ত কার্যকর একটি গ্রিডি পদ্ধতি যা ডেটাকে কম বিটে সংকুচিত করে।
দুটি সমস্যাই গ্রিডি অ্যালগরিদমের মাধ্যমে সহজে সমাধানযোগ্য এবং বাস্তব জীবনে বিভিন্ন ক্ষেত্রেই প্রয়োজনীয়।
