الگوریتم پریم

الگوریتم پریم

الگوریتم پریم، پیدا کردن درخت فراگیر مینیمال

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

شرح الگوریتم

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

می یابد  که کلیه گره ها به درخت افزوده شود.

در ابتدا مجموعه B  شامل یک گره، که همان گره دلخواه آغاز است، خواهد بود و مجموعه T خالی فرض خواهد شد. در هر لحظه محموعه B  مجموه گره های انتخاب شده و مجموعه T  مجموعه لبه های انتخاب شده خواهد بود.

برای پیاده سازی الگوریتم فرض می کنیم گراف  G=(V,E)  به وسیله ماتریس ارزشها نمایش داده شده باشد.  به گراف ارزشگذاری شده شکل ۳-۵  ماتریس  ارزشهای این گراف نشان داده شده است. در ماتریس ارزشها، ارزش ارتباطی یک گره به خودش برابر و ارزش ارتباطی دو گره که بین آنها لبه ای وجود نداشته ندارد نیز  فرض شده است.

در الگوریتم gprim  که بعداً آمده است ماتریس  cost  ماتریس ارزشها است. گرافG  با n  گره در نظر گرفته شده  است. فرض کدره ایم گره ها از صفر تا n-1  شماره گذاری شده اند و هر گره را با شماره آن خواهیم شناخت.

 T  یک آرایه دو بعدی است که دارای n-1 ردیف و دو ستون است. هر ردیف T  یک لبه را مشخص می کند، هر لبه با گره مبدا و گره انتهای آن مشخص می گردد.B  مجموعه گره های انتخاب شده است که توسط یک آرایه یک بعدی نمایش داده شده است. چنانچه گره شماره i   در مجموعه B باشد B[i]=1  و در غیر این صورت ۰B[i]= خواهد بود. به الگوریتم gprim دقت کنید. بقیه توضیحات بعداً بیان خواهد شد. 

 

گره انتخاب نشده i  در  نظر بگیرید.  این گره  ممکن است به  وسیله لبه های متفاوتی با گره هایی  از  مجموعه B  تماس برقرار نماید.  ارزش  همه این لبه ها  یکسان نیست و یکی ( یا بیشتر)  از این  لبه ها کمترین  ارزش را  دارد.  گرهی از B  که این لبه بدان  وصل  شده  می گردد.  نزدیکترین  همسایه i   در  مجموعه  B است.  اگر i  یک گره انتخاب شده باشد در مکان  near[i]  عدد منفی  یک گذاشته  شده  است.  برای یافتن لبه ای با کمترین ارزش که تماس مجموعه گره های انتخاب  نشده  را  با  مجموعه  گره های  ارزش  ( با به کارگیری مفهوم نزدیکترین همسایه)  که تماس آن ر ا  با  مجموعه B برقرارکند،  پیدا می کنیم و ارزش این ارتباط را در آرایه یک بعدی mindist می گذاریم  و سپس در آرایه  mindist کمترین مقدار از بین مقادیر متناظر با گره های انتخاب نشده را پیدا می کنیم. بنابراین mindist[i]  ارزش ارتباطی گره انتخاب نشده I را با نزدیکترین همسایه اش در B مشخص می کند.

در الگوریتم   gprim ابتدا  مجموعه B  تهی می گردد  و  سپس گره  شماره  صفر به آن  افزوده  می شود.  با توضیحات قبلی باید near[0]=-1 گردد که این کار عملی می شود.

متغیر mincost ارزش ارتباطی درخت پوشای نهای را بما خواهد داد. مقدار این متغیر ابتدا صفر است و به تدریج که لبه ای به T افزوده می شود ارزش آن به mincost  اضافه خواهد شد. گره صفر نزدیکترین همسایه  ندارد.

 بنابراین mindist[0]=  منظور شده  که در عمل به جای  از MAXFLOAT استفاده شده است.نظر به اینکه در ابتدا تنها گره شماره صفر در مجموعه B قرارداده شده، نزدیکترین همسایه گره های انتخاب نشده همه گره ها گره صفر خواهد  بود  حتی اگر گره های پ لبه مشترکی با گره صفر نداشته  باشند می توانیم فرض کنیم که لبه مشترکی  با ارزش وجود دارد.اولین گرهی که با B  افزوده می شود کاملاً  دلخواه  است  و همان طور که گفته شد ما در این الگوریتم گره صفر را به این منظور انتخاب کرده ایم.بعد از  اقدامات اولیه ،مراحل اصلی الگوریتم آغاز می گردد .

در هر مرحله ابتدا مینیمم مقدار از بین مقادیر متناظر با گره های انتخاب شده در آرایه mindistپیدا می شود و ردیفی که این مقدار را دارد مشخص میگردد. این کار در زیر روال minedge انجام شده  وردیف مربوطه بر می گردد .

