ডায়নামিক প্রোগ্রামিং৯ মিনিট পড়া

বিটমাস্ক ডিপি (Bitmask DP)

মাত্র একটি সিঙ্গেল পূর্ণসংখ্যায় বা ইনটিজারে সমস্ত সম্ভাব্য সাবসেটের পছন্দগুলো ট্র্যাক করুন
time:\(O(2^n \cdot n)\)space:\(O(2^n \cdot n)\)feasible n:≤ 20

ধরুন আপনার কাছে n টি সুইচ সহ একটি লাইট সুইচের প্যানেল আছে। প্রতিটি সুইচ হতে পারে অন (ON) অথবা অফ (OFF)। যেকোনো মুহূর্তে সমস্ত সুইচের অবস্থা — যেমন ধরুন ৩, ও ৪ নম্বর সুইচ দুটো অন — এই অন থাকা সুইচগুলো আপনি যে আইটেমগুলো বেছে নিয়েছেন মূলত তাদের একটি সাবসেট (subset) নির্দেশ করে।

এখন এখানে চতুর একটি কৌশল বা ট্রিক রয়েছে: আপনি কোন কোন সুইচগুলো অন রেখেছেন তার একটি তালিকা তৈরি না করে, আপনি বরং সরাসরি একটি বাইনারি সংখ্যাই লিখতে পারেন। সুইচ 0 অন = বিট 0 এর মান 1। সুইচ 3 অন = বিট 3 এর মান 1। যদি সব সুইচ অফ থাকে = তাহলে আপনার সংখ্যাটি হলো 0। আর সব সুইচ অন থাকলে = সংখ্যাটি হবে \(2^n\) − 1।

এই নির্দিষ্ট ইনটিজারটিকে বা পূর্ণসংখ্যাটিকে বিটমাস্ক (bitmask) বলা হয়, এবং সমস্ত সম্ভাব্য বিটমাস্কগুলোর ওপর ডাইনামিক প্রোগ্রামিং (DP বা dynamic programming) ব্যবহার করাকেই বিটমাস্ক ডিপি (Bitmask DP) বলা হয়।

এটি কীভাবে কাজে আসে?

কিছু সমস্যা এমন হতে পারে: "প্রতিটি আইটেম ঠিক একবার করেই ভিজিট করে, আইটেমগুলোতে নির্দিষ্ট স্লট বরাদ্দ করার সবচেয়ে সেরা উপায় বা পদ্ধতি কোনটি?" ব্রুট-ফোর্স (Brute force) পদ্ধতিতে এর প্রতিটি সম্ভাব্য ক্রমানুসারে বা অর্ডারে চেষ্টা করা হয় — যা হলো সব মিলিয়ে n! টি সম্ভাবনা, আর n এর মান 13 এর মতো ছোট হলেও এটি সব মিলিয়ে বিশাল বা বিস্ফোরিত একটি অবস্থা তৈরি করে। বিটমাস্ক ডিপি (Bitmask DP) প্রতিটি নির্দিষ্ট অবস্থান বা অর্ডারের পরিবর্তে কোন আইটেম বা জিনিসগুলো ইতোমধ্যে ব্যবহার করা হয়েছে তা ট্র্যাক করে, যা পুরো কাজটিকে n! অবস্থা থেকে প্রায় \(2^n\) × n এ নামিয়ে আনে — যা যদিও অনেক অনেক বড় বা সূচকীয় (exponential), কিন্তু n ≈ 20 হওয়া পর্যন্ত এটি বেশ সহজেই ব্যবহার এবং ম্যানেজ করা যায়।

মূল স্টেট বা কোর স্টেট (The Core State)

এর ডিপি (DP) স্টেটটি হলো dp[mask][i], এর অর্থ হলো: "আমি ইতিমধ্যে mask এ থাকা শহরগুলোতে (বা আইটেমগুলোতে) ঘুরে এসেছি, এবং আমি বর্তমানে i তম শহরে রয়েছি।" আপনার এর জন্য যে বিট ট্রিকস (bit tricks) গুলো প্রয়োজন তা হলো:

  • j তম শহরটি মাস্কে (mask) আছে কি না তা যাচাই করুন: (mask >> j) & 1
  • j তম শহরটিকে মাস্কে (mask) যোগ করুন: mask | (1 << j)
  • j তম শহরটিকে মাস্ক (mask) থেকে সরিয়ে ফেলুন: mask & ~(1 << j)
  • মাস্কটি কি সম্পূর্ণরূপে ভিজিট করা হয়েছে? mask == (1 << n) - 1

