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

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

الگوریتم پریم برای ساخت درخت پوشای کمینه از یک گراف به کار می رود . درخت پوشای کمینه ، زیر گرافی از یک گراف موزون است که شامل تمام رئوس گراف و برخی یال های آن می باشد به طوری که مجموع اوزان آن درخت نسبت به سایر درخت های ممکن حداقل شود .( می دانیم که معادل عدد کاتالان می توان می توان با N راس درخت ایجاد کرد . )

الگوریتم پریم در هر مرحله : یالی با کمترین وزن را انتخاب می کند به طوری که:

الف ) کم ترین وزن را میان سایر یال ها داشته باشد

ب) قبلا انتخاب نشده باشد

ج) با یال های انتخابی قبلی تشکیل دور ندهد ( زیرا در این صورت درخت نیست . ) . این الگوریتم در هر مرحله یک درخت ایجاد می کند .

سایر الگوریتم ها را می توانید در کتب طراحی الگوریتم بیابید .


 

نوشته شده توسط در چهارشنبه 1389/03/05 ساعت 5:54 بعد از ظهر موضوع | لينک ثابت