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

1395/1/18 --- 3063

به نام خدا

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

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

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

قبل از اینکه الگوریتم کروسکال رو بگیم یک مثال میزنیم تا بهتر این الگوریتم رو درک کنیم .

فرض کنید میخوایم یک درخت پوشای کمینه از گراف زیر رو تعیین کنیم :

گراف

گرافی دارای 5 راس همراه با وزن یال ها

خب اول میایم یال ها رو برحسب وزن و به ترتیب غیر نزولی مرتب میکنیم .

یعنی :

1-(V1,V2)

2-(v3,v5)

3-(v1,v3)

4-(V2,V3)

5-(V3,V4)

6-(V4,V5)

7-(V2,V4)

 

خب حالا زیر مجموعه های مستقل ساخته میشن به شکل زیر :

گراف

حالا به همون ترتیبی که گفته شد و به شرط اینکه هر یال اعضای مجموعه های مستقل از هم رو به هم وصل کنه ، یال هارو انتخاب میکنیم و مجموعه هارو با هم ادغام میکنیم . یعنی به ترتیب یال های (V1,V2) و (V3,V5) و (V1,V3) و (V2,V3) و (V3,V4) انتخاب میشن و در نهایت درخت پوشای کمینه به شکل زیر به دست میاد :

گراف

تصویر زیر هم الگوریتم "کروسکال" را نشان می دهد :

الگوریتم کروسکال

پیچیدگی زمانی الگوریتم کروسکال در حالتی که گراف بسیار متراکم باشه از مرتبه ی تتای n log n هست و اگه گراف بسیار متصل باشه ، پیچیدگی از مرتبه ی تتای n2 log n هست ( n به توان 2 ضربدر log n ) . از طرفی الگوریتم پریم که در جلسه ی قبل درباره اش حرف زدیم دارای پیچیدگی زمانی از مرتبه ی n به توان 2 بود . بنابراین میتونیم الان یک مقایسه ی کوچک داشته باشیم . زمانی که گراف متراکم باشه بهتره از الگوریتم کروسکال و زمانی که گراف متصل باشه بهتره از الگوریتم پریم استفاده کنیم (برای تعیین درخت پوشای کمینه ).

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

 

این الگوریتم "دیکسترا" نام داره و یجورایی مشابه الگوریتم پریم هست . روش کار به این صورت هست که در ابتدا برای مقدار دهی اولیه به مجموعه ای مثل Y راسی رو در اون قرار میدیم مثل V1 که کوتاه ترین مسیر های اون باید تعیین بشن . به مجموعه ای مثل F هم ابتدا یک مقدار تهی میدیم . حالا راسی رو انتخاب میکنیم که از همه به V1 نزدیک تر هست . همون رو به Y اضافه میکنیم و عبارت <V1,V>رو به F اضافه میکنیم که همون یالی هست که دو راس رو بهم وصل میکنه . این یال در واقع کوتاه ترین مسیر از راس V1 به V هست . حالا مسیر هایی از V1 به رئوس موجود در V-Y رو بررسی میکنیم رئوس Y رو به عنوان رئوس واسطه به حساب میارن . بازهم مثل قسمت قبلی کوتاه ترین مسیر رو انتخاب میکنیم و تغییرات لازم رو اعمال میکنیم . این روند رو اینقدر ادامه میدیم تا هدف این الگوریتم که پیدا کردن کوتاه ترین مسیر هست برسیم . شکل زیر الگوریتم دیکسترا رو نشون میده :

الگوریتم دیکسترا

الگوریتم دیکسترا

این توضیح رو هم باید بدم که دو عبارت length]i] و touch]i] چی هستن .

Length]i]

طول کوتاه ترین مسیر فعلی از V1 به Vi فقط با استفاده از رئوس موجود در Y.

Touch]i]

اندیس راس V در Y به طوری که یال <V,Vi> آخرین یال روی کوتاه ترین مسیر فعلی از V1 به Vi ، فقط با استفاده از رئوس موجود در Y به عنوان واسطه باشه .

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

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

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

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

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

با تشکر از توجه شما تا جلسه ی بعد خدا یار و نگهدار شما .