ট্র্যাভেলিং সেলসপারসন সমস্যা (Travelling Salesperson Problem - TSP)

সবচেয়ে বিখ্যাত এবং বহুল ব্যবহৃত বিটমাস্ক ডিপি (Bitmask DP) প্রয়োগ: কিছু n সংখ্যক শহর এবং তাদের প্রত্যেক জোড়ার মধ্যে ভ্রমণের খরচ দেওয়া থাকে, তখন সবচেয়ে সস্তা বা কম খরচে প্রতিটি শহরে ঠিক একবার করে ভ্রমণ করে আবার বাড়ি ফিরে আসার উপায়টি খুঁজে বের করতে হয়।

বেস কেস বা শর্ত: dp[1][0] = 0 — অর্থাৎ আমরা 0 নম্বর শহর থেকে শুরু করি, যেখানে শুধুমাত্র 0 নম্বর শহরটিই ভিজিট বা পরিদর্শন করা হয়েছে (0 তম বিটের মান 1), আর এতে কোনো খরচ বা কস্ট হয়নি।

ট্রানজিশন (Transition): প্রতিটি ভিজিট না করা (unvisited) বা বাকি থাকা শহর j এর জন্য, বর্তমান রুটটিকে বা ট্যুরটিকে আরেকটু বড় করার চেষ্টা করুন: dp[mask | (1<<j)][j] = min(dp[mask][i] + cost[i][j])।

উত্তর বা ফলাফল (Answer): সব শহর ঘুরে আবার বাড়ি ফিরে আসার সবচেয়ে সস্তা বা কম খরচের পথটি হলো: min over all i of (dp[full_mask][i] + cost[i][0])।

দ্রষ্টব্য: বিটমাস্ক হলো খুবই সহজ ভাষায় এবং ছোট করে "এখানে সেই আইটেমগুলোর নির্দিষ্ট সেট রয়েছে যা আমি এ পর্যন্ত ব্যবহার করেছি" এই কথাটি বলার একটি উপায়। এর প্রতিটি বিট হলো একটি হ্যাঁ/না সুইচ মাত্র। যদি দুটি স্টেটের বিটমাস্ক একই হয় তবে তাদের মধ্যে কোনো পার্থক্য করা সম্ভব নয় — আর মূলত সে কারণেই এটি ব্যবহার করা হয়।

বিটমাস্ক ডিপি দিয়ে ট্র্যাভেলিং সেলসপারসন সমস্যা বা TSP (TSP with Bitmask DP)

import math


def tsp(cost):
    n = len(cost)
    INF = math.inf
    full = (1 << n) - 1
    # dp[mask][i] = min cost to visit cities in mask, ending at i
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0


    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == INF:
                continue
            if not (mask >> i) & 1:
                continue
            for j in range(n):
                if (mask >> j) & 1:
                    continue  # already visited
                new_mask = mask | (1 << j)
                dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + cost[i][j])


    return min(dp[full][i] + cost[i][0] for i in range(n))


# 4 cities, symmetric costs
cost = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(tsp(cost))  # 80
Output
80

অ্যাসাইনমেন্ট সমস্যা (Assignment Problem)

মোট খরচ বা কস্টগুলোকে যতটা সম্ভব কমিয়ে n জন কর্মীকে n টি কাজে নিযুক্ত বা অ্যাসাইন করুন। এর স্টেট (state) অপেক্ষাকৃত সহজ: dp[mask] = mask এর কাজগুলো সম্পন্ন করতে সর্বনিম্ন খরচ, যেখানে আমরা ক্রমানুসারে একটির পর একটি কাজ কোনো নির্দিষ্ট কর্মীকে দিয়ে থাকি।

যদি mask এ মোট k টি বিট সেট করা থাকে, তবে আমরা k তম কর্মীকে (0-indexed) নিযুক্ত করছি। mask এ আগে থেকেই থাকা প্রতিটি কাজ j এর ক্ষেত্রে, আমরা হয়তো তাকে সর্বশেষ নিযুক্ত করতে পারতাম: dp[mask] = min(dp[mask ^ (1<<j)] + cost[k-1][j])।

সাবসেটের ওপর ইটারেট করা বা লুপ চালানো (Iterating Over Subsets)

এটি একটি অসাধারণ এবং অত্যন্ত শক্তিশালী প্যাটার্ন: একটি নির্দিষ্ট বা প্রদত্ত মাস্কের (mask) সমস্ত সাবসেটের ওপর ইটারেট (iterate) করা বা ঘুরে আসা। for (sub = mask; sub > 0; sub = (sub-1) & mask) এই লুপটি mask এর প্রতিটি নন-এমপ্টি (non-empty) সাবসেটের মধ্যে ঠিক একবারই ঘুরে আসে। এর কৌশলটি হলো: (sub-1) & mask অপারেশনটি mask এর ভেতরে সবচেয়ে ছোট বা পজিশনে নিচে থাকা সেট বিটটিকে ক্লিয়ার করে বা সরিয়ে দিয়ে, ঠিক \(O(2^{\text{popcount}(mask)})\) সময়ে সমস্ত সাবসেটের মধ্য দিয়ে এগিয়ে যায়। সমস্ত মাস্কগুলোকে একত্রিত করলে সব মিলিয়ে \(3^n\) টি ধাপ বা স্টেপ তৈরি হয়।

Complexity

🐌 ব্রুট-ফোর্স টিএসপি (Brute-force TSP)
n > 12 হলে এটি অবাস্তব বা অসম্ভব হয়ে পড়ে — কারণ 13! মানেই প্রায় 6 বিলিয়নের সমান
সব ধরনের অর্ডারিং (All orderings) \(O(n!)\)
⚡ বিটমাস্ক ডিপি বা Bitmask DP (সময় বা time)
\(2^n\) মাস্ক × n বর্তমান শহরগুলো × n ট্রানজিশন (transitions); n=20 হলে ~৪০০ মিলিয়ন (400M) বার কাজ করতে হয় বা অপারেশনস হয়
এক্সপোনেনশিয়াল (Exponential) বা সূচকীয় হলেও ব্যবহারযোগ্য \(O(2^n \cdot n^2)\)
💾 বিটমাস্ক ডিপি বা Bitmask DP (স্পেস বা space)
৩২-বিট ইনটিজারের (32-bit integers) সাহায্যে n=20 এর জন্য ~২০ মেগাবাইট বা 20 MB প্রয়োজন — তাই আপনার মেমরির সীমার দিকে নজর রাখুন
এক্সপোনেনশিয়াল টেবিল (Exponential table) \(O(2^n \cdot n)\)
🔁 সাবসেট অ্যানুমেরেশন বা বের করা (Subset enumeration)
প্রতিটি আইটেমের বা উপাদানের তিনটি অবস্থা থাকে: হয় এটি মাস্কে নেই, অথবা মাস্কে আছে কিন্তু সাবসেটে নেই, অথবা দুটিতেই আছে
সমস্ত মাস্কের যোগফল \(O(3^n)\)
📏 ব্যবহারিক ব্যবহারের সীমানা বা প্র্যাকটিক্যাল লিমিট (Practical limit)
\(2^{20}\) × 20 ≈ 20 মিলিয়ন স্টেট (20 million states) — এটি কয়েক সেকেন্ডের মধ্যেই ফিজিবল বা সম্ভব
কঠিন এবং নির্দিষ্ট সীমা (Hard ceiling) n ≤ 20

ছোট কুইজ

টিএসপি (TSP) বিটমাস্ক ডিপিতে (Bitmask DP), dp[mask][i] কী সংরক্ষণ বা স্টোর (store) করে?

পড়া চালিয়ে যান

ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→
0/1 ন্যাপস্যাক (0/1 Knapsack)
সর্বোচ্চ মূল্যের (value) জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করুন — যেখানে প্রতিটি জিনিস বা আইটেম হয় পুরোপুরি নিতে হবে নতুবা একদমই নেওয়া যাবে না (all-or-nothing)
→
হ্যামিল্টোনীয় পথ (Hamiltonian Path)
প্রতিটি ঘর ঠিক একবার করে ভ্রমণ করুন — এটি প্রতিটি সেতু ভ্রমণের চেয়ে অনেক বেশি কঠিন
→