پاورپوینت الگوریتم موازی prim

معرفی الگوریتم موازی prim

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

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

پاورپوینت الگوریتم موازی prim بیشتر با توضیحات عملی و مثال سعی دارد الگورتیم موازی را شرح دهد.

شرح الگوریتم

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

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

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

نکته: الگوریتم پریم را به این صورت نیزمی توان بیان کرد:ابتدا گره‌ای به دلخواه انتخاب شود و سپس از بین یالهای متصل به آن یالی که با کمترین وزن انتخاب می‌شود متصل شود به گونه‌ای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب می‌شود که حتماً یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس در الگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه شکل نگیرد.

از آنجا که در الگوریتم پریم در هر مرحله فاصله هر گره با گره‌های قبلی مقایسه می‌شود پس بدیهی است که از مرتبه (n2)Ѳ می‌باشد که n تعداد رئوس گراف است.

منبع متن الگورتیم موازی prim

تعدادی از اسلاید این پاورپوینت را در بخش گالری تصویر برایتان آپلود کردیم که میتوانید قبل از خرید مشاهده کنید.