গ্রিডি প্যারাডাইম ও এক্সচেঞ্জ আর্গুমেন্ট

১ · গ্রিডি প্যারাডাইম কী

গ্রিডি অ্যালগরিদমGreedy Algorithmএমন একটি অ্যালগরিদমিক কৌশল যা প্রতিটি ধাপে বর্তমান পরিস্থিতিতে স্থানীয়ভাবে (locally) সবচেয়ে ভালো দেখতে চয়েসটি বেছে নেয়, এবং সেই সিদ্ধান্ত পরে আর পরিবর্তন করে না। এটি DSA কোর্সে ইতিমধ্যে পরিচিত একটি ধারণা — সেখানে অ্যাক্টিভিটি সিলেকশন, হাফম্যান কোডিং, বা MST-এর মতো নির্দিষ্ট অ্যালগরিদমগুলো কীভাবে কাজ করে তা দেখানো হয়েছে। এই কোর্স ধরে নেয় আপনি সেই মেকানিক্স জানেন — এখানে প্রশ্নটা ভিন্ন: কেন এই লোকাল সিদ্ধান্তগুলোর সমষ্টি গ্লোবাল অপটিমাম দেয়, তা কীভাবে প্রমাণ করব।

একটি গ্রিডি অ্যালগরিদমের সাধারণ কাঠামো প্রায় সবসময় একই রকম:

এই দুটো শর্ত একসাথে থাকলে ইনডাকশন দিয়ে দেখানো যায় যে ধাপে ধাপে লোকাল চয়েস নেওয়াই গ্লোবাল অপটিমাম দেয়। অপটিমাল সাবস্ট্রাকচার M6/L24-এ DP-র প্রেক্ষিতেও ফিরে আসবে — পার্থক্য হলো DP-তে ওভারল্যাপিং সাবপ্রবলেম সমাধান করে সেরাটা তুলনা করা হয়, গ্রিডিতে একটিমাত্র চয়েস নিয়েই এগিয়ে যাওয়া হয় (কারণ প্রমাণ করা থাকে যে অন্য কোনো চয়েস তুলনা করার দরকারই নেই)।

২ · কেন "কয়েকটা উদাহরণে কাজ করেছে" যথেষ্ট নয়

একটি গ্রিডি স্ট্র্যাটেজি দেখতে স্বাভাবিক ও যুক্তিসঙ্গত মনে হতে পারে, এমনকি কিছু টেস্ট কেসে সঠিক উত্তরও দিতে পারে — কিন্তু তার মানে এই নয় যে এটি সবসময় সঠিক। নিচের কোড সেলে একটি ক্লাসিক উদাহরণ দেখানো হয়েছে: কয়েন-চেঞ্জ সমস্যায় "সবসময় সবচেয়ে বড় ডিনমিনেশন থেকে যতটা সম্ভব নাও" — এই গ্রিডি স্ট্র্যাটেজি প্রচলিত মুদ্রা ব্যবস্থায় ({1, 5, 10, 25}) ঠিকই কাজ করে, কিন্তু একটি ভিন্ন (কিন্তু সম্পূর্ণ বৈধ) ডিনমিনেশন সেটে ({1, 3, 4}) ভুল উত্তর দেয় — এবং আমরা তা ধরে নিচ্ছি না, প্রকৃতপক্ষে ব্রুট-ফোর্স দিয়ে যাচাই করছি।

from itertools import combinations_with_replacement

def greedy_coin_change(amount, denominations):
    # সবসময় সবচেয়ে বড় ডিনমিনেশন থেকে যতটা সম্ভব নাও
    denominations = sorted(denominations, reverse=True)
    count = 0
    used = []
    remaining = amount
    for d in denominations:
        take = remaining // d
        if take:
            used.extend([d] * take)
            count += take
            remaining -= d * take
    return count, used, remaining

def brute_force_min_coins(amount, denominations):
    # প্রকৃত ন্যূনতম কয়েন সংখ্যা: k = 0, 1, 2, ... ক্রমান্বয়ে বাড়িয়ে প্রথম বৈধ কম্বিনেশন খোঁজা
    for k in range(0, amount + 1):
        for combo in combinations_with_replacement(denominations, k):
            if sum(combo) == amount:
                return k, combo
    return None, None

# কেস ১: প্রচলিত মুদ্রা ব্যবস্থা -- গ্রিডি এখানে কাকতালীয়ভাবে সঠিক
std_coins = [1, 5, 10, 25]
amount1 = 41
g_count1, g_used1, rem1 = greedy_coin_change(amount1, std_coins)
b_count1, b_used1 = brute_force_min_coins(amount1, std_coins)
print("প্রচলিত ডিনমিনেশন {1,5,10,25}, amount=41")
print("  গ্রিডি:      ", g_count1, "কয়েন ->", g_used1)
print("  ব্রুট-ফোর্স: ", b_count1, "কয়েন ->", list(b_used1))
assert rem1 == 0
print("  গ্রিডি কি অপটিমাল?", g_count1 == b_count1)

