پرش به محتویات

الگوریتم مجارستانی برای حل مسئله تخصیص

صورت مسئله تخصیص

چندین فرمول‌بندی استاندارد برای مسئله تخصیص وجود دارد (که همگی در اصل معادل هستند). در اینجا به چند مورد از آنها اشاره می‌کنیم:

  • $n$ شغل و $n$ کارگر وجود دارد. هر کارگر مبلغی را که برای انجام یک شغل خاص انتظار دارد، مشخص می‌کند. هر کارگر فقط به یک شغل می‌تواند تخصیص داده شود. هدف، تخصیص مشاغل به کارگران به گونه‌ای است که هزینه کل کمینه شود.

  • با توجه به یک ماتریس $n \times n$ به نام $A$، وظیفه این است که از هر سطر یک عدد انتخاب کنیم به طوری که دقیقاً یک عدد از هر ستون انتخاب شده باشد و مجموع اعداد انتخاب‌شده کمینه شود.

  • با توجه به یک ماتریس $n \times n$ به نام $A$، وظیفه یافتن جایگشت $p$ به طول $n$ است به طوری که مقدار $\sum A[i]\left[p[i]\right]$ کمینه شود.

  • یک گراف کامل دوبخشی با $n$ رأس در هر بخش را در نظر بگیرید که به هر یال یک وزن اختصاص داده شده است. هدف، یافتن یک تطابق کامل با کمترین وزن کل است.

توجه به این نکته مهم است که تمام سناریوهای فوق مسائل "مربعی" هستند، به این معنی که هر دو بعد همیشه برابر با $n$ هستند. در عمل، اغلب با فرمول‌بندی‌های مشابه "مستطیلی" مواجه می‌شویم که در آنها $n$ با $m$ برابر نیست و وظیفه انتخاب $\min(n,m)$ عنصر است. با این حال، می‌توان مشاهده کرد که یک مسئله "مستطیلی" را همیشه می‌توان با افزودن سطرها یا ستون‌هایی با مقادیر صفر یا بی‌نهایت، به یک مسئله "مربعی" تبدیل کرد.

همچنین توجه داشته باشید که به قیاس با جستجوی یک راه حل کمینه، می‌توان مسئله یافتن یک راه حل بیشینه را نیز مطرح کرد. با این حال، این دو مسئله معادل یکدیگر هستند: کافی است تمام وزن‌ها را در $-1$ ضرب کنیم.

الگوریتم مجارستانی

مرجع تاریخی

این الگوریتم توسط هارولد کوهن (Harold Kuhn) در سال ۱۹۵۵ توسعه و منتشر شد. خود کوهن به دلیل اینکه این الگوریتم بر اساس کارهای قبلی ریاضیدانان مجارستانی، دینس کونیگ (Dénes Kőnig) و ینو اگرواری (Jenő Egerváry) بود، نام "مجارستانی" را برای آن انتخاب کرد.
در سال ۱۹۵۷، جیمز مانکرس (James Munkres) نشان داد که این الگوریتم در زمان چندجمله‌ای (اکیداً) اجرا می‌شود، صرف نظر از هزینه.
بنابراین، در ادبیات علمی، این الگوریتم نه تنها به عنوان "مجارستانی"، بلکه به عنوان "الگوریتم کوهن-مانکرس" یا "الگوریتم مانکرس" نیز شناخته می‌شود.
با این حال، اخیراً در سال ۲۰۰۶ کشف شد که همین الگوریتم یک قرن قبل از کوهن توسط ریاضیدان آلمانی، کارل گوستاو یاکوبی (Carl Gustav Jacobi) ابداع شده بود. اثر او، درباره تحقیق در مورد مرتبه یک سیستم از معادلات دیفرانسیل معمولی دلخواه، که پس از مرگش در سال ۱۸۹۰ منتشر شد، در میان یافته‌های دیگر، شامل یک الگوریتم چندجمله‌ای برای حل مسئله تخصیص بود. متأسفانه، از آنجا که این اثر به زبان لاتین منتشر شده بود، در میان ریاضیدانان مورد توجه قرار نگرفت.

