آموزش طراحی و تحلیل الگوریتم قسمت ششم

1395/1/18 --- 1677

به نام خدا

سلام عرض میکنم خدمت همه ی شما دوستان عزیز

ضیادید هستم و با جلسه ی ششم از آموزش طراحی و تحلیل الگوریتم ها در خدمت شما خواهم بود.

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

ببینید دوستان ، الگوریتم های حریصانه یا طمعکار ، بیشتر برای حل مسئله های بهینه سازی استفاده میشن . روش این الگوریتم ها هم به این صورت هست که میان در هر مرحله "بهترین " انتخاب رو با توجه به ملاک ها و معیار های مسئله انجام میدن . البته باید بدونید که همیشه مفاهیم "بهینه" و "بهترین" با هم برابر نیستن . در این نوع الگوریتم ها در مرحله بهترین جواب ها انتخاب میشن و اگر بشه ثابت کرد این جواب هایی که بهترین هستن ، بهینه هم هستن ، پس میتونیم این ادعا رو هم بکنیم که اصل بهینگی در این الگوریتم ها برقرار است . ما گفتیم الگوریتم های طمعکار در حل مسائل بهینه سازی به کار میرن . پس از این نظر میشه گفت شبیه برنامه ریزی پویا هستن.. اما الگوریتم های طمعکار برخلاف الگوریتم های برنامه ریزی پویا و روش تقسیم و حل ، مسئله  رو به نمونه های کوچکتر تقسیم نمی کنند .بلکه در هر مرحله با توجه معیار های مسئله ،بهترین انتخاب انجام میشه و این انتخاب مستقل از سایر مراحل هست .

بیاید یک مثال رو بررسی کنیم با هم :

فرض کنید میخوایم 16000 تومن به یک نفر پول بدیم و بسته های پولی هم که در اختیار داریم ، بسته های 1000 تومانی ، 5000، 10000، 12000 تومانی هستن . همچنین هدف مسئله ، پرداخت پول با صرف کمترین بسته اسکناس هست . خب اگر بر اساس الگوریتم حریصانه پیش بریم ، در مرحله ی اول بهترین انتخاب ، بسته ی 12000 تومانی هست ، چون میخواد کمترین بسته هدر بره و این مستقل از سایر مراحل هست پس نزدیکترین بسته به کل مبلغ انتخاب میشه . در مرحله ی بعد هر بسته ی دیگه ای رو  انتخاب کنیم ، از مبلغ کل بزرگتر میشه به جز بسته ی 1000 تومانی . پس قطعا باید 4 بسته ی 1000 تومانی انتخاب کنیم . یعنی جمعا 5 بسته پرداخت شد . الان میتونیم بگیم در هر مرحله بهترین انتخاب ممکن صورت گرفت . ولی مطمئنا متوجه شدید که این انتخاب بهینه نیست . ما میتونیم با انتخاب 3 بسته ی 10000، 5000 و 1000 تومانی به جواب بهینه تری برسیم . پس لزوما جواب یک الگوریتم حریصانه ، بهینه نیست !

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

 

روال انتخاب : این مرحله ، عناصر بعدی مجموعه ی جواب رو بر اساس یک معیار حریصانه انتخاب می کنه

بررسی امکان سنجی ( تحقیق علمی بودن ): این مرحله ، مشخص کننده ی این هست که آیا مجموعه ی به دست آمده ، برای رسیدن به حل نمونه ی مسئله عملی هست یا نه .

بررسی حل : این مرحله هم مشخص میکنه که آیا مجموعه ی به دست آمده ، مسئله رو حل کرده یا نه.

یبار دیگه بریم سراغ همون مثال قبلی که مربوط به پول میشد . میخوایم اینبار یک الگوریتم رو برای این مثال بنویسیم تا متوجه ی مراحلی که گفتیم بشیم :

1-تا زمانی که بسته های بیشتری وجود داره و مسئله حل نشده است

2-بزرگترین بسته ی باقیمانده را بگیر

3-اگر با اضافه کردن آن ، مبلغ کل بیشتر از مبلغ مسئله می شود

4-بسته را رد کن

5-در غیر این صورت

6-بسته را اضافه کن

7-اگر کل مقدار ، برابر با مبلغ مسئله شد

8-مسئله حل شده است

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

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

همونطور که میدونید گراف بدون جهت G رو با زوج مرتب (V,E) نشون میدن که V مجموعه ی رئوس گراف و E مجموعه ی یال های گراف هستن .

گراف

گرافی که دور نداشته باشه رو یک درخت میگن . حالا درخت پوشا چیه ؟ یک درخت پوشا ، درختی هست که متصل و حاوی همه ی رئوس گراف اصلی باشه . مثلا اگه گراف G رو داشته باشیم ، زیر گرافی از اون که درخت باشه و حاوی تمام رئوس اون هم باشه رو درخت پوشا ی گراف G مینامیم . اگر گراف G وزن دار باشه و درخت پوشا رو بتونیم طوری انتخاب کنیم که کمترین وزن ها شامل بشه ، آنگاه درخت پوشای کمینه رو خواهیم داشت .

 

خب حالا میخوایم الگوریتم هایی معرفی کنیم که با روش حریصانه میان و درخت پوشای کمینه رو ایجاد میکنن .. اول بریم سراغ الگوریتم پریم :

الگوریتم پریم با زیر مجموعه ای تهی از یال های F و زیر مجموعه ای از رئوس Y که در ابتدا حاوی یک راس دلخواه است ، شروع میشه . فرض کنید این راس دلخواه مثلا v1 باشه . راسی که توسط یک یال با کمترین وزن به v1 متصل شده رو به عنوان نزدیک ترین راس به v1 در نظر میگیریم . این راس به مجموعه ی Y و یالش به  F اضافه میشه . این فرایند باید تا زمانی که V و Y با هم برابر بشن ادامه داشته باشه . یعنی پوشا بودن تامین بشه . اما برای اینکه یک الگوریتم قابل استفاده برای برنامه نویسی ارائه کنیم باید یک فرایند قدم به قدم رو در پیش بگیریم . میایم گراف وزن دار رو توسط یک آرایه ی دو بعدی نشون میدیم (یعنی ماتریس)

درایه های این ماتریس رو هم اینطور تعریف میکنیم که اگر بین راس iام و jام یک یال باشه ، وزن اون یال رو به عنوان درایه انتخاب میکنیم و اگر یالی وجود نداشته باشه ، درایه رو بی نهایت قرار میدیم . اگر i=j باشه هم درایه 0 میشه .

دو آرایه ی D و N رو هم به صورت زیر تعریف میکنیم :

اندیس نزدیک ترین راس در Y به vi رو در Ni قرار میدیم و

وزن یال میان vi و راسی که توسط N[i] مشخص شده است رو در Di قرار میدیم .

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

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

پیچیدگی الگوریتم پریم هم از مرتبه ی تتای n به توان دو هست .

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

به امید دیدار و خدانگهدارتان