কেস স্টাডি — সঠিক অ্যালগরিদমিক প্যারাডাইম বেছে নেওয়া

১ · সমস্যা — একটি ডেলিভারি ট্রাকের দৈনিক শিডিউল

ধরা যাক একটি ছোট কুরিয়ার কোম্পানির একটি ট্রাক আছে এবং আজকের জন্য কয়েকটি প্রার্থী ডেলিভারি জব পাওয়া গেছে। প্রতিটি জবের একটি নির্দিষ্ট সময়-উইন্ডো (শুরু ও শেষ সময়) এবং একটি লাভ (profit) আছে — কিছু জব দূরের বা জরুরি ক্লায়েন্টের হওয়ায় বেশি লাভজনক, কিছু কম। ট্রাক একসাথে শুধু একটি জব করতে পারে, এবং দুটি জব একে অপরের সময়ে ওভারল্যাপ করলে দুটোই নেওয়া যায় না। লক্ষ্য: সামগ্রিক লাভ সর্বোচ্চ করা এমন একটি সেট জব বেছে নেওয়া।

এই সমস্যাটি দেখতে পুরোপুরি M5/L20-এর অ্যাক্টিভিটি সিলেকশন প্রবলেমের মতোই — কিন্তু একটি গুরুত্বপূর্ণ পার্থক্য আছে: L20-এ লক্ষ্য ছিল সংখ্যায় সর্বোচ্চ অ্যাক্টিভিটি বাছাই করা (সব অ্যাক্টিভিটির "মূল্য" সমান ধরে নেওয়া হয়েছিল), কিন্তু এখানে প্রতিটি জবের ভিন্ন ভিন্ন লাভ আছে। এই একটি পার্থক্যই পুরো সিদ্ধান্ত-প্রক্রিয়া বদলে দেয় — এটাই এই কেস স্টাডির মূল শিক্ষা।

২ · ধাপ ১ — দ্রুত গ্রিডি হিউরিস্টিক (এবং কেন এটি এখানে বিপজ্জনক)

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

কিন্তু L20-এর প্রমাণটি নির্দিষ্টভাবে সংখ্যা সর্বোচ্চ করার জন্য, লাভ সর্বোচ্চ করার জন্য নয়। যখন জবগুলোর লাভ ভিন্ন ভিন্ন হয়, তখন এক্সচেঞ্জ আর্গুমেন্টের প্রমাণ আর প্রযোজ্য থাকে না — এবং M6/L56-এ (পরের পাঠে বিস্তারিত) আমরা দেখব "গ্রিডি অতীতে কাজ করেছিল" এটা প্রমাণ নয়। নিচের কোডে ঠিক এটাই ঘটতে দেখা যাবে।

৩ · ধাপ ২ — এক্স্যাক্ট সমাধান: ওয়েটেড ইন্টারভাল শিডিউলিং DP

যেহেতু একটি ট্রাকের জন্য প্রার্থী জবের সংখ্যা স্বাভাবিকভাবেই ছোট (একটি শিফটে হাতে গোনা কয়েকটি সম্ভাব্য জব), তাই M6-এর optimal substructure যুক্তি প্রয়োগ করা যায়: ফিনিশ-টাইম অনুযায়ী সাজানো জবগুলোর মধ্যে $i$-তম জব পর্যন্ত সর্বোচ্চ লাভ হয় হয় (ক) $i$-তম জব বাদ দিয়ে প্রথম $i-1$টির সর্বোচ্চ লাভ, অথবা (খ) $i$-তম জব নিয়ে তার সাথে সামঞ্জস্যপূর্ণ সর্বশেষ জব $p(i)$ পর্যন্ত সর্বোচ্চ লাভ যোগ করে:

এখানে $p(i)$ হলো ফিনিশ-টাইম অনুযায়ী সাজানো তালিকায় $i$-তম জবের সাথে সময়ে সামঞ্জস্যপূর্ণ (ওভারল্যাপ করে না) এমন সর্বশেষ জবের ইনডেক্স। এই রিকারেন্সেই ওভারল্যাপিং সাব-প্রবলেম দেখা যায় — $p(i)$ বিভিন্ন $i$-এর জন্য একই সাব-প্রবলেমে ফিরে আসতে পারে — তাই এটি একটি আসল DP, প্লেইন রিকার্সন নয়। এই সমাধান $O(n \log n)$ সময়ে চলে (সাজানো + প্রতিটি জবের জন্য বাইনারি সার্চে $p(i)$ বের করা) — নিচের কোডে ব্রুট-ফোর্সের বিপরীতে যাচাই করা হয়েছে।