همچنین شایان ذکر است که الگوریتم اصلی کوهن دارای پیچیدگی مجانبی $\mathcal{O}(n^4)$ بود و تنها بعدها جک ادموندز (Jack Edmonds) و ریچارد کارپ (Richard Karp) (و به طور مستقل تومیزاوا (Tomizawa)) نشان دادند که چگونه می‌توان آن را به پیچیدگی مجانبی $\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$ کمتر از مقدار هر پتانسیلی نیست.

لم. $sol\geq f.$

اثبات

راه حل مطلوب مسئله شامل $n$ خانه از ماتریس $A$ است، بنابراین برای هر یک از آنها $u[i]+v[j]\leq A[i][j]$ برقرار است. از آنجا که تمام عناصر در $sol$ در سطرها و ستون‌های مختلفی قرار دارند، با جمع کردن این نابرابری‌ها بر روی تمام $A[i][j]$ های انتخاب‌شده، در سمت چپ نابرابری به $f$ و در سمت راست به $sol$ می‌رسید.

از سوی دیگر، معلوم می‌شود که همیشه یک راه حل و یک پتانسیل وجود دارد که این نابرابری را به تساوی تبدیل می‌کند. الگوریتم مجارستانی که در ادامه شرح داده می‌شود، یک اثبات سازنده برای این واقعیت خواهد بود. در حال حاضر، فقط به این نکته توجه می‌کنیم که اگر هر راه حلی هزینه‌ای برابر با هر پتانسیلی داشته باشد، آنگاه این راه حل بهینه است.

یک پتانسیل را ثابت در نظر بگیرید. یال $(i,j)$ را سفت (rigid) می‌نامیم اگر $u[i]+v[j]=A[i][j].$

فرمول‌بندی جایگزین مسئله تخصیص با استفاده از گراف دوبخشی را به یاد بیاورید. یک گراف دوبخشی $H$ را که فقط از یال‌های سفت تشکیل شده است، در نظر بگیرید. الگوریتم مجارستانی برای پتانسیل فعلی، تطابق با بیشترین تعداد یال $M$ از گراف $H$ را حفظ می‌کند. به محض اینکه $M$ شامل $n$ یال شود، راه حل مسئله همان $M$ خواهد بود (چرا که این یک راه حل خواهد بود که هزینه‌اش با مقدار یک پتانسیل برابر است).

بیایید مستقیماً به شرح الگوریتم بپردازیم.

گام ۱. در ابتدا، پتانسیل صفر فرض می‌شود ($u[i]=v[i]=0$ برای همه $i$ ها) و تطابق $M$ خالی در نظر گرفته می‌شود.

گام ۲. در ادامه، در هر مرحله از الگوریتم، سعی می‌کنیم بدون تغییر پتانسیل، اندازه تطابق فعلی $M$ را یک واحد افزایش دهیم (به یاد داشته باشید که تطابق در گراف یال‌های سفت $H$ جستجو می‌شود). برای این کار، از الگوریتم کوهن برای یافتن تطابق بیشینه در گراف‌های دوبخشی استفاده می‌شود. الگوریتم را در اینجا یادآوری می‌کنیم. تمام یال‌های تطابق $M$ از بخش راست به بخش چپ جهت‌دهی می‌شوند و تمام یال‌های دیگر گراف $H$ در جهت مخالف جهت‌دهی می‌شوند.

به یاد بیاورید (از اصطلاحات جستجوی تطابق) که یک رأس اشباع‌شده (saturated) نامیده می‌شود اگر یک یال از تطابق فعلی به آن متصل باشد. رأسی که به هیچ یال از تطابق فعلی متصل نباشد، اشباع‌نشده (unsaturated) نامیده می‌شود. مسیری با طول فرد که یال اول آن به تطابق تعلق ندارد و برای تمام یال‌های بعدی، تعلق به تطابق به صورت متناوب (تعلق دارد/ندارد) تغییر می‌کند، مسیر افزایشی (augmenting path) نامیده می‌شود. از تمام رئوس اشباع‌نشده در بخش چپ، پیمایش عمق-اول یا سطح-اول شروع می‌شود. اگر در نتیجه جستجو، بتوان به یک رأس اشباع‌نشده از بخش راست رسید، یک مسیر افزایشی از بخش چپ به بخش راست پیدا کرده‌ایم. اگر یال‌های فرد مسیر را به تطابق اضافه کنیم و یال‌های زوج را از آن حذف کنیم (یعنی یال اول را در تطابق بگنجانیم، دومی را حذف کنیم، سومی را بگنجانیم و غیره)، اندازه تطابق را یک واحد افزایش خواهیم داد.

