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

{{Infobox algorithm|image=|data=[[گراف (ساختار داده)]]|time=<math>O(E \sqrt V)</math>|class=Graph algorithm|space=<math>O(V)</math>}}
'''الگوریتم هاپکرافت – کارپ ''' <ref>Hopcroft–Karp</ref> در [[علوم کامپیوتر]]، [[الگوریتم|الگوریتمی]] است که به عنوان ورودی یک [[گراف دوبخشی]] را گرفته و [[الگوریتم تطابق بیشینه در گراف دوبخشی|تطابق بیشینه‌ای]]<ref>Perfect Matching</ref> برای آن ارائه می‌دهد. تطابق بیشینه عبارت است از بیشترین تعداد یال‌های ممکن که هیچ دو راسی در نقطه پایانی مشترک نباشند. این کار در بدترین حالت از مرتبه زمانی (O(m√n امکانپذیر است که m تعداد یالها و n تعداد رئوس گراف هستند. در گراف‌های متراکم این زمان به O(n<sup>۵/۲</sup>) هم می‌رسد.{{سخ}}

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

OBD orz


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

== مسیرهای افزایشی ==
به راسی که نقطه پایانی یال قرار گرفته و در تطابق M نیست، راس آزاد و به یالی که در تطابق M قرار نگرفته، یال آزاد می‌گوییم. مفهوم بنیادین استفاده شده در این الگوریتم این است که یک مسیر افزایشی، مسیری است که از یک راس آزاد شروع می‌شود و به یک راس آزاد ختم می‌شود و به‌طور تناوبی شامل یک یال آزاد و یک یال غیر آزاد می‌باشد. اگر تطابق M دارای اندازه n باشد و P یک مسیر افزایشی بر مبنای M باشد [[تفاضل متقارن]] دو مجموعه یال M و P یک تطابق با سایز n+۱ می‌باشد. بنابراین پیدا کردن مسیر افزایشی می‌تواند سایز تطابق را افزایش دهد.{{سخ}}
همچنین فرض کنید تطابق M بهینه نباشد و P را تفاضل متقارن M و M<sup>*</sup> که M<sup>*</sup> تطابق بهینه‌است تصور کنید. بنابراین P باید شامل مجموعه‌ای از دورهای مجزا و مسیرهای افزایشی باشد. تفاوت اندازه M و M<sup>*</sup> تعداد مسیرهای موجود در P است. بنابراین اگر هیچ مسیر افزایشی پیدا نشود، الگوریتم به پایان می‌رسد پس M باید همان تطابق بهینه باشد.

== الگوریتم ==

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

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

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

[[پرونده:Hop-karp-code1.jpg|چپ]] 
{{-}}

== تحلیل الگوریتم هاپکرافت ==
هر مرحله شامل یک جستجوی سطح اول و یک جستجوی عمق اول است. پس هر مرحله می‌تواند در زمان خطی پیاده‌سازی شود. بنابراین 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 = G<sub>1</sub> <math>\cup</math> G<sub>2</sub> <math>\cup</math> {''NIL''}
  3   G1 و G2 دو بخش گراف و NIL یک راس منحصربه‌فرد null است.
  4 */
  5
  6 '''function''' BFS ()
  7     '''for''' ''v'' '''in''' G<sub>1</sub>
  8         '''if''' Pair[''v''] == ''NIL''
  9             Dist[''v''] = 0
 10             Enqueue(Q,''v'')
 11         '''else'''
 12             Dist[''v''] = <math>\infty</math>
 13     Dist[''NIL''] = <math>\infty</math>
 14     '''while''' Empty(Q) == false'''
 15         ''v'' = Dequeue(Q)
 16         '''for''' each ''u'' '''in''' Adj[v]
 17             '''if''' Dist[ Pair[u] ] == <math>\infty</math>
 18                 Dist[ Pair[u] ] = Dist[''v''] + 1
 29                 Enqueue(Q,Pair[u])
 20     '''return''' Dist[''NIL''] != <math>\infty</math>
 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''] = <math>\infty</math>
 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''' G<sub>1</sub>
 40             '''if''' Pair[''v''] == ''NIL''
 41                 '''if''' DFS(''v'') == true'''
 42                     matching = matching + 1
 44     '''return''' matching
{{پایان چپ‌چین}}
[[پرونده:HopcroftKarpExample.png|بندانگشتی|مثال الگوریتم هاپکرافت کارپ]]

== منابع ==
[//en.wikipedia.org/w/index.php?title=Hopcroft–Karp_algorithm&oldid=453910163 ویکی‌پدیا انگلیسی] 

== پی نوشت ==

{{پانویس}}

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