توضیحات محصول

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

۱- مقدمه

۲- توضیح کامل الگوریتم prim

۳- شکل

۴- الگوریتم ترتیبی prim  

۵- الگوریتم موازی prim

۶- فرمول ها

مقدمه

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 تعداد رئوس گراف است.


برچسب ها:

,
قابل ویرایشمی باشد
قابل پرینتمی باشد
حجم فایل1.22 مگابایت
رفرنسندارد
محتوای فایل دانلودیZip
زبانفارسی
فرمت فایلپاورپوینت
تعداد صفحات14 اسلاید
جزئیات محصولاین محصول شامل یک فایل پاورپوینت (Power Point) و نیز یک فایل پی دی اف (PDF) آن می‌ باشد.

    شما باید وارد شوید و یک خریدار محصول باشید تا بتوانید نظر خود را ثبت کنید.

    For security, use of Google's reCAPTCHA service is required which is subject to the Google Privacy Policy and Terms of Use.

    If you agree to these terms, please click here.

    نظری بدهید

    For security, use of Google's reCAPTCHA service is required which is subject to the Google Privacy Policy and Terms of Use.

    If you agree to these terms, please click here.