অ্যাসাইনমেন্ট সমস্যা সমাধানের জন্য হাঙ্গেরিয়ান অ্যালগরিদম#

অ্যাসাইনমেন্ট সমস্যার বিবৃতি#

অ্যাসাইনমেন্ট সমস্যার বেশ কয়েকটি আদর্শ রূপ আছে (যেগুলো মূলত সমতুল্য)। এখানে কয়েকটি দেওয়া হলো:

$n$ টি কাজ এবং $n$ জন কর্মী আছে। প্রতিটি কর্মী একটি নির্দিষ্ট কাজের জন্য যে পরিমাণ অর্থ আশা করে তা উল্লেখ করে। প্রতিটি কর্মীকে শুধুমাত্র একটি কাজে নিয়োগ করা যায়। লক্ষ্য হলো কর্মীদের এমনভাবে কাজে নিয়োগ করা যাতে মোট খরচ সর্বনিম্ন হয়।
একটি $n \times n$ ম্যাট্রিক্স $A$ দেওয়া আছে, প্রতিটি সারি থেকে একটি সংখ্যা নির্বাচন করতে হবে যাতে প্রতিটি কলাম থেকে ঠিক একটি সংখ্যা নির্বাচিত হয়, এবং নির্বাচিত সংখ্যাগুলোর যোগফল সর্বনিম্ন হয়।
একটি $n \times n$ ম্যাট্রিক্স $A$ দেওয়া আছে, $n$ দৈর্ঘ্যের একটি পারমুটেশন $p$ খুঁজে বের করতে হবে যাতে $\sum A[i]\left[p[i]\right]$ মান সর্বনিম্ন হয়।
প্রতি পার্টে $n$ টি ভার্টেক্স বিশিষ্ট একটি কমপ্লিট বাইপার্টাইট গ্রাফ বিবেচনা করুন, যেখানে প্রতিটি এজে একটি ওয়েট নির্ধারিত। লক্ষ্য হলো সর্বনিম্ন মোট ওয়েটের একটি পারফেক্ট ম্যাচিং খুঁজে বের করা।

এটি লক্ষ্য করা গুরুত্বপূর্ণ যে উপরের সমস্ত পরিস্থিতি “বর্গাকার” সমস্যা, অর্থাৎ উভয় মাত্রা সর্বদা $n$ এর সমান। বাস্তবে, প্রায়ই “আয়তাকার” রূপ দেখা যায় যেখানে $n$ $m$ এর সমান নয়, এবং কাজটি হলো $\min(n,m)$ টি উপাদান নির্বাচন করা। তবে, এটি লক্ষ্য করা যায় যে একটি “আয়তাকার” সমস্যা সবসময় শূন্য বা অসীম মানের সারি বা কলাম যোগ করে “বর্গাকার” সমস্যায় রূপান্তরিত করা যায়।

আমরা এটিও লক্ষ্য করি যে সর্বনিম্ন সমাধান খোঁজার অনুরূপ, সর্বাধিক সমাধান খোঁজার সমস্যাও করা যায়। তবে, এই দুটি সমস্যা একে অপরের সমতুল্য: সমস্ত ওয়েটকে $-1$ দিয়ে গুণ করাই যথেষ্ট।

হাঙ্গেরিয়ান অ্যালগরিদম#

ঐতিহাসিক তথ্য#

এই অ্যালগরিদমটি হ্যারল্ড কুন ১৯৫৫ সালে তৈরি ও প্রকাশ করেন। কুন নিজেই এর নাম দেন “হাঙ্গেরিয়ান” কারণ এটি হাঙ্গেরিয়ান গণিতবিদ ডেনেশ ক্যোনিগ ও ইয়েনো এগেরভারির পূর্ববর্তী কাজের উপর ভিত্তি করে তৈরি।
১৯৫৭ সালে, জেমস মুঙ্করেশ দেখান যে এই অ্যালগরিদম (কঠোরভাবে) পলিনোমিয়াল সময়ে চলে, খরচ নির্বিশেষে।
তাই সাহিত্যে, এই অ্যালগরিদম শুধু “হাঙ্গেরিয়ান” নয়, বরং “কুন-মুঙ্করেশ অ্যালগরিদম” বা “মুঙ্করেশ অ্যালগরিদম” নামেও পরিচিত।
তবে, সম্প্রতি ২০০৬ সালে আবিষ্কৃত হয়েছে যে কুনের এক শতাব্দী আগে জার্মান গণিতবিদ কার্ল গুস্তাভ ইয়াকোবি একই অ্যালগরিদম আবিষ্কার করেছিলেন। তাঁর কাজ, সাধারণ সাধারণ ডিফারেনশিয়াল সমীকরণের একটি সিস্টেমের ক্রম গবেষণা সম্পর্কে, যেটি ১৮৯০ সালে মরণোত্তর প্রকাশিত হয়েছিল, অন্যান্য ফলাফলের মধ্যে, অ্যাসাইনমেন্ট সমস্যা সমাধানের একটি পলিনোমিয়াল অ্যালগরিদম ধারণ করেছিল। দুর্ভাগ্যবশত, প্রকাশনাটি ল্যাটিনে হওয়ায় এটি গণিতবিদদের দৃষ্টি এড়িয়ে যায়।

এটিও উল্লেখযোগ্য যে কুনের মূল অ্যালগরিদমের অ্যাসিম্পটোটিক কমপ্লেক্সিটি ছিল $\mathcal{O}(n^4)$, এবং পরে জ্যাক এডমন্ডস ও রিচার্ড কার্প (এবং স্বাধীনভাবে তোমিজাওয়া) দেখান কীভাবে এটিকে $\mathcal{O}(n^3)$ অ্যাসিম্পটোটিক কমপ্লেক্সিটিতে উন্নত করা যায়।

$\mathcal{O}(n^4)$ অ্যালগরিদম#

অস্পষ্টতা এড়াতে, আমরা এখনই উল্লেখ করি যে আমরা মূলত ম্যাট্রিক্স রূপে অ্যাসাইনমেন্ট সমস্যা নিয়ে কাজ করছি (অর্থাৎ একটি ম্যাট্রিক্স $A$ দেওয়া আছে, এটি থেকে $n$ টি সেল নির্বাচন করতে হবে যেগুলো ভিন্ন সারি এবং কলামে)। আমরা ১ থেকে শুরু করে অ্যারে ইনডেক্স করি, অর্থাৎ উদাহরণস্বরূপ একটি ম্যাট্রিক্স $A$ এর ইনডেক্স $A[1 \dots n][1 \dots n]$।

আমরা এটিও ধরে নিই যে ম্যাট্রিক্স A-র সমস্ত সংখ্যা অ-ঋণাত্মক (যদি এটি না হয়, সমস্ত সংখ্যায় কোনো ধ্রুবক যোগ করে ম্যাট্রিক্সকে সর্বদা অ-ঋণাত্মক করা যায়)।

আসুন সংখ্যার দুটি ইচ্ছামতো অ্যারে $u[1 \ldots n]$ এবং $v[1 \ldots n]$ কে একটি পটেনশিয়াল বলি, যাতে নিম্নলিখিত শর্ত পূরণ হয়:

$$u[i]+v[j]\leq A[i][j],\quad i=1\dots n,\ j=1\dots n$$

(যেমনটি দেখা যাচ্ছে, $u[i]$ $i$-তম সারির সাথে সম্পর্কিত, এবং $v[j]$ ম্যাট্রিক্সের $j$-তম কলামের সাথে সম্পর্কিত)।

আসুন পটেনশিয়ালের মান $f$ কে এর উপাদানগুলোর যোগফল বলি:

$$f=\sum_{i=1}^{n} u[i] + \sum_{j=1}^{n} v[j].$$

একদিকে, এটি দেখা সহজ যে কাঙ্ক্ষিত সমাধান $sol$ এর খরচ যেকোনো পটেনশিয়ালের মানের চেয়ে কম নয়।

Info

লেমা। $sol\geq f.$

প্রমাণ

সমস্যার কাঙ্ক্ষিত সমাধান ম্যাট্রিক্স $A$ এর $n$ টি সেল নিয়ে গঠিত, তাই প্রতিটির জন্য $u[i]+v[j]\leq A[i][j]$। যেহেতু $sol$ এর সমস্ত উপাদান ভিন্ন সারি এবং কলামে, সমস্ত নির্বাচিত $A[i][j]$ এর উপর এই অসমতাগুলো যোগ করলে, অসমতার বাম পাশে $f$ এবং ডান পাশে $sol$ পাওয়া যায়।

অন্যদিকে, দেখা যায় যে সর্বদা একটি সমাধান এবং একটি পটেনশিয়াল পাওয়া যায় যেটি এই অসমতাকে সমতায় পরিণত করে। নিচে বর্ণিত হাঙ্গেরিয়ান অ্যালগরিদম এই তথ্যের একটি গঠনমূলক প্রমাণ হবে। আপাতত, শুধু লক্ষ্য করি যে যদি কোনো সমাধানের খরচ কোনো পটেনশিয়ালের সমান হয়, তাহলে সেই সমাধান অপটিমাল।

আসুন কোনো পটেনশিয়াল ঠিক করি। একটি এজ $(i,j)$ কে রিজিড বলি যদি $u[i]+v[j]=A[i][j].$

বাইপার্টাইট গ্রাফে অ্যাসাইনমেন্ট সমস্যার বিকল্প রূপ স্মরণ করি। $H$ দিয়ে শুধুমাত্র রিজিড এজ দিয়ে গঠিত বাইপার্টাইট গ্রাফ বোঝাই। হাঙ্গেরিয়ান অ্যালগরিদম বর্তমান পটেনশিয়ালের জন্য গ্রাফ $H$ এর সর্বাধিক-এজ-সংখ্যার ম্যাচিং $M$ বজায় রাখবে। $M$ এ $n$ টি এজ থাকলেই সমস্যার সমাধান হলো $M$ (যেহেতু এটি এমন একটি সমাধান হবে যার খরচ পটেনশিয়ালের মানের সাথে মিলে যায়)।

এখন সরাসরি অ্যালগরিদমের বর্ণনায় আসা যাক।

ধাপ ১। শুরুতে পটেনশিয়াল শূন্য ধরা হয় (সমস্ত $i$ এর জন্য $u[i]=v[i]=0$), এবং ম্যাচিং $M$ খালি ধরা হয়।

ধাপ ২। এরপর, অ্যালগরিদমের প্রতিটি ধাপে, আমরা পটেনশিয়াল পরিবর্তন না করে বর্তমান ম্যাচিং $M$ এর কার্ডিনালিটি এক বাড়ানোর চেষ্টা করি (স্মরণ করুন যে ম্যাচিং রিজিড এজের গ্রাফ $H$ এ খোঁজা হয়)। এর জন্য, বাইপার্টাইট গ্রাফে ম্যাক্সিমাম ম্যাচিং খোঁজার কুন অ্যালগরিদম ব্যবহৃত হয়। আসুন অ্যালগরিদমটি এখানে স্মরণ করি। ম্যাচিং $M$ এর সমস্ত এজ ডান অংশ থেকে বাম অংশে নির্দেশিত, এবং গ্রাফ $H$ এর অন্যান্য সমস্ত এজ বিপরীত দিকে নির্দেশিত।

স্মরণ করি (ম্যাচিং খোঁজার পরিভাষা থেকে) যে একটি ভার্টেক্সকে স্যাচুরেটেড বলা হয় যদি বর্তমান ম্যাচিং-এর একটি এজ এর সাথে সংশ্লিষ্ট হয়। বর্তমান ম্যাচিং-এর কোনো এজের সাথে সংশ্লিষ্ট নয় এমন ভার্টেক্সকে আনস্যাচুরেটেড বলা হয়। বিজোড় দৈর্ঘ্যের একটি পাথ, যার প্রথম এজ ম্যাচিং-এ নেই, এবং পরবর্তী সমস্ত এজের জন্য ম্যাচিং-এ থাকা/না-থাকা পর্যায়ক্রমে হয় - একে অগমেন্টিং পাথ বলা হয়। বাম অংশের সমস্ত আনস্যাচুরেটেড ভার্টেক্স থেকে একটি ডেপথ-ফার্স্ট বা ব্রেডথ-ফার্স্ট ট্রাভার্সাল শুরু করা হয়। সার্চের ফলে যদি ডান অংশের একটি আনস্যাচুরেটেড ভার্টেক্সে পৌঁছানো যায়, আমরা বাম অংশ থেকে ডান অংশে একটি অগমেন্টিং পাথ পেয়েছি। যদি আমরা পাথের বিজোড় এজগুলো ম্যাচিং-এ অন্তর্ভুক্ত করি এবং জোড় এজগুলো বাদ দিই (অর্থাৎ প্রথম এজ ম্যাচিং-এ অন্তর্ভুক্ত, দ্বিতীয় বাদ, তৃতীয় অন্তর্ভুক্ত ইত্যাদি), তাহলে আমরা ম্যাচিং কার্ডিনালিটি এক বাড়াব।

যদি কোনো অগমেন্টিং পাথ না পাওয়া যায়, তাহলে বর্তমান ম্যাচিং $M$ গ্রাফ $H$ এ ম্যাক্সিমাল।

ধাপ ৩। যদি বর্তমান ধাপে বর্তমান ম্যাচিং-এর কার্ডিনালিটি বাড়ানো সম্ভব না হয়, তাহলে পটেনশিয়াল এমনভাবে পুনরায় গণনা করা হয় যাতে পরবর্তী ধাপে ম্যাচিং বাড়ানোর আরও সুযোগ তৈরি হয়।

$Z_1$ দিয়ে কুন অ্যালগরিদমের শেষ ট্রাভার্সালে পরিদর্শিত বাম অংশের ভার্টেক্সের সেট এবং $Z_2$ দিয়ে পরিদর্শিত ডান অংশের ভার্টেক্সের সেট বোঝাই।

$\Delta$ মানটি গণনা করি:

$$\Delta = \min_{i\in Z_1,\ j\notin Z_2} A[i][j]-u[i]-v[j].$$

Info

লেমা। $\Delta > 0.$

প্রমাণ

ধরি $\Delta=0$। তাহলে $i\in Z_1$ এবং $j\notin Z_2$ সহ একটি রিজিড এজ $(i,j)$ আছে। এর ফলে এজ $(i,j)$ ডান অংশ থেকে বাম অংশে নির্দেশিত হতে হবে, অর্থাৎ $(i,j)$ ম্যাচিং $M$ এ অন্তর্ভুক্ত হতে হবে। তবে, এটি অসম্ভব, কারণ আমরা $j$ থেকে $i$ তে যাওয়া এজ ছাড়া স্যাচুরেটেড ভার্টেক্স $i$ তে পৌঁছাতে পারতাম না। তাই $\Delta > 0$।

এখন এভাবে পটেনশিয়াল পুনরায় গণনা করি:

সমস্ত ভার্টেক্স $i\in Z_1$ এর জন্য, $u[i] \gets u[i]+\Delta$ করি,
সমস্ত ভার্টেক্স $j\in Z_2$ এর জন্য, $v[j] \gets v[j]-\Delta$ করি।

Info

লেমা। ফলস্বরূপ পটেনশিয়াল এখনো একটি সঠিক পটেনশিয়াল।

প্রমাণ

আমরা দেখাব যে, পুনরায় গণনার পর, সমস্ত $i,j$ এর জন্য $u[i]+v[j]\leq A[i][j]$। $i\in Z_1$ এবং $j\in Z_2$ সহ $A$ এর সমস্ত উপাদানের জন্য, $u[i]+v[j]$ যোগফল পরিবর্তন হয় না, তাই অসমতা সত্য থাকে। $i\notin Z_1$ এবং $j\in Z_2$ সহ সমস্ত উপাদানের জন্য, $u[i]+v[j]$ যোগফল $\Delta$ কমে, তাই অসমতা এখনো সত্য। অন্যান্য উপাদানগুলোর জন্য যাদের $i\in Z_1$ এবং $j\notin Z_2$, যোগফল বাড়ে, কিন্তু অসমতা এখনো সংরক্ষিত, কারণ $\Delta$ মানটি, সংজ্ঞা অনুসারে, সেই সর্বাধিক বৃদ্ধি যা অসমতা পরিবর্তন করে না।

Info

লেমা। পুরনো ম্যাচিং $M$ রিজিড এজের বৈধ, অর্থাৎ ম্যাচিং-এর সমস্ত এজ রিজিড থাকবে।

প্রমাণ

কোনো রিজিড এজ $(i,j)$ পটেনশিয়াল পরিবর্তনের ফলে রিজিড না থাকতে হলে, সমতা $u[i] + v[j] = A[i][j]$ অসমতা $u[i] + v[j] < A[i][j]$ তে পরিণত হতে হবে। তবে, এটি শুধুমাত্র তখনই ঘটতে পারে যখন $i \notin Z_1$ এবং $j \in Z_2$। কিন্তু $i \notin Z_1$ বোঝায় যে এজ $(i,j)$ ম্যাচিং এজ হতে পারে না।

Info

লেমা। পটেনশিয়ালের প্রতিটি পুনরায় গণনার পর, ট্রাভার্সাল দ্বারা গম্য ভার্টেক্সের সংখ্যা, অর্থাৎ $|Z_1|+|Z_2|$, কঠোরভাবে বৃদ্ধি পায়।

প্রমাণ

প্রথমত, লক্ষ্য করুন যে পুনরায় গণনার আগে যে কোনো ভার্টেক্স গম্য ছিল, সেটি এখনো গম্য। প্রকৃতপক্ষে, যদি কোনো ভার্টেক্স গম্য হয়, তাহলে বাম অংশের আনস্যাচুরেটেড ভার্টেক্স থেকে শুরু করে গম্য ভার্টেক্সের মধ্য দিয়ে কোনো পাথ আছে; যেহেতু $(i,j),\ i\in Z_1,\ j\in Z_2$ আকারের এজগুলোর জন্য $u[i]+v[j]$ যোগফল পরিবর্তন হয় না, পটেনশিয়াল পরিবর্তনের পরও এই সম্পূর্ণ পাথ সংরক্ষিত থাকবে। দ্বিতীয়ত, আমরা দেখাই যে পুনরায় গণনার পর, কমপক্ষে একটি নতুন ভার্টেক্স গম্য হবে। এটি $\Delta$ এর সংজ্ঞা থেকে অনুসরণ করে: যে এজ $(i,j)$ এর জন্য $\Delta$ নির্ধারিত সেটি রিজিড হয়ে যাবে, তাই ভার্টেক্স $j$ ভার্টেক্স $i$ থেকে গম্য হবে।

