آموزش طراحی و تحلیل الگوریتم قسمت دهم
به نام خدا
سلام عرض می کنم خدمت همه ی شما دوستان عزیز و ارجمند.
ضیادید هستم و با قسمت دهم از سری آموزش های طراحی و تحلیل الگوریتم ها در خدمت شما خواهم بود.
در این جلسه قصد داریم کاربرد الگوریتم مونت کارلو در الگوریتم عقبگرد مسئله ی n وزیر رو بگیم . بعدش دو مسئله ی مدار های هامیلتونی و رنگ آمیزی گراف رو بررسی می کنیم . در آخر هم یک سری مطالب درباره ی راهبرد عقبگرد و برنامه ریزی پویا مطرح میکنیم .
خب دوستان برای یادآوری ، تخمین مونت کارلو رو نشون میدیم که در جلسه ی قبلی مورد بررسی قرار گرفت :
در تصویر زیر هم براورد مونت کارلو برای الگوریتم عقبگرد برای مسئله ی n وزیر رو میبینید:
البته برای استفاده ی بهتر ، باید این برآورد رو چند بار تکرار کنیم و بعدش میانگین نتایج رو به عنوان برآورد واقعی در نظر بگیریم . با استفاده از برخی روش های استاندارد آماری میشه یک بازه ی اطمینان برای تعداد واقعی گره های چک شده از روی نتایج آزمون ها به دست بیاریم . معمولا 20 تا 25 بار آزمون کافیه . برآورد حاصل از به کارگیری روش مونت کارلو الزاما نشانگر تعداد گره هایی نیست که پیش از یافتن نخستین حل چک میشن . برای پیدا کردن تنها یک حل ، ممکنه که الگوریتم ما کسر کوچکی از گره هایی رو چک کنه که برای پیدا کردن همه ی حل ها قبلا چک میکرد .
خب دوستان بریم سراغ مسئله ی مدار های هامیلتونی . یک مدار هامیلتونی چیه؟ یک گراف متصل و غیر جهت دار رو درنظر بگیرید . یک مسیر در چنین گرافی که از یک راس شروع بشه ، تمام رئوس گراف رو دقیقا یکبار ملاقات کنه و در راس شروع به پایان برسه . این مسیر رو یک مدار هامیلتونی یا یک تور میگن . هدف مسئله ی نام برده شده هم تعیین کردن مدار های هامیلتونی در یک گراف متصل و بدون جهت هست .
از اونجایی که در مبحث راهبرد عقبگرد هستیم ، مشخصا باید چنین الگوریتمی رو برای حل این مسئله بیان کنیم . پس باید درخت فضای حالت رو بررسی کنیم . درخت فضای حالت این مسئله به این صورت هست که راس شروع در سطح صفر از درخت قرار داره و اسمش رو هم میذاریم راس صفرم (در مسیر) . در سطح 1 ، همه ی رئوس غیر از راس شروع رو به عنوان نخستین راس پس از شروع در نظر میگیریم . در سطح 2 ، هر یک از همین رئوس رو به عنوان راس دوم در نظر میگیریم و همینجوری تا آخر ادامه میدیم . آخر سر هم در سطح n-1 ام هر یک از رئوس رو به عنوان راس n-1 ام در نظر میگیریم . حالا میتونیم در چنین درخت فضای حالتی از راهبرد عقبگرد استفاده کنیم . البته با شرایط زیر :
1-راس i ام از مسیر باید مجاور به راس n-1ام از مسیر باشه.
2-راس n-1 ام باید مجاور به راس صفرم (راس شروع) باشه .
3-راس i ام نمیتونه یکی از i-1 راس باشه .
در زیر هم الگوریتمی رو ملاحظه میکنیم که از همین شرایط استفاده میکنه (راس شروع v1هست )
حالا مسئله ی رنگ آمیزی گراف رو خواهیم داشت . این مسئله بیشتر مربوط به مباحث گراف هست و برای اینکه دقیقا با این مسئله آشنا بشید بهتره به منابع مفید برای این مبحث مراجعه کنید . اما اگه بخوام به طور خلاصه خدمت شما عرض کنم ، مسئله ی m-coloring (رنگ آمیزی – ام) این هدف رو داره که ما همه ی راه های ممکن برای رنگ آمیزی یک گراف بدون جهت رو با استفاده از حداکثرm رنگ متفاوت پیدا کنیم به طوری که هیچ دو راس مجاوری دارای رنگ های یکسان نباشند . حالا اگه بخوایم یک درخت فضای حالت رو برای این مسئله در نظر بگیریم ، درختی رو ایجاد می کنیم که در اون هر رنگ ممکن برای راس v1 در سطح 1 امتحان بشه ، هر رنگ ممکن برای راس v2 در سطح 2 امتحان بشه و همینطور تا آخر و در آخر هر رنگ ممکن برای راس vn در سطح n امتحان بشه . هر مسیر هم از ریشه به برگ یک راه حل کاندید خواهد بود . گره ی غیر امید بخش هم گره ای هست که یک راس مجاور به راسی که در گره رنگ آمیزی میشه ، قبلا با همون رنگ ، رنگ آمیزی شده باشه . در زیر الگوریتمی هست این مسئله رو برای مقادیر دلخواه حل میکنه . در این الگوریتم برای نمایش گراف از یک ماتریس هم جواری استفاده میشه.
اینم الگوریتم بررسی امیدبخش بودن یک گره
اما در جلسات قبلی درباره ی مسئله ی حاصل جمع زیر مجموعه ها صحبت کردیم و گفتیم که این مسئله خیلی شبیه مسئله ی کوله پشتی صفر و یک هست . تقریبا با همون نگرش میشه الگوریتمی عقبگرد برای مسئله ی کوله پشتی صفر و یک ارائه کرد . این الگوریتم رو در زیر ملاحظه میکنید :
bool promising (index i)}
index j,k;
int totweight;
float bound ;
}
دوستان عزیز توجه کنید که مطالب بالا به هم متصل هستند و همگی با هم یک الگوریتم عقبگرد برای مسئله ی کوله پشتی صفر و یک خواهند بود .
اما به عنوان آخرین مطلب برای این جلسه ، یک مقایسه میکنیم بین الگوریتم عقبگرد و برنامه ریزی پویا در مسئله ی کوله پشتی صفر و یک .
الگوریتم برنامه ریزی پویا در بدترین حالت از مرتبه ی مینیمم 2 به توان n و nW هست .
اما الگوریتم عقبگرد فقط از مرتبه ی 2 به توان nهست .
هورویتز و ساهنی نشون دادن که الگوریتم عقبگرد معمولا نسبت به الگوریتم برنامه ریزی پویا کارایی بیشتری داره . اما برنامه ریزی پویا و روش تقسیم و حل رفتن اتحاد تشکیل دادن :))
چجوری؟
خود هورویتز و ساهنی یک الگوریتم ترکیبی از این دو روش ارائه کردند که در بدترین حالت از مرتبه ی 2 به توان n/2 هست و الگوریتمی که حاصل از اتحاد اون دو روش پویا و تقسیم و حل بود معمولا کارایی بیشتری نسبت به الگوریتم عقبگرد داره .
در جلسه ی بعدی درباره ی راهبرد شاخه و حد صحبت می کنیم . تا جلسه ی بعدی خدانگهدار همه ی شما عزیزان
نظرات کاربران
4 سال پیش
ali-ra
این سایت فوق العادس