الگوریتم هاپکرافت-کارپ

الگوریتم هاپکرافت – کارپ [1] در علوم کامپیوتر، الگوریتمی است که به عنوان ورودی یک گراف دوبخشی را گرفته و تطابق بیشینه‌ای[2] برای آن ارائه می‌دهد. تطابق بیشینه عبارت است از بیشترین تعداد یال‌های ممکن که هیچ دو راسی در نقطه پایانی مشترک نباشند. این کار در بدترین حالت از مرتبه زمانی (O(m√n امکانپذیر است که m تعداد یالها و n تعداد رئوس گراف هستند. در گراف‌های متراکم این زمان به O(n^۵/۲) هم می‌رسد.

الگوریتم هاپکرافت-کارپ

رده	Graph algorithm
ساختمان داده	گراف (ساختار داده)
کارایی بدترین حالت	${\displaystyle O(E{\sqrt {V}})}$
پیچیدگی فضایی	${\displaystyle O(V)}$

این الگوریتم توسط جان هاپکرافت[3] و ریچارد کارپ[4] در سال ۱۹۷۳ ابداع شد. همانند روش‌های قبلی تطابق بیشینه، مثل الگوریتم مجارستانی[5]، الگوریتم هاپکرافت – کارپ نیز سایز تطابق را به‌طور متوالی با پیدا کردن مسیر افزایشی[6]، زیاد می‌کند. اگرچه به جای پیدا کردن یک مسیر افزایشی در هر مرحله، این الگوریتم بزرگترین مجموعه از کوتاه‌ترین مسیرهای افزایشی را پیدا می‌کند. بنابراین تنها (O(√n مرحله لازم است. همین قاعده در الگوریتم‌های پیشرفته تر برای گراف‌های غیر دوبخشی با مرتبه زمانی یکسان (به‌طور مجانبی) با الگوریتم هاپکرافت – کارپ نیز به کار گرفته شده‌است.

مسیرهای افزایشی

به راسی که نقطه پایانی یال قرار گرفته و در تطابق M نیست، راس آزاد و به یالی که در تطابق M قرار نگرفته، یال آزاد می‌گوییم. مفهوم بنیادین استفاده شده در این الگوریتم این است که یک مسیر افزایشی، مسیری است که از یک راس آزاد شروع می‌شود و به یک راس آزاد ختم می‌شود و به‌طور تناوبی شامل یک یال آزاد و یک یال غیر آزاد می‌باشد. اگر تطابق M دارای اندازه n باشد و P یک مسیر افزایشی بر مبنای M باشد تفاضل متقارن دو مجموعه یال M و P یک تطابق با سایز n+۱ می‌باشد. بنابراین پیدا کردن مسیر افزایشی می‌تواند سایز تطابق را افزایش دهد.
همچنین فرض کنید تطابق M بهینه نباشد و P را تفاضل متقارن M و M^* که M^* تطابق بهینه‌است تصور کنید. بنابراین P باید شامل مجموعه‌ای از دورهای مجزا و مسیرهای افزایشی باشد. تفاوت اندازه M و M^* تعداد مسیرهای موجود در P است. بنابراین اگر هیچ مسیر افزایشی پیدا نشود، الگوریتم به پایان می‌رسد پس M باید همان تطابق بهینه باشد.

الگوریتم

U و V دو مجموعه راس در گراف دوبخشی G هستند و در هر مرحله تطابق U به V را با M نمایش می‌دهیم.

الگوریتم چند مرحله‌است که هر مرحله، خود شامل مراحل زیر می‌شود:

• یک جستجوی سطح اول رئوس گراف را به چند لایه تقسیم می‌کند. رئوس آزاد واقع در U به عنوان رئوس آغازین این جستجو انتخاب می‌شوند. در اولین لایه جستجو، تنها یالهای آزاد طی می‌شوند. در مراحل بعدی جستجو، یالهای طی شده به‌طور تناوبی شامل یالهای آزاد و غیرآزاد هستند. به عبارتی با شروع از هر راس در U یال آزاد طی می‌شود در حالیکه با شروع از هر راس در V یال غیرآزاد طی می‌شود. جستجو در k مرحله اول با رسیدن به یک راس آزاد در V یا بیشتر به پایان می‌رسد.
• همه رئوس آزاد واقع در V در مرحله kام در مجموعه F قرار داده می‌شوند. بنابراین هر راس v در مجموعه F قرار می‌گیرد اگر و تنها اگر نقطه پایانی یک مسیر افزایشی باشد.
• هر کدام از مسیرهای پیدا شده برای افزایش سایز M استفاده می‌شوند.
• الگوریتم، مجموعه بیشترین رئوس مسیرهای افزایشی به طول k را پیدا می‌کند. این مجموعه توسط جستجوی عمق اول از F به مجموعه رئوس آزاد U که در لایه قبلی توسط جستجوی سطح اول تعیین شده‌اند، پیدا می‌شود. پس از اینکه مسیر افزایشی متوجه شد شامل راسی از F است، این جستجو از راس بعدی شروع به کار می‌کند.
  

الگوریتم زمانی پایان می‌پذیرد که جستجوی سطح اول، هیچ مسیر افزایشی پیدا نکند.

تحلیل الگوریتم هاپکرافت

هر مرحله شامل یک جستجوی سطح اول و یک جستجوی عمق اول است. پس هر مرحله می‌تواند در زمان خطی پیاده‌سازی شود. بنابراین n√ مرحله اول در گرافی با n راس و m یال (O(m√n زمان می‌برد.
می‌توان نشان داد که هر مرحله، حداقل یک واحد طول کوتاه‌ترین مسیر افزایشی را زیاد می‌کند: در هر مرحله بزرگترین مجموعه شامل کوتاه‌ترین مسیرهای افزایشی پیدا می‌شود پس مسیرهای باقی‌مانده باید بلندتر باشند. بنابراین پس از به پایان رسیدن n√ مرحله، کوتاه‌ترین مسیر افزایشی حداقل شامل n√ یال است.
تفاضل متقارن تطابق بهینه نهایی و تطابق M ایجاد شده در هر مرحله، مجموعه از رئوس مسیرهای افزایشی و دورهای متناوب را تشکیل می‌دهند. اگر هر مسیر این مجموعه دارای حداقل طول n√ باشد، حداکثر n√ مسیر در این مجموعه وجود دارد. و اندازه تطابق نهایی می‌تواند حداکثر n√ یال از تطابق M بیشتر باشد. هر مرحله از الگوریتم اندازه تطابق را حداقل یک واحد افزایش می‌دهد و پیش از به پایان رسیدن الگوریتم حداکثر n√ مرحله افزایشی وجود دارد.
الگوریتم حداکثر شامل n√2 مرحله‌است و در بدترین حالت از مرتبه زمانی (O(m√n می‌باشد.

گراف‌های غیر دوبخشی

ایده پیدا کردن مجموعه‌ای شامل بیشترین تعداد از کوتاه‌ترین مسیرهای افزایشی برای پیدا کردن تطابق بیشینه در گراف‌های غیر دوبخشی نیز به کار می‌رود. و با همان استدلال این الگوریتم شامل (O(√n مرحله می‌باشد. اگرچه برای یک گراف غیر دوبخشی، پیدا کردن مسیر افزایشی در هر مرحله دشوارتر است. Micali و Vazirani در سال 1980 نشان دادند چگونه هر یک از (O(√n مرحله را می‌توان در زمان خطی انجام داد. بنابراین این الگوریتم مرتبه زمانی مشابهی با الگوریتم هاپکرافت – کارپ دارد.

شبه کد

1 /*
 2   G = G1 ${\displaystyle \cup }$ G2 ${\displaystyle \cup }$ {NIL}
 3   G1 و G2 دو بخش گراف و NIL یک راس منحصربه‌فرد null است.
 4 */
 5
 6 function BFS ()
 7     for v in G1
 8         if Pair[v] == NIL
 9             Dist[v] = 0
10             Enqueue(Q,v)
11         else
12             Dist[v] = ${\displaystyle \infty }$
13     Dist[NIL] = ${\displaystyle \infty }$
14     while Empty(Q) == false
15         v = Dequeue(Q)
16         for each u in Adj[v]
17             if Dist[ Pair[u] ] == ${\displaystyle \infty }$
18                 Dist[ Pair[u] ] = Dist[v] + 1
29                 Enqueue(Q,Pair[u])
20     return Dist[NIL] != ${\displaystyle \infty }$
21
22 function DFS (v)
23     if v != NIL
24         for each u in Adj[v]
25             if Dist[ Pair[u] ] == Dist[v] + 1
26                 if DFS(Pair[u]) == true
27                     Pair[u] = v
28                     Pair[v] = u
39                     return true
30         Dist[v] = ${\displaystyle \infty }$
31         return false
32     return true
33
34 function Hopcroft-Karp
35     for each v in G
36         Pair[v] = NIL
37     matching = 0
38     while BFS() == true
49         for each v in G1
40             if Pair[v] == NIL
41                 if DFS(v) == true
42                     matching = matching + 1
44     return matching

منابع

ویکی‌پدیا انگلیسی

پی نوشت

1. Hopcroft–Karp
2. Perfect Matching
3. John Hopcroft
4. Richard Karp
5. Hungarian algorithm
6. augmenting path