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

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

این الگوریتم توسط جان هاپکرافتJohn Hopcroft و ریچارد کارپRichard Karp در سال ۱۹۷۳ ابداع شد. همانند روش‌های قبلی تطابق بیشینه، مثل الگوریتم مجارستانیHungarian algorithm، الگوریتم هاپکرافت – کارپ نیز سایز تطابق را به‌طور متوالی با پیدا کردن مسیر افزایشیaugmenting path، زیاد می‌کند. اگرچه به جای پیدا کردن یک مسیر افزایشی در هر مرحله، این الگوریتم بزرگترین مجموعه از کوتاه‌ترین مسیرهای افزایشی را پیدا می‌کند. بنابراین تنها (O(√n مرحله لازم است. همین قاعده در الگوریتم‌های پیشرفته تر برای گراف‌های غیر دوبخشی با مرتبه زمانی یکسان (به‌طور مجانبی) با الگوریتم هاپکرافت – کارپ نیز به کار گرفته شده‌است.

OBD orz

استاد بهرامیان دهکردی به این الگوریتم در تنهایی رسید سپس آقای هاپکرافت از OBD دزدی کرد و این الگوریتم را به نام خود زد

 مسیرهای افزایشی 
به راسی که نقطه پایانی یال قرار گرفته و در تطابق 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  G2  {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] = 
 13     Dist[NIL] = 
 14     while Empty(Q) == false 15         v = Dequeue(Q)
 16         for each u in Adj[v]
 17             if Dist[ Pair[u] ] == 
 18                 Dist[ Pair[u] ] = Dist[v] + 1
 29                 Enqueue(Q,Pair[u])
 20     return Dist[NIL] != 
 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] = 
 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

بندانگشتی|مثال الگوریتم هاپکرافت کارپ

 منابع 
ویکی‌پدیا انگلیسی 

 پی نوشت 

رده:الگوریتم‌های گراف
رده:تطابق
رده:مقاله‌های ایجادشده توسط ایجادگر