اگر مسیر افزایشی وجود نداشته باشد، تطابق فعلی $M$ در گراف $H$ بیشینه است.

گام ۳. اگر در مرحله فعلی، امکان افزایش اندازه تطابق فعلی وجود نداشته باشد، پتانسیل به گونه‌ای باز محاسبه می‌شود که در مراحل بعدی، فرصت‌های بیشتری برای افزایش تطابق وجود داشته باشد.

مجموعه رئوس بخش چپ را که در آخرین پیمایش الگوریتم کوهن بازدید شده‌اند با $Z_1$ و مجموعه رئوس بازدید شده بخش راست را با $Z_2$ نشان می‌دهیم.

مقدار $\Delta$ را محاسبه می‌کنیم:

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

لم. $\Delta > 0.$

اثبات

فرض کنید $\Delta=0$. در این صورت، یک یال سفت $(i,j)$ با $i\in Z_1$ و $j\notin Z_2$ وجود دارد. از این رو، یال $(i,j)$ باید از بخش راست به بخش چپ جهت‌دهی شده باشد، یعنی $(i,j)$ باید در تطابق $M$ گنجانده شده باشد. با این حال، این غیرممکن است، زیرا نمی‌توانستیم به رأس اشباع‌شده $i$ برسیم مگر با پیمودن یال از j به i. بنابراین $\Delta > 0$ است.

اکنون پتانسیل را به این صورت باز محاسبه می‌کنیم:

  • برای تمام رئوس $i\in Z_1$، قرار می‌دهیم $u[i] \gets u[i]+\Delta$
  • برای تمام رئوس $j\in Z_2$، قرار می‌دهیم $v[j] \gets v[j]-\Delta$

لم. پتانسیل حاصل همچنان یک پتانسیل معتبر است.

اثبات

نشان خواهیم داد که پس از باز محاسبه، برای تمام $i,j$ ها $u[i]+v[j]\leq A[i][j]$ برقرار است. برای تمام عناصر $A$ با $i\in Z_1$ و $j\in Z_2$، مجموع $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$ طبق تعریف، حداکثر افزایشی است که نابرابری را تغییر نمی‌دهد.

لم. تطابق قدیمی $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)$ نمی‌تواند یک یال تطابق باشد.

لم. پس از هر بار باز محاسبه پتانسیل، تعداد رئوس قابل دسترس توسط پیمایش، یعنی $|Z_1|+|Z_2|$، اکیداً افزایش می‌یابد.

اثبات

ابتدا، توجه کنید که هر رأسی که قبل از باز محاسبه قابل دسترس بود، همچنان قابل دسترس است. در واقع، اگر رأسی قابل دسترس باشد، مسیری از رئوس قابل دسترس به آن وجود دارد که از رأس اشباع‌نشده بخش چپ شروع می‌شود؛ از آنجا که برای یال‌های به شکل $(i,j)$ با $i\in Z_1, j\in Z_2$ مجموع $u[i]+v[j]$ تغییر نمی‌کند، کل این مسیر پس از تغییر پتانسیل حفظ خواهد شد. ثانیاً، نشان می‌دهیم که پس از باز محاسبه، حداقل یک رأس جدید قابل دسترس خواهد بود. این از تعریف $\Delta$ نتیجه می‌شود: یالی $(i,j)$ که $\Delta$ به آن اشاره دارد، سفت خواهد شد، بنابراین رأس $j$ از رأس $i$ قابل دسترس خواهد بود.

با توجه به لم آخر، نمی‌تواند بیش از $n$ باز محاسبه پتانسیل رخ دهد قبل از اینکه یک مسیر افزایشی پیدا شود و اندازه تطابق $M$ افزایش یابد. بنابراین، دیر یا زود، پتانسیلی که با یک تطابق کامل $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)$).

ایده اصلی این است که سطرهای ماتریس را یک به یک و نه همه را با هم در نظر بگیریم. بنابراین، الگوریتم توصیف‌شده در بالا شکل زیر را به خود می‌گیرد:

  1. سطر بعدی ماتریس $A$ را در نظر بگیرید.

  2. تا زمانی که هیچ مسیر افزایشی از این سطر شروع نشود، پتانسیل را باز محاسبه کنید.

  3. به محض یافتن یک مسیر افزایشی، تطابق را در طول آن گسترش دهید (و در نتیجه یال آخر را در تطابق بگنجانید) و از مرحله ۱ دوباره شروع کنید (تا سطر بعدی را در نظر بگیرید).

برای رسیدن به پیچیدگی مورد نیاز، لازم است مراحل ۲-۳ که برای هر سطر ماتریس انجام می‌شوند، در زمان $\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)$ است.

پیاده‌سازی الگوریتم مجارستانی

پیاده‌سازی زیر توسط آندری لوپاتین (Andrey Lopatin) چندین سال پیش توسعه یافته است. این پیاده‌سازی با ایجاز شگفت‌انگیزش متمایز می‌شود: کل الگوریتم از ۳۰ خط کد تشکیل شده است.

این پیاده‌سازی برای ماتریس مستطیلی $A[1\dots n][1\dots m]$ که در آن $n\leq m$ است، راه حلی پیدا می‌کند. ماتریس برای راحتی و کوتاهی کد، ۱-پایه (1-based) است: این پیاده‌سازی یک سطر و ستون صفر مجازی (dummy) معرفی می‌کند که به ما امکان می‌دهد بسیاری از حلقه‌ها را به شکل کلی و بدون بررسی‌های اضافی بنویسیم.

آرایه‌های $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$) گرفت. بنابراین، $way[j]$ برای هر ستون $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);
}

برای بازیابی پاسخ به شکلی آشناتر، یعنی یافتن شماره ستون $ans[i]$ انتخاب‌شده در هر سطر $i = 1 \ldots n$، می‌توان به صورت زیر عمل کرد:

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];

ارتباط با الگوریتم مسیرهای کوتاه متوالی

الگوریتم مجارستانی را می‌توان به عنوان الگوریتم مسیرهای کوتاه متوالی که برای مسئله تخصیص تطبیق داده شده است، در نظر گرفت. بدون پرداختن به جزئیات، بیایید یک شهود در مورد ارتباط بین آنها ارائه دهیم.

الگوریتم مسیرهای متوالی از نسخه اصلاح‌شده‌ای از الگوریتم جانسون به عنوان تکنیک بازوزن‌دهی (reweighting) استفاده می‌کند. این الگوریتم به چهار مرحله تقسیم می‌شود:

  • از الگوریتم بلمن-فورد استفاده کنید، از چاهک $s$ شروع کرده و برای هر گره، کمترین وزن $h(v)$ یک مسیر از $s$ به $v$ را پیدا کنید.

برای هر مرحله از الگوریتم اصلی:

  • یال‌های گراف اصلی را به این صورت بازوزن‌دهی کنید: $w(u,v) \gets w(u,v)+h(u)-h(v)$.
  • از الگوریتم دایکسترا برای یافتن زیرگراف کوتاه‌ترین مسیرهای شبکه اصلی استفاده کنید.
  • پتانسیل‌ها را برای تکرار بعدی به‌روز کنید.

با توجه به این توصیف، می‌توانیم مشاهده کنیم که یک تشابه قوی بین $h(v)$ و پتانسیل‌ها وجود دارد: می‌توان بررسی کرد که آنها تا یک مقدار ثابت با هم برابر هستند. علاوه بر این، می‌توان نشان داد که پس از بازوزن‌دهی، مجموعه تمام یال‌های با وزن صفر، زیرگراف کوتاه‌ترین مسیر را نشان می‌دهد که الگوریتم اصلی سعی می‌کند جریان را در آن افزایش دهد. این اتفاق در الگوریتم مجارستانی نیز رخ می‌دهد: ما یک زیرگراف از یال‌های سفت (rigid) می‌سازیم (آنهایی که مقدار $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$ را پیدا می‌کند که شرط مسئله را برآورده سازد. از سوی دیگر، بدون دانش الگوریتم مجارستانی، حل چنین مسئله‌ای تقریباً غیرممکن به نظر می‌رسد.

    نکته

    این وظیفه به عنوان مسئله دوگان مسئله تخصیص نیز نامیده می‌شود: کمینه کردن هزینه کل تخصیص معادل بیشینه کردن مجموع پتانسیل‌ها است.

ادبیات

مسائل تمرینی