শেষ লেমার কারণে, একটি অগমেন্টিং পাথ পাওয়া এবং ম্যাচিং $M$ এর কার্ডিনালিটি বাড়ানোর আগে সর্বাধিক $n$ বার পটেনশিয়াল পুনরায় গণনা হতে পারে। এভাবে, একটি পারফেক্ট ম্যাচিং $M^*$ এর সাথে সম্পর্কিত একটি পটেনশিয়াল শীঘ্রই বা পরে পাওয়া যাবে, এবং $M^*$ হবে সমস্যার উত্তর। অ্যালগরিদমের কমপ্লেক্সিটি নিয়ে বললে, এটি $\mathcal{O}(n^4)$: মোটে সর্বাধিক $n$ বার ম্যাচিং বৃদ্ধি হওয়া উচিত, প্রতিটির আগে সর্বাধিক $n$ বার পটেনশিয়াল পুনরায় গণনা, যার প্রতিটি $\mathcal{O}(n^2)$ সময়ে সম্পাদিত হয়।

আমরা এখানে $\mathcal{O}(n^4)$ অ্যালগরিদমের ইমপ্লিমেন্টেশন দেব না, কারণ এটি নিচে বর্ণিত $\mathcal{O}(n^3)$ এর ইমপ্লিমেন্টেশনের চেয়ে ছোট হবে না।

$\mathcal{O}(n^3)$ অ্যালগরিদম#

এখন শিখি কীভাবে একই অ্যালগরিদম $\mathcal{O}(n^3)$ এ ইমপ্লিমেন্ট করতে হয় (আয়তাকার সমস্যা $n \times m$ এর জন্য $\mathcal{O}(n^2m)$)।

মূল ধারণা হলো ম্যাট্রিক্সের সারিগুলো একটি করে বিবেচনা করা, একবারে সব নয়। এভাবে, উপরে বর্ণিত অ্যালগরিদম নিম্নলিখিত রূপ নেবে:

১. ম্যাট্রিক্স $A$ এর পরবর্তী সারি বিবেচনা করুন।

২. যতক্ষণ এই সারি থেকে শুরু করে কোনো অগমেন্টিং পাথ না পাওয়া যায়, পটেনশিয়াল পুনরায় গণনা করুন।

৩. অগমেন্টিং পাথ পাওয়া মাত্র, এটি বরাবর ম্যাচিং প্রচার করুন (এভাবে শেষ এজটি ম্যাচিং-এ অন্তর্ভুক্ত করা), এবং ধাপ ১ থেকে পুনরায় শুরু করুন (পরবর্তী সারি বিবেচনা করতে)।

প্রয়োজনীয় কমপ্লেক্সিটি অর্জন করতে, ধাপ ২-৩ ম্যাট্রিক্সের প্রতিটি সারির জন্য $\mathcal{O}(n^2)$ সময়ে (আয়তাকার সমস্যায় $\mathcal{O}(nm)$) ইমপ্লিমেন্ট করা প্রয়োজন।

এটি করতে, উপরে প্রমাণিত দুটি তথ্য স্মরণ করি:

পটেনশিয়াল পরিবর্তনে, কুনের ট্রাভার্সাল দ্বারা গম্য ভার্টেক্সগুলো গম্যই থাকবে।
মোটে, অগমেন্টিং পাথ পাওয়ার আগে শুধুমাত্র $\mathcal{O}(n)$ বার পটেনশিয়াল পুনরায় গণনা হতে পারে।

এ থেকে এই মূল ধারণাগুলো অনুসরণ করে যা আমাদের প্রয়োজনীয় কমপ্লেক্সিটি অর্জন করতে দেয়:

অগমেন্টিং পাথের উপস্থিতি পরীক্ষা করতে, প্রতিটি পটেনশিয়াল পুনরায় গণনার পর কুন ট্রাভার্সাল আবার শুরু করার প্রয়োজন নেই। পরিবর্তে, আপনি কুন ট্রাভার্সালকে একটি ইটারেটিভ রূপে করতে পারেন: প্রতিটি পটেনশিয়াল পুনরায় গণনার পর, যোগ হওয়া রিজিড এজগুলো দেখুন এবং, যদি তাদের বাম প্রান্ত গম্য ছিল, তাদের ডান প্রান্তগুলোও গম্য হিসেবে চিহ্নিত করুন এবং সেখান থেকে ট্রাভার্সাল চালিয়ে যান।
এই ধারণাটি আরও বিকশিত করে, আমরা অ্যালগরিদমকে এভাবে উপস্থাপন করতে পারি: লুপের প্রতিটি ধাপে পটেনশিয়াল পুনরায় গণনা করা হয়। পরবর্তীতে, একটি কলাম চিহ্নিত করা হয় যেটি গম্য হয়েছে (যেটি সর্বদা থাকবে কারণ প্রতিটি পটেনশিয়াল পুনরায় গণনার পর নতুন গম্য ভার্টেক্স আসে)। যদি কলামটি আনস্যাচুরেটেড হয়, একটি অগমেন্টিং চেইন আবিষ্কৃত হয়। বিপরীতভাবে, যদি কলামটি স্যাচুরেটেড হয়, ম্যাচিং সারিটিও গম্য হয়ে যায়।
পটেনশিয়াল দ্রুত পুনরায় গণনা করতে ($\mathcal{O}(n^2)$ নেইভ সংস্করণের চেয়ে দ্রুত), প্রতিটি কলামের জন্য সহায়ক ন্যূনতম মান বজায় রাখতে হবে:

$minv[j]=\min_{i\in Z_1} A[i][j]-u[i]-v[j].$

এটি দেখা সহজ যে কাঙ্ক্ষিত মান $\Delta$ এগুলো দিয়ে নিম্নরূপ প্রকাশ করা যায়:

$\Delta=\min_{j\notin Z_2} minv[j].$

এভাবে, $\Delta$ খোঁজা এখন $\mathcal{O}(n)$ এ করা যায়।
নতুন পরিদর্শিত সারি আসলে $minv$ অ্যারে আপডেট করতে হবে। এটি যোগ করা সারির জন্য $\mathcal{O}(n)$ এ করা যায় (যা সমস্ত সারি মিলে $\mathcal{O}(n^2)$ হয়)। পটেনশিয়াল পুনরায় গণনার সময়ও $minv$ অ্যারে আপডেট করতে হবে, যেটিও $\mathcal{O}(n)$ সময়ে করা হয় ($minv$ শুধুমাত্র সেই কলামগুলোর জন্য পরিবর্তিত হয় যেগুলো এখনো গম্য হয়নি: যথা, এটি $\Delta$ কমে)।

এভাবে, অ্যালগরিদমটি নিম্নলিখিত রূপ নেয়: বাইরের লুপে, আমরা ম্যাট্রিক্সের সারিগুলো একটি করে বিবেচনা করি। প্রতিটি সারি $\mathcal{O}(n^2)$ সময়ে প্রক্রিয়া করা হয়, যেহেতু শুধুমাত্র $\mathcal{O}(n)$ বার পটেনশিয়াল পুনরায় গণনা হতে পারে (প্রতিটি $\mathcal{O}(n)$ সময়ে), এবং $minv$ অ্যারে $\mathcal{O}(n^2)$ সময়ে বজায় রাখা হয়; কুনের অ্যালগরিদম $\mathcal{O}(n^2)$ সময়ে কাজ করবে (যেহেতু এটি $\mathcal{O}(n)$ ইটারেশনের রূপে উপস্থাপিত, যার প্রতিটি একটি নতুন কলাম পরিদর্শন করে)।

ফলস্বরূপ কমপ্লেক্সিটি $\mathcal{O}(n^3)$ বা, সমস্যা আয়তাকার হলে, $\mathcal{O}(n^2m)$।

হাঙ্গেরিয়ান অ্যালগরিদমের ইমপ্লিমেন্টেশন#

নিচের ইমপ্লিমেন্টেশনটি কয়েক বছর আগে আন্দ্রে লোপাতিন তৈরি করেছিলেন। এটি আশ্চর্যজনক সংক্ষিপ্ততায় আলাদা: সম্পূর্ণ অ্যালগরিদম ৩০ লাইনের কোডে গঠিত।

ইমপ্লিমেন্টেশনটি $A[1\dots n][1\dots m]$ আয়তাকার ম্যাট্রিক্সের জন্য সমাধান খুঁজে, যেখানে $n\leq m$। ম্যাট্রিক্সটি সুবিধা ও কোডের সংক্ষিপ্ততার জন্য ১-ভিত্তিক: এই ইমপ্লিমেন্টেশন একটি ডামি শূন্য সারি ও শূন্য কলাম প্রবর্তন করে, যা আমাদের অতিরিক্ত চেক ছাড়া অনেক সাইকেল সাধারণ রূপে লিখতে দেয়।

$u[0 \ldots n]$ এবং $v[0 \ldots m]$ অ্যারে পটেনশিয়াল সংরক্ষণ করে। প্রাথমিকভাবে, এগুলো শূন্যে সেট করা হয়, যা শূন্য সারি ম্যাট্রিক্সের সাথে সামঞ্জস্যপূর্ণ (লক্ষ্য করুন যে এই ইমপ্লিমেন্টেশনের জন্য ম্যাট্রিক্স $A$ তে ঋণাত্মক সংখ্যা আছে কিনা তা গুরুত্বপূর্ণ নয়)।

$p[0 \ldots m]$ অ্যারে একটি ম্যাচিং ধারণ করে: প্রতিটি কলাম $j = 1 \ldots m$ এর জন্য, এটি নির্বাচিত সারির সংখ্যা $p[j]$ সংরক্ষণ করে (বা $0$ যদি কিছু নির্বাচিত না হয়)। ইমপ্লিমেন্টেশনের সুবিধার্থে, $p[0]$ বর্তমান সারির সংখ্যার সমান ধরা হয়।

$minv[1 \ldots m]$ অ্যারে, প্রতিটি কলাম $j$ এর জন্য, পটেনশিয়ালের দ্রুত পুনরায় গণনার জন্য প্রয়োজনীয় সহায়ক ন্যূনতম মান ধারণ করে, যেমন উপরে বর্ণিত হয়েছে।

$way[1 \ldots m]$ অ্যারে তথ্য ধারণ করে কোথায় এই ন্যূনতম মানগুলো পৌঁছায় যাতে আমরা পরে অগমেন্টিং পাথ পুনর্গঠন করতে পারি। লক্ষ্য করুন যে, পাথ পুনর্গঠনের জন্য শুধু কলাম মান সংরক্ষণ করাই যথেষ্ট, কারণ সারি সংখ্যা ম্যাচিং (অর্থাৎ $p$ অ্যারে) থেকে নেওয়া যায়। এভাবে, প্রতিটি কলাম $j$ এর জন্য $way[j]$ পাথে পূর্ববর্তী কলামের সংখ্যা ধারণ করে (বা $0$ যদি না থাকে)।

