নেটওয়ার্ক ফ্লো৯ মিনিট পড়া

হাঙ্গেরিয়ান অ্যালগরিদম (Hungarian Algorithm)

সর্বনিম্ন খরচে কর্মীদের কাজ বরাদ্দ করুন — নিখুঁত সমন্বয় বা পারফেক্ট ম্যাচ

time:\(O(n^3)\)space:\(O(n^2)\)problem:মিনিমাম-কস্ট পারফেক্ট বাইপার্টাইট ম্যাচিং (Bipartite Matching)

কল্পনা করুন আপনার সফটওয়্যার ফার্মে ৪ জন প্রোগ্রামার এবং ৪টি প্রজেক্ট আছে। প্রতিটি প্রজেক্টে একেকজন প্রোগ্রামারের কাজ করতে একেক রকম সময় লাগে (বা একেক রকম খরচ হয়)। আপনি চান এমনভাবে দায়িত্বগুলো ভাগ করতে যাতে সবার জন্য ঠিক একটি করে কাজ থাকে এবং সব মিলিয়ে মোট সময় বা খরচ সর্বনিম্ন হয়। এটিই হলো বিখ্যাত অ্যাসাইনমেন্ট প্রবলেম (Assignment problem)।

বাইপার্টাইট ম্যাচিং সাধারণত কাজের সর্বোচ্চ সংখ্যা খুঁজে বের করে। কিন্তু হাঙ্গেরিয়ান অ্যালগরিদম খুঁজে বের করে সবচেয়ে সস্তা বা দ্রুততম উপায়টি। এর সময় জটিলতা মাত্র \(O(n^3)\) — যা সবগুলো সম্ভাব্য বিন্যাস (n!) পরীক্ষা করার তুলনায় অবিশ্বাস্য দ্রুত।

মূল ধারণা: রো এবং কলাম রিডাকশন

এই অ্যালগরিদমের মূল ভিত্তি হলো একটি চমৎকার গাণিতিক সত্য: যদি আপনি কোনো একটি রো-এর (row) প্রতিটি এন্ট্রি থেকে একটি নির্দিষ্ট মান বিয়োগ করেন, তবে সব সম্ভাব্য কম্বিনেশনের মোট খরচও সেই একই পরিমাণে কমে যাবে। ফলে, সেরা এবং খারাপের আপেক্ষিক হায়ারার্কি বা ক্রম পরিবর্তন হয় না — যা আগে সেরা ছিল, সেটিই সেরা থেকে যায়।

কলামের ক্ষেত্রেও একই কথা প্রযোজ্য। তাই পদক্ষেপগুলো হলো:

প্রতিটি রো থেকে ওই রো-এর সর্বনিম্ন মান বিয়োগ করুন (এখন প্রতিটি লাইনে অন্তত একটি করে শূন্য থাকবে)।
একইভাবে প্রতিটি কলাম থেকেও ওই কলামের সর্বনিম্ন মান বিয়োগ করুন (এখন প্রতিটি কলামেও অন্তত একটি করে শূন্য থাকবে)।

এখন লক্ষ্য করুন তালিকায় থাকা শূন্যগুলোর ওপর ভিত্তি করে কাজ বরাদ্দ দেওয়া যায় কিনা। যদি আমরা এমন এক সেট শূন্য পাই যেখানে প্রতি রো এবং প্রতি কলামে একটি করে শূন্য থাকে, তবে সেটিই আমাদের সেরা সমাধান — কারণ রিডাকশনের পর এর খরচ ০, যার মানে মূল ম্যাট্রিক্সে এটিই ছিল সর্বনিম্ন।

যখন শূন্যগুলো দিয়ে সব কাভার করা যায় না

প্রাথমিক রিডাকশনের পরে হয়তো আপনি পর্যাপ্ত শূন্য পাবেন না যাতে সবাইকে কাজ দেওয়া যায়। তখন নতুন শূন্য তৈরি করতে হয়:

বড় বড় লাইন (রো বা কলাম) টেনে সব শূন্যগুলো ঢেকে দিন — দেখুন সর্বনিম্ন কয়টি লাইন (k) লাগছে।
যদি লাইনের সংখ্যা n-এর সমান হয়, তবে আমাদের কাছে সেরা সমাধান আছে — কাজ শেষ!
যদি k < n হয়, তবে যেসব জায়গায় কোনো লাইন পড়েনি তাদের মধ্যে সবচেয়ে ছোট মানটি খুঁজে বের করুন। এই মানটি খোলা জায়গাগুলো থেকে বিয়োগ করুন এবং যেখানে দুটি লাইন একে অপরকে ছেদ করেছে (intersection) সেখানে যোগ করুন। এতে অন্তত একটি নতুন শূন্য তৈরি হবে কিন্তু পুরনো শূন্যগুলো নষ্ট হবে না।
আবার প্রথম ধাপ থেকে ফিরে শুরু করুন।

অগমেন্টিং পাথ (Augmenting Path) এর দৃষ্টিভঙ্গি

ভেতরের দিকে ভাবলে, শূন্যগুলোর মধ্য দিয়ে নিখুঁত সমন্বয় খোঁজা আসলে বাইপার্টাইট ম্যাচিং সমস্যার অংশ। অ্যালগরিদমটি অগমেন্টিং পাথ ব্যবহার করে এগিয়ে যায়। যখন কোথাও আটকে যায়, তখন ম্যাট্রিক্স আপডেটের মাধ্যমে নতুন 'শূন্য-খরচের' পথ তৈরি করে কাজ সচল রাখা হয়। এটি সর্বোচ্চ n বার ধাপ অতিক্রম করার মধ্যেই শেষ হয়।

কেন এটি সঠিক: এলপি ডুয়ালিটি (LP Duality)

রো এবং কলাম থেকে বিয়োগ করা মানগুলো আসলে লিনিয়ার প্রোগ্রামিংয়ের ডুয়াল ভেরিয়েবল (dual variables) হিসেবে কাজ করে। অ্যালগরিদমটি সবসময় নিশ্চিত করে যাতে কোনো নেতিবাচক খরচ না তৈরি হয় (dual feasibility) এবং যখন সবশেষে একটি পারফেক্ট ম্যাচিং পাওয়া যায় (primal feasibility), তখন গাণিতিক 'স্ট্রং ডুয়ালিটি' থিওরেম অনুযায়ী এটিই হয় চূড়ান্ত সেরা উত্তর।

দ্রষ্টব্য: প্রতিটি বৈধ অ্যাসাইনমেন্টে প্রতি রো এবং প্রতি কলাম থেকে ঠিক একটি করে ঘর ব্যবহৃত হয়। তাই কোনো রো থেকে মান বিয়োগ করলে সেটি সব কম্বিনেশনের জন্য সমানভাবে কমে যায়। এই চমৎকার গাণিতিক বৈশিষ্ট্যের কারণেই রিডাকশন পদ্ধতি কাজ করে।

হাঙ্গেরিয়ান অ্যালগরিদম — কোড উদাহরণ

def hungarian(cost):
    """Returns assign[i] = job for worker i."""
    n = len(cost)
    INF = float('inf')
    u = [0] * (n+1)  # row potential
    v = [0] * (n+1)  # column potential
    p = [0] * (n+1)  # p[j] = worker matched to column j
    way = [0] * (n+1)

    for i in range(1, n+1):
        p[0] = i
        j0  = 0
        minv = [INF] * (n+1)
        used = [False] * (n+1)
        while True:
            used[j0] = True
            i0, delta, j1 = p[j0], INF, -1
            for j in range(1, n+1):
                if not used[j]:
                    cur = cost[i0-1][j-1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j]  = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1    = j
            for j in range(n+1):
                if used[j]:
                    u[p[j]] += delta
                    v[j]    -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0: break
        while j0:
            p[j0] = p[way[j0]]
            j0    = way[j0]

    ans = [0] * n
    for j in range(1, n+1):
        if p[j]: ans[p[j]-1] = j-1
    total = sum(cost[i][ans[i]] for i in range(n))
    return total, ans

# 4x4 cost matrix (e.g., in dollars or hours)
cost = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
]
total, assign = hungarian(cost)
print('Min cost:', total)
print('Assignment:', assign)