import bisect
from itertools import combinations

# একটি ডেলিভারি ট্রাকের প্রার্থী জব: (শুরু, শেষ, লাভ)
jobs = [
    (1, 4, 5), (3, 5, 6), (0, 6, 10), (5, 7, 4),
    (6, 9, 5), (8, 10, 3), (2, 8, 100),
]

def compatible(a, b):
    return a[1] <= b[0] or b[1] <= a[0]

def brute_force_optimal(jobs):
    n = len(jobs)
    best = 0
    for r in range(n + 1):
        for combo in combinations(range(n), r):
            ok = all(compatible(jobs[i], jobs[j])
                     for x, i in enumerate(combo) for j in combo[x + 1:])
            if ok:
                best = max(best, sum(jobs[i][2] for i in combo))
    return best

def greedy_earliest_finish(jobs):
    # M5/L20-এর নিয়ম: সবচেয়ে আগে শেষ হওয়া, সামঞ্জস্যপূর্ণ জব বেছে নেওয়া
    order = sorted(range(len(jobs)), key=lambda i: jobs[i][1])
    chosen, last_finish = [], -1
    for i in order:
        s, f, p = jobs[i]
        if s >= last_finish:
            chosen.append(i)
            last_finish = f
    return sum(jobs[i][2] for i in chosen), chosen

def weighted_interval_dp(jobs):
    n = len(jobs)
    order = sorted(range(n), key=lambda i: jobs[i][1])
    sj = [jobs[i] for i in order]
    finishes = [f for _, f, _ in sj]
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        s, f, profit = sj[i - 1]
        p_idx = bisect.bisect_right(finishes, s, 0, i - 1)
        dp[i] = max(dp[i - 1], profit + dp[p_idx])
    return dp[n]

opt_bf = brute_force_optimal(jobs)
opt_dp = weighted_interval_dp(jobs)
g_profit, g_chosen = greedy_earliest_finish(jobs)

print("জব তালিকা (শুরু, শেষ, লাভ):", jobs)
print(f"ব্রুট-ফোর্স সর্বোচ্চ লাভ      : {opt_bf}")
print(f"DP (weighted interval) লাভ  : {opt_dp}   (ব্রুট-ফোর্সের সাথে মিলল: {opt_dp == opt_bf})")
print(f"গ্রিডি (earliest-finish) লাভ : {g_profit}   বাছাই করা জব index: {g_chosen}")
print(f"\nফাঁক (gap) = {opt_bf - g_profit}  --  গ্রিডি অপটিমালের মাত্র {100 * g_profit / opt_bf:.1f}% অর্জন করেছে")

৪ · ধাপ ৩ — স্কেল বড় হলে কী বদলায়

উপরের সমস্যায় DP পুরোপুরি ব্যবহারযোগ্য ছিল কারণ একটি ট্রাকের জব-সংখ্যা ছোট এবং সাব-প্রবলেম গঠন সরল। কিন্তু কোম্পানিটি বড় হয়ে বহু ট্রাক ও শত শত সম্ভাব্য জব নিয়ে কাজ করতে শুরু করলে সমস্যাটি রূপান্তরিত হয় ভেহিকল-রাউটিং-সদৃশ একটি সমস্যায় — যেখানে কোন ট্রাক কোন জব নেবে এবং কোন ক্রমে যাবে তা একসাথে সিদ্ধান্ত নিতে হয়। এই সাধারণ রূপটি TSP ও সেট-কভার-ধর্মী সমস্যার সাথে গঠনগতভাবে সম্পর্কিত এবং ব্যবহারিকভাবে NP-hard (M11/L48-এর "NP-hard সমস্যা চেনা" চেকলিস্ট দিয়ে যাচাইযোগ্য)।

NP-hardness-এর মুখোমুখি হলে M11/L49-এর সিদ্ধান্ত-ফ্রেমওয়ার্ক অনুযায়ী দুটো পথ থাকে: