X
تبلیغات
رایتل

مقاله های علمی و تخصصی
 
مقاله دانشجویی ، شبکه های کامپیوتری ، شناسایی و حذف ویروس ، امنیت شبکه و سیستم عامل

الگوریتم پریم، الگوریتمی در نظریه گراف ها است که زیر درخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا می‌کند یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه رئوس را شامل می‌شود در حالیکه مجموع وزن همه آن یال‌ها کمینه شده‌است. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد وسپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته می‌شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.

الگوریتم پریم، الگوریتمی در نظریه گراف ها است که زیر درخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا می‌کند یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه رئوس را شامل می‌شود در حالیکه مجموع وزن همه آن یال‌ها کمینه شده‌است. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد وسپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته می‌شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.

شرح الگوریتم

این الگوریتم مرتبا سایز درخت را که از یک یال شروع شده‌است، افزایش می‌دهد تاجائی که همه رئوس وارد درخت شوند.

این الگوریتم را به طور خلاصه می‌توان چنین شرح داد:

  • ورودی: یک گراف همبند وزن دار با مجموعه رئوس V و یالهای E
  • مقدار دهی اولیه: {Vnew = {x که Vnew مجموعه رئوس درخت پوشای کمینه در حالت آغازین را نشان می‌دهد و x یک راس دلخواه است (نقطه شروع) و
    {} = Enew که Enew بیانگر مجموعه یالهای این درخت است.
  • حلقه زیر را تا وقتی که Vnew = V تکرار کن:
    • یال (u,v) را با وزن کمینه انتخاب کن به طوری که u در Vnew قرار داشته باشد ولی v عضوی از این مجموعه نباشد (اگر چند یال باوزن یکسان وجود دارند یکی را به دلخواه انتخاب کن)
    • راس v را به Vnew و یال (u , v) رابه Enew اضافه کن.
  • خروجی :Vnew و Enew درخت پوشای کمینه را توصیف می‌کنند.

هزینه زمانی

یک پیاده سازی ساده، استفاده از نمایش گراف به صورت ماتریس مجاورت است که درآن به دنبال آرایه‌ای از وزنها باشیم و یال‌های با وزن کمینه را به مجموعه خود بیفزائیم. این روش (O(V۲ زمان می‌برد. الگوریتم پریم بااستفاده از داده ساختار هیپ دودوئی ساده و نمایش فهرست مجاورت می‌تواند در زمان (O(E log V اجرا شود که در آن E تعداد یالها و V تعداد رئوس است. استفاده از مدل پیچیده تری به نام هیپ فیبوناچی باعث می‌شود این زمان تا حد (O(E + V log V کاهش یابد. سرعت این روش به خصوص زمانی آشکار می‌شود که در گراف رابطه (E = ω(V بین رئوس و یالها برقرار باشد.

مثال

شکلشرح
Prim Algorithm 0.svgاین شکل گراف وزن دار اصلی را نشان می‌دهد. اعداد کنارهر یال بیانگر وزن آن یال هستند.
Prim Algorithm 1.svgراس D به طور دلخواه به عنوان نقطه شروع انتخاب شده‌است. رئوس A، B، E، F همگی با یالی به D متصل هستند. A نزدیک ترین راس به D است بنابراین همراه با یال AD برای درخت انتخاب می‌گردد.
Prim Algorithm 2.svgراس بعدی که انتخاب می‌شود باید نزدیک ترین راس به A یاD باشد. فاصله B از D برابر ۹ و فاصله آن از A برابر ۷ است. فواصل E وF نیز به ترتیب ۱۵ و ۶ می‌باشد. راس F کمترین فاصله را دارد ینابراین این راس و کمان DF را انتخاب می‌کنیم.
Prim Algorithm 3.svgالگوریتم مشابه بالا ادامه می‌یابد و راس B که فاصله اش از A برابر ۷ است انتحاب می‌شود.
Prim Algorithm 4.svgدر این حالت انتخاب ما بین C، E، G می‌تواند صورت گیرد. فاصه C از B برابر ۸، فاصله E ازآن برابر ۷ و فاصله G از F نیز ۱۱ است. مشاهده می‌شود که E نزدیک ترین راس است پس آن را همراه با کمان BE انتخاب می‌کنیم.
Prim Algorithm 5.svgدر اینجا تنها رئوس C و G باقی مانده‌اند. فاصله C از E برابر ۵ و فاصله G از آن ۹ است پس C انتخاب می‌شود و کمان CE نیز همزمان با آن وارد درخت می‌گردد.
Prim Algorithm 6.svgتنها راس باقیمانده G است که چون فاصله اش از E کمتر از فاصله اش تا F می‌باشد، یال EG را انتخاب می‌کنیم.
Prim Algorithm 7.svgدر پایان همه رئوس انتخاب شده‌اند و درخت پوشای کمینه با رنگ سبز نشان داده شده‌است که وزنی برابر ۳۹ دارد.

منبع



نوشته شده در تاریخ دوشنبه 8 خرداد 1391 توسط قاسم عرفانی فر
 
تمامی حقوق این وبلاگ محفوظ است | طراحی : پیچک  

  • paper | قدس | قیمت ارز بازار آزاد