From Wikipedia, the free encyclopedia
الگوریتم هاپکرافت – کارپ [1] در علوم کامپیوتر، الگوریتمی است که به عنوان ورودی یک گراف دوبخشی را گرفته و تطابق بیشینهای[2] برای آن ارائه میدهد. تطابق بیشینه عبارت است از بیشترین تعداد یالهای ممکن که هیچ دو راسی در نقطه پایانی مشترک نباشند. این کار در بدترین حالت از مرتبه زمانی (O(m√n امکانپذیر است که m تعداد یالها و n تعداد رئوس گراف هستند. در گرافهای متراکم این زمان به O(n۵/۲) هم میرسد.
رده | Graph algorithm |
---|---|
ساختمان داده | گراف (ساختار داده) |
کارایی بدترین حالت | |
پیچیدگی فضایی |
این الگوریتم توسط جان هاپکرافت[3] و ریچارد کارپ[4] در سال ۱۹۷۳ ابداع شد. همانند روشهای قبلی تطابق بیشینه، مثل الگوریتم مجارستانی[5]، الگوریتم هاپکرافت – کارپ نیز سایز تطابق را بهطور متوالی با پیدا کردن مسیر افزایشی[6]، زیاد میکند. اگرچه به جای پیدا کردن یک مسیر افزایشی در هر مرحله، این الگوریتم بزرگترین مجموعه از کوتاهترین مسیرهای افزایشی را پیدا میکند. بنابراین تنها (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 نمایش میدهیم.
الگوریتم چند مرحلهاست که هر مرحله، خود شامل مراحل زیر میشود:
الگوریتم زمانی پایان میپذیرد که جستجوی سطح اول، هیچ مسیر افزایشی پیدا نکند.
هر مرحله شامل یک جستجوی سطح اول و یک جستجوی عمق اول است. پس هر مرحله میتواند در زمان خطی پیادهسازی شود. بنابراین 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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.