دانلودنما | فروشگاه فایل های آموزشی
پاورپوینت الگوریتم موازی prim
1- مقدمه
2- توضیح کامل الگوریتم prim
3- شکل
4- الگوريتم ترتيبي prim
5- الگوريتم موازي prim
6- فرمول ها
مقدمه
algorithm پریم، الگوریتمی در نظریه گراف ها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا می کند یعنی زیرمجموعه ای از یال ها را در آن گراف می یابد که درختی را تشکیل می دهند که همه رئوس را شامل می شود در حالیکه مجموع وزن همه آن یال ها کمینه شده است. این algorithm در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد و سپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. از این رو این algorithm گاهی با نام الگوریتم DJP نیز شناخته می شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است. این algorithm مرتب سازی درخت را که از یک یال شروع شده است، افزایش می دهد تا جایی که که همه رئوس وارد درخت شوند.
این الگوریتم را به طور خلاصه می توان چنین شرح داد:
ورودی: یک گراف همبند وزن دار با مجموعه رئوس V و یال های E
مقدار دهی اولیه: {Vnew = {x که Vnew مجموعه رئوس درخت پوشای کمینه در حالت آغازین را نشان می دهد و x یک راس دلخواه است (نقطه شروع) و
{} = Enew که Enew بیانگر مجموعه یال های این درخت است.
حلقه زیر را تا وقتی که Vnew = V تکرار کن:یال (u,v) را با وزن کمینه انتخاب کن به‌طوری‌که u در Vnew قرار داشته باشد ولی v عضوی از این مجموعه نباشد (اگر چند یال باوزن یکسان وجود دارند یکی را به دلخواه انتخاب کن)
راس v را به Vnew و یال (u , v) رابه Enew اضافه کن.
خروجی :Vnew و Enew درخت پوشا. کمینه را توصیف می‌کنند.
نکته: الگوریتم پریم را به این صورت نیزمی توان بیان کرد:
ابتدا گره‌ای به دلخواه انتخاب شود و سپس از بین یال های متصل به آن یالی با کمترین وزن انتخاب می شود به گونه ای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب می شود که حتماً یکی از دو سر آن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس در algorithm پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه شکل نگیرد. از آنجا که در الگوریتم پریم در هر مرحله فاصله هر گره با گره های قبلی مقایسه می شود پس بدیهی است که از مرتبه (n2(Ѳ می باشد که n تعداد رئوس گراف است.
چنانچه تمایل به مشاهده پاورپوینت های بیشتر دارید به سایت دانلودنما مراجعه فرمایید.
هیچ دیدگاهی برای این محصول نوشته نشده است.