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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

این الگوریتم توسط جان هاپکرافت[۳] و ریچارد کارپ[۴] در سال ۱۹۷۳ ابداع شد. همانند روش های قبلی تطابق بیشینه، مثل الگوریتم مجارستانی[۵]، الگوریتم هاپکرافت – کارپ نیز سایز تطابق را به طور متوالی با پیدا کردن مسیر افزایشی[۶]، زیاد می‌کند. اگرچه به جای پیدا کردن یک مسیر افزایشی در هر مرحله، این الگوریتم بزرگترین مجموعه از کوتاه ترین مسیرهای افزایشی را پیدا می‌کند. بنابراین تنها (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 است، این جستجو از راس بعدی شروع به کار می‌کند.

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

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 = G1 \cup G2 \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] = \infty
13     Dist[NIL] = \infty
14     while Empty(Q) == false
15         v = Dequeue(Q)
16         for each u in Adj[v]
17             if Dist[ Pair[u] ] == \infty
18                 Dist[ Pair[u] ] = Dist[v] + 1
29                 Enqueue(Q,Pair[u])
20     return Dist[NIL] != \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] = \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