# কেস ২: একটি ইচ্ছাকৃতভাবে বেছে নেওয়া ডিনমিনেশন সেট -- গ্রিডি ব্যর্থ হয়
odd_coins = [1, 3, 4]
amount2 = 6
g_count2, g_used2, rem2 = greedy_coin_change(amount2, odd_coins)
b_count2, b_used2 = brute_force_min_coins(amount2, odd_coins)
print("\nঅস্বাভাবিক ডিনমিনেশন {1,3,4}, amount=6")
print("  গ্রিডি:      ", g_count2, "কয়েন ->", g_used2)
print("  ব্রুট-ফোর্স: ", b_count2, "কয়েন ->", list(b_used2))
assert rem2 == 0
print("  গ্রিডি কি অপটিমাল?", g_count2 == b_count2)

৩ · এক্সচেঞ্জ আর্গুমেন্ট — গ্রিডি সঠিকতা প্রমাণের সাধারণ কৌশল

তাহলে প্রশ্ন হলো: কীভাবে বোঝা যাবে কোনো নির্দিষ্ট সমস্যায় গ্রিডি সঠিক কি না — অনুমান না করে, প্রমাণ করে? উত্তর হলো এক্সচেঞ্জ আর্গুমেন্টExchange Argumentধরে নাও একটি অপটিমাল সমাধান OPT আছে যা গ্রিডির থেকে ভিন্ন। দেখাও যে OPT-এর একটি চয়েসকে গ্রিডির চয়েস দিয়ে "বদলে" (exchange) দিলে সমাধানটি খারাপ হয় না। এভাবে ধাপে ধাপে OPT-কে গ্রিডির সমাধানে রূপান্তর করা যায়, প্রমাণ করে যে গ্রিডিও অপটিমাম। — একটি সাধারণ, পুনরায় ব্যবহারযোগ্য প্রমাণ টেমপ্লেট। ধাপে ধাপে যুক্তিটা এরকম:

1. ধরে নাও: OPT একটি অপটিমাল সমাধান, এবং OPT প্রথম যে ধাপে গ্রিডি থেকে ভিন্ন সিদ্ধান্ত নেয় সেটি হলো ধাপ $i$।
2. বদলাও (exchange): OPT-এর ধাপ $i$-এর চয়েসের জায়গায় গ্রিডির চয়েসটি বসিয়ে একটি নতুন সমাধান $\text{OPT}'$ তৈরি করো।
3. দেখাও কোনো ক্ষতি হয়নি: $\text{OPT}'$ এখনও বৈধ (feasible) এবং এর মান OPT-এর সমান অথবা ভালো — অর্থাৎ $\text{OPT}'$ ও একটি অপটিমাল সমাধান।
4. ইনডাকশন: এখন $\text{OPT}'$ ও গ্রিডি ধাপ $i$ পর্যন্ত একমত। একই যুক্তি বাকি ধাপগুলোর উপর প্রয়োগ করলে দেখা যায় গ্রিডির সম্পূর্ণ সমাধান নিজেই একটি অপটিমাল সমাধান।

লক্ষ করুন — এই যুক্তিটি এখনো বিমূর্ত (abstract); এটি কোনো নির্দিষ্ট সমস্যার কথা বলছে না। এর শক্তি ঠিক এখানেই: একবার এই টেমপ্লেট বুঝে গেলে, একই কাঠামো (ধাপ ১-৪) যেকোনো নির্দিষ্ট গ্রিডি সমস্যায় প্রয়োগ করা যায় — কেবল "ধাপ ৩"-এর প্রমাণটা প্রতিটি সমস্যার জন্য আলাদাভাবে করতে হয়। যেমন ধাপ ২-এর কাউন্টার-এক্সাম্পলে, এই এক্সচেঞ্জ আর্গুমেন্ট প্রয়োগ করলে ধাপ ৩-তেই আটকে যেত — কারণ OPT-এর ৩+৩ চয়েসকে গ্রিডির ৪-চয়েস দিয়ে বদলালে অবশিষ্ট সমস্যাটি (৬-৪=২, যা {1,3,4} দিয়ে ২টি কয়েনে তৈরি হয়, ১+১) OPT-এর চেয়ে খারাপ হয়ে যায় — এই ব্যর্থতাই বলে দেয় যে এই সমস্যায় (এই নির্দিষ্ট গ্রিডি নিয়মে) গ্রিডি-চয়েস প্রপার্টি সত্যি নয়।