অ্যাডভান্সড টপিক৮ মিনিট পড়া

ব্রাঞ্চ অ্যান্ড বাউন্ড (Branch & Bound)

ভবিষ্যত দেখার ক্ষমতাসহ ব্যাকট্র্যাকিং (Backtracking) — যে শাখাগুলো বা ব্রাঞ্চ কোনোভাবেই জিততে পারবে না, সেগুলোকে কেটে ছেঁটে ফেলুন (prune)
best case:পলিনোমিয়াল (Polynomial) (আঁটোসাঁটো বা টাইট বাউন্ডগুলো খুব দৃঢ়ভাবে বা শক্তভাবে প্রুন (prune) করে বলে)worst case:এক্সপোনেনশিয়াল বা সূচকীয় (Exponential) (যখন বাউন্ডগুলো একেবারেই কোনো কাজে আসে না বা সাহায্য করে না)goal:NP-hard সমস্যার জন্য একদম নিখুঁত এবং সর্বোত্তম (optimal) সমাধান বের করা

ধরুন আপনি লেওভার (layover) বা যাত্রাবিরতি আছে এমন সবচেয়ে সস্তা বা কম খরচের একটি ফ্লাইটের খোঁজ করছেন। আপনি বিমানবন্দরে দাঁড়িয়ে রুট A (ঢাকা → চট্টগ্রাম → সিলেট) এবং রুট B (ঢাকা → রাজশাহী → সিলেট) এর কথা ভাবছেন বা বিবেচনা করছেন। চট্টগ্রামের টিকিট বা লেগ বুক করার আগেই, আপনি যাচাই করে দেখতে চাইলেন: "বাকি রুটের পরম ন্যূনতম বা সবচেয়ে কম খরচ (absolute minimum) কত হতে পারে?" যদি রুট A-এর সেরা অবস্থা বা বেস্ট-কেস (best-case) সম্পন্ন করতে আপনি যে রুট B-কে ইতিমধ্যে খুঁজে পেয়েছেন তার চেয়েও বেশি খরচ হয় — তবে রুট A-কে পুরোপুরি স্কিপ বা বাতিল করে দিন।

এটাই হলো ব্রাঞ্চ অ্যান্ড বাউন্ড (Branch and Bound): যা মূলত বাউন্ডিং ফাংশন (bounding function) দ্বারা আপগ্রেড বা উন্নত করা একটি ব্যাকট্র্যাকিং পদ্ধতি, যা আংশিক বা হাফ উপায়ের (partial solution) সম্ভাব্য সর্বোত্তম বা বেস্ট ফলাফল নিয়ে অনুমান করে। যদি সম্ভাব্য সেই সবচেয়ে ভালো ফলাফলটি আপনার ইতিমধ্যে খুঁজে পাওয়া সেরা ফলাফলের চেয়ে ভালো না হতে পারে, তবে সেই পুরো শাখাটিকে বা ব্রাঞ্চটিকেই প্রুন (prune) করে দিন বা ছেঁটে ফেলুন — অর্থাৎ সেখানে যাওয়ার কিংবা খোঁজার কোনো প্রশ্নই আসে না।

এর নামের দুটি অংশ বা ভাগ

ব্রাঞ্চ (Branch) বা শাখা — সমস্যাটিকে বিভিন্ন ছোট ছোট উপ-নির্বাচনে বা সাব-চয়েসে (sub-choices) ভাগ করে, ঠিক যেমনটি ব্যাকট্র্যাকিং (backtracking) একটি ডিসিশন ট্রি (decision tree) বা সিদ্ধান্তের গাছ তৈরি করে।

বাউন্ড (Bound) বা সীমা — প্রতিটি আংশিক বা হাফ উপায়ের (partial solution) জন্য একটি সীমা বা বাউন্ড গণনা করুন বা বের করুন: এটি সম্পন্ন করার পরে সম্ভাব্য সর্বোত্তম অবজেক্টিভ ভ্যালু (objective value) বা লক্ষ্যের মান। মিনিমাইজেশন (minimization) বা কমানোর ক্ষেত্রে এটি হলো লোয়ার বাউন্ড (lower bound) বা নিম্নসীমা। আর ম্যাক্সিমাইজেশন (maximization) বা বাড়ানোর ক্ষেত্রে এটি হলো আপার বাউন্ড (upper bound) বা উচ্চসীমা।

মিনিমাইজেশন (minimization)-এর বা কমানোর ক্ষেত্রে প্রুনিংয়ের বা বাতিলের নিয়মটি হলো: যদি lower_bound(node) ≥ best_complete_solution_so_far হয়, তবে প্রুন বা বাতিল করুন — এই সাবট্রির (subtree) বা ছোট গাছের কোনো কিছুই বর্তমান সেরাকে আর উন্নত বা অতিক্রম করতে পারবে না।

ট্রাভার্সাল স্ট্র্যাটেজি (Traversal strategies)

আপনি কোন ক্রমে বা অর্ডারে নোডগুলোকে সম্প্রসারিত বা বড় (expand) করছেন, তার উপর অনেকটাই নির্ভর করে যে আপনি কত দ্রুত বাউন্ডটিকে টাইট বা সঠিক করার জন্য একটি ভালো সমাধান বা উপায় খুঁজে পাবেন:

ডেপথ-ফার্স্ট বা গভীর-খোঁজ (Depth-first - stack): এটি খুব দ্রুত সম্পূর্ণ বা পরিপূর্ণ সমাধান খুঁজবে, এবং প্রথম দিকেই বাউন্ড বা সীমাকে টাইট করে আনবে। এটি মেমরি-সাশ্রয়ী বা মেমরি-এফিশিয়েন্ট (Memory-efficient)। তবে এটি হয়তো ভালো ব্রাঞ্চ বা শাখাগুলোর আগে খারাপ ব্রাঞ্চগুলোতে খুঁজতে শুরু করতে পারে।

বেস্ট-ফার্স্ট বা সেরা-খোঁজ (Best-first - priority queue): এটি সবসময় সেরা (সর্বনিম্ন) বাউন্ড বা সীমা থাকা নোডটিকেই বা নির্দিষ্ট অংশটিকেই প্রসারিত করে — এর সাহায্যে সবচেয়ে কম নোড বা অংশ এক্সপ্লোর বা ঘুরে যাচাই করে সবচেয়ে অপ্টিমাল (optimal) বা ভালো রেজাল্ট পাওয়ার গ্যারান্টি বা নিশ্চয়তা পাওয়া যায়। এর একটি নেতিবাচক দিক হলো (Downside): এর জন্য এক্সপোনেনশিয়াল বা সূচকীয় মেমরির প্রয়োজন হতে পারে।

বাস্তব ক্ষেত্রে, একটি ভালো বাউন্ডিং ফাংশনের সাথে বেস্ট-ফার্স্ট পদ্ধতি অন্যান্য যেকোনো বিকল্পের চেয়ে অনেকগুণ বেশি দ্রুত কাজ করে।

0/1 ন্যাপস্যাক বা 0/1 Knapsack — কাজের উদাহরণ বা ওয়ার্কড এক্সাম্পল

প্রতিটি আইটেমের বা উপাদানের উপর ব্রাঞ্চ করুন বা শাখা তৈরি করুন: একে অন্তর্ভুক্ত (include) করুন অথবা স্কিপ বা বাতিল (skip) করুন। আংশিক সমাধানের বা হাফ উপায়ের ক্ষেত্রে আপার বাউন্ড (upper bound) বা উচ্চসীমা হলো: এখন পর্যন্ত অর্জিত বা জমা হওয়া মান বা ভ্যালুটিকে (value) নিন, তারপর বাকি অংশের ফ্র্যাকশনাল (fractional) ন্যাপস্যাক সমাধান বা ভগ্নাংশের সমাধান দিয়ে অবশিষ্ট বা বাকি থাকা ক্যাপাসিটি বা ধারণক্ষমতাকে গ্রিডিলি (greedily) বা লোভীর মতো পূরণ করুন (আইটেম বা উপাদানগুলোকে ভাঙার বা টুকরো করার অনুমতি দিন)। যেহেতু ফ্র্যাকশনাল বা ভগ্নাংশের দ্বারা পূরণ করা সর্বদা 0/1 দ্বারা পূরণ করার চেয়ে সমান বা তার চেয়ে ভালো, তাই এটি একটি ভ্যালিড বা সঠিক আপার বাউন্ড (upper bound) বা উচ্চসীমা। যদি এই আপার বাউন্ড ইতিমধ্যে পাওয়া সেরা সম্পূর্ণ বা পরিপূর্ণ সমাধানের নিচে থাকে, তবে তাকে প্রুন (prune) বা বাতিল করুন।

আইটেম বা উপাদানগুলোকে যখন তাদের মান-প্রতি-ওজন (value-per-weight) অনুপাত (ratio) অনুসারে সাজানো বা সর্ট করা থাকে, তখন ফ্র্যাকশনাল বাউন্ডটি বা ভগ্নাংশ সীমাটি বেশ আঁটোসাঁটো বা টাইট হয়, এবং খুব দৃঢ়ভাবে বা শক্তভাবে প্রুনিং (pruning) করা অত্যন্ত সহজ হয়ে যায়।

ট্র্যাভেলিং সেলসপারসন সমস্যা (Traveling Salesman Problem)

এটি ট্র্যাভেলিং সেলসপারসন সমস্যা বা টিএসপি (TSP) সফরের আংশিক বা হাফ উপায়ের জন্য ব্যবহৃত একটি লোয়ার বাউন্ড (lower bound) বা নিম্নসীমা: (এখন পর্যন্ত বাছাই করা বা বেছে নেওয়া এজগুলোর (edges) বা সংযোগগুলোর খরচ) + (পরিদর্শন বা ভিজিট না করা শহরগুলোর মিনিমাম স্প্যানিং ট্রি (minimum spanning tree))। এটি বাকি থাকা বা অবশিষ্ট খরচের একটি আন্ডার-এস্টিমেট দেয় বা কম অনুমান করে — যা একটি ভ্যালিড বা সঠিক লোয়ার বাউন্ড বা নিম্নসীমা। যখন এই লোয়ার বাউন্ড বর্তমানে পাওয়া সেরা সম্পূর্ণ বা ফুল টিএসপি সফরের খরচকে ছাড়িয়ে যায়, তখন তাকে প্রুন (prune) বা বাতিল করুন। টাইট বাউন্ড বা শক্ত সীমার সাহায্যে, ব্রাঞ্চ অ্যান্ড বাউন্ড (Branch and Bound) শত শত শহর বিশিষ্ট টিএসপি সমস্যারও একদম নিখুঁত সমাধান দিতে পারে — যদিও সবচেয়ে খারাপ পরিস্থিতিতে বা ওয়ার্স্ট-কেসে এটি এক্সপোনেনশিয়াল বা সূচকীয়ই থেকে যায়।

কখন ব্রাঞ্চ অ্যান্ড বাউন্ড বা Branch and Bound ব্যবহার করবেন

এটি তখনই ব্যবহার করুন যখন আপনার একটি প্রমাণযোগ্য সর্বোত্তম বা প্রুভেবলি অপ্টিমাল (provably optimal) উত্তরের প্রয়োজন হয় এবং সমস্যার আকারটি যথেষ্ট ছোট হয়। এর থেকে বড় আকারের সমস্যার ক্ষেত্রে: অ্যাপ্রক্সিমেশন (approximation) অ্যালগরিদমগুলো পলিনোমিয়াল-টাইমে বা কম সময়ে অপ্টিমাল উত্তরের একটি গ্যারান্টি বা নিশ্চয়তাযুক্ত অনুপাতের (ratio) মধ্যে ফলাফল প্রদান করে; সমস্যার মধ্যে উপযুক্ত আনুষঙ্গিক কাঠামো বা সাবস্ট্রাকচার (substructure) থাকলে তখন ডাইনামিক প্রোগ্রামিং (dynamic programming) বেশ ভালো কাজ করে; আর কোনো গ্যারান্টি বা নিশ্চয়তা ছাড়াই দ্রুত কাজ করার জন্য হিউরিস্টিকস (heuristics) ব্যবহার করা যায়। এখানে বাউন্ডিং ফাংশনের (bounding function) মান বা কোয়ালিটিই (quality) হলো সবকিছু — দুর্বল বাউন্ড বা সীমার অর্থ হলো প্রায় সব উপায়ে অনুসন্ধান বা এক্সহস্টিভ সার্চ (exhaustive search) করা; আর টাইট বা শক্ত বাউন্ড অবাক করে দেওয়ার মতো বিশাল আকারের সমস্যাকেও অতি সহজে বাগে বা নিয়ন্ত্রণে নিয়ে আসতে সক্ষম।

দ্রষ্টব্য: বাউন্ডিং ফাংশন (bounding function) হলো মূলত ব্রাঞ্চ অ্যান্ড বাউন্ডের প্রাণ। এমন একটি বাউন্ড বা সীমা যা সর্বদা এবং ঠিক নিখুঁতভাবে অপ্টিমাল বা সর্বোত্তম হয় তা আপনাকে কাজের বা কার্যকরী কোনো কিছুই জানাতে পারে না। আর এমন একটি বাউন্ড যা খুব দ্রুত গণনা বা হিসাব করতে সক্ষম এবং প্রকৃত বা আসল অপ্টিমাল বা সর্বোত্তম ফলাফলের খুব কাছাকাছি থাকে—তা এই পুরো ট্রির (tree) বা গাছের ৯৯% শাখাকেই প্রুন বা বাতিল করতে পারে। তাই সর্বদা আপনার বাউন্ডের বা সীমার পেছনে বেশ ভালো পরিমাণ সময় বা এনার্জি বিনিয়োগ করুন বা ইনভেস্ট করুন।

ব্রাঞ্চ অ্যান্ড বাউন্ডের সাহায্যে ০/১ ন্যাপস্যাক বা 0/1 Knapsack via Branch & Bound

import heapq


def knapsack_bb(weights, values, capacity):
    n = len(weights)
    # Sort by value/weight ratio descending
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)


    def upper_bound(idx, remaining_cap, current_val):
        """Fractional knapsack upper bound from item idx onward."""
        val = current_val
        for i in range(idx, n):
            v, w = items[i]
            if w <= remaining_cap:
                val += v; remaining_cap -= w
            else:
                val += v * (remaining_cap / w)
                break
        return val


    best = 0
    # Heap entries: (-upper_bound, idx, remaining_cap, current_val)
    heap = [(-upper_bound(0, capacity, 0), 0, capacity, 0)]


    while heap:
        neg_ub, idx, rem, cur = heapq.heappop(heap)
        if -neg_ub <= best or idx == n:
            continue
        v, w = items[idx]
        # Branch: include item
        if w <= rem:
            new_val = cur + v
            best = max(best, new_val)
            ub = upper_bound(idx+1, rem-w, new_val)
            if ub > best:
                heapq.heappush(heap, (-ub, idx+1, rem-w, new_val))
        # Branch: skip item
        ub = upper_bound(idx+1, rem, cur)
        if ub > best:
            heapq.heappush(heap, (-ub, idx+1, rem, cur))


    return best


weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_bb(weights, values, 8))  # 10
Output
10

Complexity

🎯 বেস্ট কেস বা সেরা পরিস্থিতি (টাইট বা শক্ত বাউন্ডের ক্ষেত্রে)
যে বাউন্ড বা সীমাগুলো প্রকৃত অপ্টিমাল বা সর্বোত্তম মানের একদম কাছাকাছি থাকে, তার সাহায্যে শুধুমাত্র পলিনোমিয়াল (polynomial) সংখ্যক নোডগুলোকে পরিদর্শন বা ভিজিট করা হতে পারে
অর্ধেকেরও বেশি ব্রাঞ্চ বা শাখাকে তাৎক্ষণিকভাবেই প্রুন বা বাতিল করা যায় \(O(n^c)\) সম্ভব
💥 ওয়ার্স্ট কেস বা সবচেয়ে খারাপ পরিস্থিতি (লুস বা আলগা বাউন্ডের ক্ষেত্রে)
যদি বাউন্ডগুলো কখনোই কিছু প্রুন না করে বা না ছাঁটে, তবে ব্রাঞ্চ অ্যান্ড বাউন্ড মূলত অতিরিক্ত ওভারহেডসহ বা অতিরিক্ত কাজের বোঝাসহ একটি ব্যাকট্র্যাকিং-এ (backtracking) পরিণত হয়
এক্সহস্টিভ সার্চের (exhaustive search) মাধ্যমে সময় আরও খারাপ হয়ে যায় \(O(2^n)\) অথবা \(O(n!)\)
📊 বেস্ট-ফার্স্ট ট্রাভার্সাল (Best-first traversal)
N = পরিদর্শন বা ঘুরে দেখা নোডগুলোর সংখ্যা; এটি সবচেয়ে কম সংখ্যক নোডগুলোর সাহায্যে সর্বোত্তম সমাধানের খোঁজ পেতে গ্যারান্টি বা নিশ্চয়তা দেয় তবে কিউ-এর (queue) জন্য \(O(N)\) মেমরিরও প্রয়োজন হয়
প্রতিটি নোডের জন্য প্রায়োরিটি কিউ (Priority queue) প্রতি নোডে \(O(\log N)\)
📐 ফ্র্যাকশনাল বা ভগ্নাংশের ন্যাপস্যাক বাউন্ড (Fractional knapsack bound)
প্রথমে \(O(n \log n)\) সর্ট করার পরে; এটি সব টাইট বা শক্ত বাউন্ডগুলো তৈরি করে যা খুব কঠোরভাবে প্রুন (prune) বা বাতিল করতে সাহায্য করে
বাকি আইটেম বা জিনিসগুলোকে গ্রিডিলি বা লোভীর মতো পূরণ করে (Greedy fill) প্রতি নোডে \(O(n)\)

ছোট কুইজ

ব্রাঞ্চ অ্যান্ড বাউন্ড সাধারণ বা প্লেইন ব্যাকট্র্যাকিংয়ের উপরে বা সাথে মূলত আর কী কী জিনিস যোগ করে?

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