অ্যালগরিদমটি হলো ম্যাট্রিক্সের সারি দিয়ে বাইরের লুপ, যার ভেতরে $i$-তম সারি বিবেচনা করা হয়। প্রথম do-while লুপটি চলে যতক্ষণ না একটি মুক্ত কলাম $j0$ পাওয়া যায়। লুপের প্রতিটি ইটারেশন $j0$ নম্বরের একটি নতুন কলাম (শেষ ইটারেশনে গণিত; এবং প্রাথমিকভাবে শূন্যের সমান - অর্থাৎ আমরা ডামি কলাম থেকে শুরু করি) এবং একটি নতুন সারি $i0$ - ম্যাচিং-এ এর সংশ্লিষ্ট (অর্থাৎ $p[j0]$; এবং প্রাথমিকভাবে যখন $j0=0$ তখন $i$-তম সারি নেওয়া হয়) পরিদর্শিত হিসেবে চিহ্নিত করে। নতুন পরিদর্শিত সারি $i0$ এর কারণে, আপনাকে $minv$ অ্যারে এবং $\Delta$ সেই অনুযায়ী পুনরায় গণনা করতে হবে। যদি $\Delta$ আপডেট হয়, তাহলে $j1$ কলামটি পৌঁছানো ন্যূনতম হয়ে যায় (লক্ষ্য করুন যে এমন ইমপ্লিমেন্টেশনে $\Delta$ শূন্য হতে পারে, যার মানে বর্তমান ধাপে পটেনশিয়াল পরিবর্তন করা যায় না: ইতিমধ্যে একটি নতুন গম্য কলাম আছে)। এরপর, পটেনশিয়াল এবং $minv$ অ্যারে পুনরায় গণনা করা হয়। “do-while” লুপের শেষে, আমরা $j0$ কলামে শেষ হওয়া একটি অগমেন্টিং পাথ পেয়েছি যেটি পূর্বসূরি অ্যারে $way$ ব্যবহার করে “আনরোল” করা যায়।

INF ধ্রুবকটি হলো “অসীম”, অর্থাৎ এমন একটি সংখ্যা যা স্পষ্টতই ইনপুট ম্যাট্রিক্স $A$ এর সমস্ত সম্ভাব্য সংখ্যার চেয়ে বড়।

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
for (int i=1; i<=n; ++i) {
    p[0] = i;
    int j0 = 0;
    vector<int> minv (m+1, INF);
    vector<bool> used (m+1, false);
    do {
        used[j0] = true;
        int i0 = p[j0],  delta = INF,  j1;
        for (int j=1; j<=m; ++j)
            if (!used[j]) {
                int cur = A[i0][j]-u[i0]-v[j];
                if (cur < minv[j])
                    minv[j] = cur,  way[j] = j0;
                if (minv[j] < delta)
                    delta = minv[j],  j1 = j;
            }
        for (int j=0; j<=m; ++j)
            if (used[j])
                u[p[j]] += delta,  v[j] -= delta;
            else
                minv[j] -= delta;
        j0 = j1;
    } while (p[j0] != 0);
    do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
    } while (j0);
}

আরও পরিচিত রূপে উত্তর পুনরুদ্ধার করতে, অর্থাৎ প্রতিটি সারি $i = 1 \ldots n$ এর জন্য এতে নির্বাচিত কলামের সংখ্যা $ans[i]$ খুঁজতে, নিম্নরূপ করা যায়:

vector<int> ans (n+1);
for (int j=1; j<=m; ++j)
    ans[p[j]] = j;

ম্যাচিং-এর খরচ কেবল শূন্য কলামের পটেনশিয়াল (বিপরীত চিহ্নসহ) হিসেবে নেওয়া যায়। প্রকৃতপক্ষে, কোড থেকে দেখা যায় যে $-v[0]$ সমস্ত $\Delta$ মানের যোগফল ধারণ করে, অর্থাৎ পটেনশিয়ালের মোট পরিবর্তন। যদিও একসাথে বেশ কয়েকটি $u[i]$ এবং $v[j]$ মান পরিবর্তিত হতে পারে, পটেনশিয়ালের মোট পরিবর্তন ঠিক $\Delta$ এর সমান, কারণ অগমেন্টিং পাথ না পাওয়া পর্যন্ত, গম্য সারির সংখ্যা গম্য কলামের সংখ্যার চেয়ে ঠিক এক বেশি (শুধুমাত্র বর্তমান সারি $i$ এর পরিদর্শিত কলামের রূপে “জোড়া” নেই):

int cost = -v[0];

সাক্সেসিভ শর্টেস্ট পাথ অ্যালগরিদমের সাথে সম্পর্ক#

হাঙ্গেরিয়ান অ্যালগরিদমকে সাক্সেসিভ শর্টেস্ট পাথ অ্যালগরিদম হিসেবে দেখা যায়, অ্যাসাইনমেন্ট সমস্যার জন্য অভিযোজিত। বিস্তারিত না গিয়ে, তাদের মধ্যে সম্পর্কের ব্যাপারে একটি স্বজ্ঞাত ধারণা দেওয়া যাক।

সাক্সেসিভ পাথ অ্যালগরিদম জনসনের অ্যালগরিদমের একটি পরিবর্তিত সংস্করণ রিওয়েটিং টেকনিক হিসেবে ব্যবহার করে। এটি চারটি ধাপে বিভক্ত:

সিঙ্ক $s$ থেকে শুরু করে বেলম্যান-ফোর্ড অ্যালগরিদম ব্যবহার করুন এবং, প্রতিটি নোডের জন্য, $s$ থেকে $v$ পর্যন্ত পাথের সর্বনিম্ন ওয়েট $h(v)$ খুঁজুন।

মূল অ্যালগরিদমের প্রতিটি ধাপের জন্য:

মূল গ্রাফের এজগুলো এভাবে রিওয়েট করুন: $w(u,v) \gets w(u,v)+h(u)-h(v)$।
মূল নেটওয়ার্কের শর্টেস্ট-পাথ সাবগ্রাফ খুঁজতে ডায়াক্সট্রা অ্যালগরিদম ব্যবহার করুন।
পরবর্তী ইটারেশনের জন্য পটেনশিয়াল আপডেট করুন।

এই বর্ণনা দেওয়া হলে, আমরা দেখতে পারি যে $h(v)$ এবং পটেনশিয়ালের মধ্যে একটি শক্তিশালী সাদৃশ্য আছে: এটি যাচাই করা যায় যে একটি ধ্রুবক অফসেট পর্যন্ত এগুলো সমান। এছাড়া, এটি দেখানো যায় যে, রিওয়েটিং-এর পরে, সমস্ত শূন্য-ওয়েট এজের সেট শর্টেস্ট-পাথ সাবগ্রাফ উপস্থাপন করে যেখানে মূল অ্যালগরিদম ফ্লো বাড়ানোর চেষ্টা করে। এটি হাঙ্গেরিয়ান অ্যালগরিদমেও ঘটে: আমরা রিজিড এজ দিয়ে (যেগুলোর জন্য $A[i][j]-u[i]-v[j]$ পরিমাণ শূন্য) একটি সাবগ্রাফ তৈরি করি, এবং ম্যাচিং-এর আকার বাড়ানোর চেষ্টা করি।

ধাপ ৪-এ, সমস্ত $h(v)$ আপডেট করা হয়: প্রতিবার আমরা ফ্লো নেটওয়ার্ক পরিবর্তন করলে, নিশ্চিত করতে হবে যে সোর্স থেকে দূরত্বগুলো সঠিক (অন্যথায়, পরবর্তী ইটারেশনে ডায়াক্সট্রা অ্যালগরিদম ব্যর্থ হতে পারে)। এটি পটেনশিয়ালে করা আপডেটের মতো শোনায়, কিন্তু এক্ষেত্রে এগুলো সমানভাবে বৃদ্ধি পায় না।

পটেনশিয়ালের গভীর বোঝাপড়ার জন্য, এই নিবন্ধটি দেখুন।

কাজের উদাহরণ#

এখানে অ্যাসাইনমেন্ট সমস্যা সম্পর্কিত কিছু উদাহরণ দেওয়া হলো, খুব তুচ্ছ থেকে কম স্পষ্ট কাজ পর্যন্ত:

একটি বাইপার্টাইট গ্রাফ দেওয়া আছে, এতে সর্বনিম্ন ওয়েটের ম্যাক্সিমাম ম্যাচিং খুঁজে বের করতে হবে (অর্থাৎ প্রথমত ম্যাচিং-এর আকার সর্বাধিক করা হয়, এবং দ্বিতীয়ত এর খরচ সর্বনিম্ন করা হয়)।
এটি সমাধান করতে, আমরা কেবল অনুপস্থিত এজের জায়গায় “অসীম” সংখ্যা রেখে একটি অ্যাসাইনমেন্ট সমস্যা তৈরি করি। তারপর, আমরা হাঙ্গেরিয়ান অ্যালগরিদম দিয়ে সমস্যাটি সমাধান করি, এবং উত্তর থেকে অসীম ওয়েটের এজ সরিয়ে দিই (এগুলো উত্তরে প্রবেশ করতে পারে যদি সমস্যার পারফেক্ট ম্যাচিং আকারে সমাধান না থাকে)।
একটি বাইপার্টাইট গ্রাফ দেওয়া আছে, এতে সর্বাধিক ওয়েটের ম্যাক্সিমাম ম্যাচিং খুঁজে বের করতে হবে।
সমাধান আবার স্পষ্ট, সমস্ত ওয়েটকে মাইনাস এক দিয়ে গুণ করতে হবে।
ইমেজে চলমান বস্তু সনাক্তকরণের কাজ: দুটি ইমেজ তোলা হয়েছে, যার ফলে দুটি স্থানাঙ্ক সেট পাওয়া গেছে। প্রথম ও দ্বিতীয় ইমেজের বস্তুগুলো সম্পর্কিত করতে হবে, অর্থাৎ দ্বিতীয় ইমেজের প্রতিটি বিন্দুর জন্য নির্ধারণ করতে হবে প্রথম ইমেজের কোন বিন্দুর সাথে এটি সম্পর্কিত ছিল। এক্ষেত্রে, তুলনা করা বিন্দুগুলোর মধ্যে দূরত্বের যোগফল সর্বনিম্ন করতে হবে (অর্থাৎ আমরা এমন একটি সমাধান খুঁজছি যেখানে বস্তুগুলো মোটে সবচেয়ে কম পথ অতিক্রম করেছে)।
সমাধানে, আমরা কেবল একটি অ্যাসাইনমেন্ট সমস্যা তৈরি ও সমাধান করি, যেখানে এজের ওয়েট হলো বিন্দুগুলোর মধ্যে ইউক্লিডীয় দূরত্ব।
লোকেটর দ্বারা চলমান বস্তু সনাক্তকরণের কাজ: দুটি লোকেটর আছে যেগুলো বস্তুর অবস্থান নির্ণয় করতে পারে না, শুধু তার দিক জানতে পারে। উভয় লোকেটর (বিভিন্ন বিন্দুতে অবস্থিত) $n$ টি এমন দিক আকারে তথ্য পেয়েছে। বস্তুগুলোর অবস্থান নির্ণয় করতে হবে, অর্থাৎ বস্তুগুলোর প্রত্যাশিত অবস্থান এবং তাদের সংশ্লিষ্ট দিক জোড়া নির্ধারণ করতে হবে এমনভাবে যাতে বস্তু থেকে দিক রশ্মি পর্যন্ত দূরত্বের যোগফল সর্বনিম্ন হয়।
সমাধান: আবার, আমরা কেবল অ্যাসাইনমেন্ট সমস্যা তৈরি ও সমাধান করি, যেখানে বাম অংশের ভার্টেক্সগুলো প্রথম লোকেটরের $n$ টি দিক, ডান অংশের ভার্টেক্সগুলো দ্বিতীয় লোকেটরের $n$ টি দিক, এবং এজের ওয়েটগুলো সংশ্লিষ্ট রশ্মির মধ্যে দূরত্ব।
ডিরেক্টেড অ্যাসাইক্লিক গ্রাফকে পাথ দিয়ে কভার করা: একটি ডিরেক্টেড অ্যাসাইক্লিক গ্রাফ দেওয়া আছে, সবচেয়ে কম সংখ্যক পাথ (সমান হলে, সর্বনিম্ন মোট ওয়েটসহ) খুঁজে বের করতে হবে যাতে গ্রাফের প্রতিটি ভার্টেক্স ঠিক একটি পাথে থাকে।
সমাধান হলো দেওয়া গ্রাফ থেকে সংশ্লিষ্ট বাইপার্টাইট গ্রাফ তৈরি করা এবং এতে সর্বনিম্ন ওয়েটের ম্যাক্সিমাম ম্যাচিং খোঁজা। আরও বিস্তারিতের জন্য আলাদা নিবন্ধ দেখুন।
ট্রি কালারিং বুক। একটি ট্রি দেওয়া আছে যেখানে পাতা ব্যতীত প্রতিটি ভার্টেক্সের ঠিক $k-1$ টি চাইল্ড আছে। প্রতিটি ভার্টেক্সের জন্য $k$ টি রংয়ের একটি বেছে নিতে হবে যাতে কোনো দুটি সংলগ্ন ভার্টেক্সের একই রং না হয়। এছাড়া, প্রতিটি ভার্টেক্স ও প্রতিটি রংয়ের জন্য, সেই ভার্টেক্সকে সেই রংয়ে রং করার খরচ জানা আছে, এবং মোট খরচ সর্বনিম্ন করতে হবে।
এই সমস্যা সমাধানে আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করি। যথা, আসুন $d[v][c]$ মান গণনা করতে শিখি, যেখানে $v$ হলো ভার্টেক্স নম্বর, $c$ হলো রং নম্বর, এবং $d[v][c]$ মানটি হলো $v$ তে রুটকৃত সাবট্রি-র সমস্ত ভার্টেক্স এবং ভার্টেক্স $v$ নিজেকে $c$ রংয়ে রং করতে প্রয়োজনীয় সর্বনিম্ন খরচ। $d[v][c]$ গণনা করতে, বাকি $k-1$ টি রং $v$ এর চাইল্ডদের মধ্যে বিতরণ করা প্রয়োজন, এবং এর জন্য অ্যাসাইনমেন্ট সমস্যা তৈরি ও সমাধান করা প্রয়োজন (যেখানে বাম অংশের ভার্টেক্সগুলো রং, ডান অংশের ভার্টেক্সগুলো চাইল্ড, এবং এজের ওয়েটগুলো $d$ এর সংশ্লিষ্ট মান)।
এভাবে প্রতিটি $d[v][c]$ মান অ্যাসাইনমেন্ট সমস্যার সমাধান ব্যবহার করে গণনা করা হয়, যা চূড়ান্ত অ্যাসিম্পটোটিক $\mathcal{O}(nk^4)$ দেয়।
যদি অ্যাসাইনমেন্ট সমস্যায় ওয়েট এজে নয়, ভার্টেক্সে থাকে, এবং শুধুমাত্র একই অংশের ভার্টেক্সে, তাহলে হাঙ্গেরিয়ান অ্যালগরিদম ব্যবহার করা প্রয়োজন নয়: কেবল ওয়েট অনুসারে ভার্টেক্স সর্ট করুন এবং সাধারণ কুন অ্যালগরিদম চালান (আরও বিস্তারিতের জন্য, আলাদা নিবন্ধ দেখুন)।
নিম্নলিখিত বিশেষ ক্ষেত্র বিবেচনা করুন। বাম অংশের প্রতিটি ভার্টেক্সে একটি সংখ্যা $\alpha[i]$ এবং ডান অংশের প্রতিটিতে $\beta[j]$ নির্ধারিত। যেকোনো এজ $(i,j)$ এর ওয়েট $\alpha[i]\cdot \beta[j]$ এর সমান ($\alpha[i]$ এবং $\beta[j]$ সংখ্যাগুলো জানা)। অ্যাসাইনমেন্ট সমস্যা সমাধান করুন।
এটি হাঙ্গেরিয়ান অ্যালগরিদম ছাড়া সমাধান করতে, প্রথমে দুটি ভার্টেক্স বিশিষ্ট উভয় অংশের ক্ষেত্র বিবেচনা করুন। এক্ষেত্রে, সহজেই দেখা যায় যে ভার্টেক্সগুলো বিপরীত ক্রমে সংযুক্ত করা ভালো: ছোট $\alpha[i]$ বিশিষ্ট ভার্টেক্সটিকে বড় $\beta[j]$ বিশিষ্ট ভার্টেক্সের সাথে সংযুক্ত করুন। এই নিয়মটি সহজেই যেকোনো সংখ্যক ভার্টেক্সে সাধারণীকরণ করা যায়: প্রথম অংশের ভার্টেক্সগুলো $\alpha[i]$ মানের ঊর্ধ্বক্রমে, দ্বিতীয় অংশেরগুলো $\beta[j]$ মানের নিম্নক্রমে সর্ট করুন, এবং সেই ক্রমে ভার্টেক্সগুলো জোড়ায় জোড়ায় সংযুক্ত করুন। এভাবে, আমরা $\mathcal{O}(n\log n)$ কমপ্লেক্সিটির একটি সমাধান পাই।
পটেনশিয়ালের সমস্যা। একটি ম্যাট্রিক্স $A[1 \ldots n][1 \ldots m]$ দেওয়া আছে, দুটি অ্যারে $u[1 \ldots n]$ এবং $v[1 \ldots m]$ খুঁজে বের করতে হবে যাতে, যেকোনো $i$ এবং $j$ এর জন্য, $u[i] + v[j] \leq a[i][j]$ এবং অ্যারে $u$ ও $v$ এর উপাদানের যোগফল সর্বাধিক হয়।
হাঙ্গেরিয়ান অ্যালগরিদম জানলে, এই সমস্যার সমাধান কঠিন হবে না: হাঙ্গেরিয়ান অ্যালগরিদম ঠিক এমন পটেনশিয়াল $u, v$ খুঁজে পায় যেটি সমস্যার শর্ত পূরণ করে। অন্যদিকে, হাঙ্গেরিয়ান অ্যালগরিদমের জ্ঞান ছাড়া এমন সমস্যা সমাধান করা প্রায় অসম্ভব বলে মনে হয়।
!!! info “মন্তব্য”
```
  এই কাজটি অ্যাসাইনমেন্ট সমস্যার **ডুয়াল সমস্যা** নামেও পরিচিত: অ্যাসাইনমেন্টের মোট খরচ সর্বনিম্ন করা পটেনশিয়ালের যোগফল সর্বাধিক করার সমতুল্য।
```