این ردیف،j ، شماره گره انتخاب نشده ای است که یتواند در این مرحله به وسیله لبه j , near[j]>>با B ارتباط برقرار کند .سپس این لبه به T  افزوده می گردد،  و B[j]،mindist[j]  وارزش لبه به mincost افزوده می شود.

آنچه در انتهای هر مرحله انجام می شود از اهمیت بسزایی برخوردار است .چون گره j به گره B  افزوده می گردد ممکن است برروی نزدیک ترین همسایه گره های انتخاب نشده اثر بگذارد و خود نزدیکترین همسایه برخی از گره ها بشود.اگر گره انتخاب نشده k  را داشته باشیم که فاصله اش با نزدیک ترین همسایه اش بیشتر از فاصله اش با j  باشد همسایه k  را باید تغییر دهیم .

با منظور کردن O(n) برای مرتبه زمانی minedge   مرتبه زمانی الگوریتم gprim برابر O(n) محاسبه می گردد .نکته ای که قابل بیان است این که ، می توان با کمی تغییر کارایی الگوریتم را اندکی بالا برد ، برای مثال آرایه B  را حذف و به جای آن از near  استفاده کرد .اما  این تغییرات بر  مرتبه زمانی الگوریتم اثری ندارد . باتوجه به پیچیده  بودن الگوریتم سعی بر تدوین ساده آن شده  است . از آن گذشته به عنوان یک اصل ،  اعتقاد ما بر این است  که از  این  متغیر تا  وقتی فعال است، تنها به یک منظور استفاده می شود . پیشنهاد  بالا  برای near   دو منظور مطرح می کند ، اول نزدیک ترین همسایه و دوم انتخاب شده بودن یا نبودن گره ها .

در این جا یک مثال می تواند به درک مطالب گفته شده کمک کند.

 

 

 

مثال ۱-۵:درخت پوشای گراف مرتبط بودن جهت شکل ۴-۵را به دست آورید.

 

 

 

 

 

                             

                                                        شکل ۴-۵:یگ گراف مرتبط بدون جهت

 

با توجه به الگوریتم gprim  ، عملیات مقدماتی الگوریتم در جدول شکل۵-۵الف خلاصه شده است .در این جدول M به مفهوم بزرگترین عدد اعشاری ویا همان فرض شده

 

 

 

 

 

 

                                                            شکل ۵-۵الف

مرحله اول عملیات در جدول شکل ۵-۵ ب خلاصه شده و حاصل با شکل نشان داده شده است.

 

 

                                                                         شکل۵-۵ب

 

مراحل دوم  تا پنجم نیز متشابها انجام ونتایج در شکل های ۵-۵پ تا ج آمده است .

 

 

 

 

 

                                             

                                                       شکل ۵-۵پ

 

 

 

 

                            

                                                         شکل ۵-۵ت

 

هزینه زمانی

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

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

مثال ۱

شکل

شرح

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

راس D به طور دلخواه به عنوان نقطه شروع انتخاب شده‌است. رئوس A، B، E، F همگی با یالی به D متصل هستند. A نزدیک ترین راس به D است بنابراین همراه با یال AD برای درخت انتخاب می‌گردد.

راس بعدی که انتخاب می‌شود باید نزدیک ترین راس به A یاD باشد. فاصله B از D برابر ۹ و فاصله آن از A برابر ۷ است. فواصل E وF نیز به ترتیب ۱۵ و ۶ می‌باشد. راس F کمترین فاصله را دارد ینابراین این راس و کمان DF را انتخاب می‌کنیم.

الگوریتم مشابه بالا ادامه می‌یابد و راس B که فاصله اش از A برابر ۷ است انتحاب می‌شود.

در این حالت انتخاب ما بین C، E، G می‌تواند صورت گیرد. فاصه C از B برابر ۸، فاصله E ازآن برابر ۷ و فاصله G از F نیز ۱۱ است. مشاهده می‌شود که E نزدیک ترین راس است پس آن را همراه با کمان BE انتخاب می‌کنیم.

در اینجا تنها رئوس C و G باقی مانده‌اند. فاصله C از E برابر ۵ و فاصله G از آن ۹ است پس C انتخاب می‌شود و کمان CE نیز همزمان با آن وارد درخت می‌گردد.

تنها راس باقیمانده G است که چون فاصله اش از E کمتر از فاصله اش تا F می‌باشد، یال EG را انتخاب می‌کنیم.

در پایان همه رئوس انتخاب شده‌اند و درخت پوشای کمینه با رنگ سبز نشان داده شده‌است که وزنی برابر ۳۹ دارد.

 مثال ۲

۱۳۹۴-۹-۲۳ ۱۸:۱۴:۱۰ +۰۳:۳۰آبان ۵ام, ۱۳۹۲|Categories: matlab, آموزش متلب, عمومی, متلب, مهندسی نرم افزار, هوش مصنوعی|۰ Comments

Leave A Comment

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی