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

1395/1/18 --- 2049

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

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

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

خب دوستان بیایم درباره ی یکی از مسائل بسیار مهم و معروف در این زمینه صحبت کنیم . این مسئله "چند وزیر" یا "n  وزیر " نام داره و چون معمولا روی صفحه ی شطرنج اونو حل میکنن و ملاک قرار میدن ، این مسئله رو "8 وزیر" هم میگن . ولی خب در حالت کلی n میتونه هر عددی ( مثل 8( باشه . خب توی مسئله هدف ما اینه که در یک صفحه ی شطرنجی n*n وزیر ها رو (n تا وزیر) طوری قرار بدیم که همدیگر رو تهدید نکنن . برای کسانی که با علم شطرنج آشنایی ندارن عرض کنم که یک وزیر در جهت محورهای افقی ، عمودی و قطری حرکت می کنه . خب توی این مسئله میشه دنباله رو ، n موقعیتی که توی اون وزیر ها قرار میگیرن ، در نظر گرفت . مجموعه ی ما هم عبارت هست از تمام جاهایی که وزیر ها میتونن قرار بگیرن که قطعا دارای n به توان دو عضو خواهد بود . ملاک هم همون تهدید نکردن وزیر هاست .

 

حالا بیایم مسئله رو برای یک n کوچکتر مثل 4 بررسی کنیم . مسلما این مسئله به این صورت هست که میخوایم 4 تا وزیر رو توی یک صفحه ی شطرنج 4*4 طوری قرار بدیم که هیچکدوم نتونن همدیگرو تهدید کنن . برای حل چنین مسئله ای ما 256 راه حل کاندید داریم هر کدوم از این 4 وزیر میتونن در 4 خونه ی مجزا قرار بگیرن . این تکنیک میاد درخت فضای حالت رو ایجاد میکنه و این رو در نظر میگیره که گره های سطح اول درخت ، انتخاب های ستون برای وزیر ردیف اوله و گره های سطح دوم ، انتخاب های ستون برای وزیر دومه و برای وزیر های سوم و چهارم هم همین ترتیب برقراره . ما اگر این درخت رو رسم کنیم میبینیم که درخت خیلی کوچکی نیست ! چون هر مسیر از ریشه به سمت برگ ، یک راه حل کاندید خواهد بود . پس ما 256 برگ داریم توی این درخت . توی هر گره هم یک زوج مرتب (i,j) نگه می داریم و معنیش اینه که وزیر توی ردیف iام و ستون  jام قرار خواهد داشت .

خب حالا کافیه با یک پیمایش عمقی مناسب ، تمام راه حل های کاندید رو پیدا کنیم . بسیاری از راه حل های کاندید رو میشه به راحتی حذف کرد و حتی بررسی هم نکرد . مثلا فرض کنید وزیر اول در سطر 1 و ستون 1 باشه . یعنی داشته باشیم Q(1,1)

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

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

درخت

همون طور که میبینید ، یک راه حل ، مجموعه جواب {(1,2),(2,4),(3,1),(4,3)}  هست . معنیش این هست که ، وزیر 1 باید توی ردیف 1 و ستون 2 باشه ، وزیر 2 باید توی سطر 2 و ستون 4 باشه . وزیر 3 هم توی ردیف 3 و ستون 1 باشه و در نهایت وزیر چهارم توی سطر 4 و ستون 3 باشه .اما تصاویر زیر میتونن جزئیات بیشتری از نحوه ی استفاده از این تکنیک برای حل مسئله رو در اختیار ما بذارن . بعد از تصاویر توضیحاتش رو هم خواهید دید .

شطرنج

تصویر1

شطرنج

تصویر2

شطرنج

تصویر3

شطرنج

تصویر4

شطرنج

تصویر5

شطرنج

تصویر6

شطرنج

تصویر7

شطرنج

تصویر8

شطرنج

تصویر9

شطرنج

تصویر10

شطرنج

تصویر11

در تصویر شماره ی 1 :

(1,1) امید بخش هست

در تصویر 2 :

(2,1) و (2,2) امید بخش نیستند

(3,3) امید بخش هست

در تصویر 3 :

(3,1) و  (3,2) و (3,3) و (3,4) امید بخش نیستند .

در تصویر شماره ی 4 :

عقبگرد به (1,1) داریم .

(2,4) امید بخش هست .

در تصویر 5 :

(3,1) امید بخش نیست

(3,2) امید بخش هست

در تصویر 6 :

(4,1) و (4,2) و (4,3) و (4,4) امید بخش نیستند .

در تصویر 7 :

عقبگرد به (2,4) داریم .

(3,3) و (3,4) امید بخش نیستند

در تصویر 8 :

عقبگرد به ریشه داریم .

(1,2) امید بخش هست .

در تصویر 9 :

(2,1) و (2,2) و (2,3) امید بخش نیستند .

(2,4) امید بخش هست .

در تصویر 10 :

(3,1) امید بخش هست .

در تصویر 11:

(4,1)  و (4,2) امید بخش نیست

(4,3) امید بخش هست .

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

الگوریتم n وزیر

هدف مسئله رو که دیگه کامل میدونید و اگر فرض کنیم هر وزیر قطعا در یک سطر قرار میگیره ، تابع امیدبخش باید بیاد چک کنه که دو وزیر در یک ستون یا قطر هستن یا نه . اگر col(i) ستونی باشه توی اون وزیر ردیف i ام قرار میگیره ، آنگاه برای اینکه ببنیم آیا با وزیر در ردیف kام در یک ستون هستن باید چک کنیم که آیا :

col(i)=col(k)

برای چک کردن قطر ها هم باید بگیم که اگر وزیر ردیف i ام  با وزیر ردیف k ام در یک قطر باشن ، اونوقت داریم :

col(i)-col(k)=i-k

یا

col(i)-col(k)=k-i

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

مثلا فرض کنید 5 عدد صحیح داشته باشیم و عدد ماکسیمم ما 21 باشه . اعداد ماهم عبارت هستن از

w1=5

w2=6

w3=10

w4=11

w5=16

در این صورت راه حل های موجود هم به صورت زیر خواهند بود

w1+w2+w3=5+6+10=21

w1+w5=5+16=21

w3+w4=10+11=21

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

درخت فضای حالت

الگوریتم عقبگرد برای این مسئله هم به صورت زیر خواهد بود که در اون ورودی های ما یک عدد صحیح و مثبت n ، آرایه ای غیر نزولی از اعداد صحیح و مثبت w و همچنین عدد صحیح و مثبت W خواهند بود . خروجی این الگوریتم هم عبارت هست از ترکیبات اعداد صحیح که حاصل جمع اونها برابر با W بشه .

حاصل جمع زیر مجموعه

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

•اقتصاد

•محیط زیست

•شیمی

•فیزیک

•مدلسازی

•شبیه سازی

•علوم کامپیوتر

•گرافیک

•و ..........

هست .

 

حالا چجوری میشه از الگوریتم مونت کارلو برای تخمین کارایی یک الگوریتم عقبگرد استفاده کرد ؟

ببینید دوستان در درختی که شامل گره هایی هست که برای مسئله ی خاص چک میشن ، یک مسیر تولید می کنیم و بعدش تعداد گره های درخت رو از روی مسیر برآورد میکنیم . 2 شرط رو هم باید در نظر بگیریم :

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

2-در یک سطح مشترک از درخت فضای حالت ، تمام گره ها باید دارای تعداد فرزندان یکسان باشن .

ادامه ی مسیر این الگوریتم هم به صورت زیر هست :

•فرض میکنیم m0  برابر با تعداد فرزندان امید بخش ریشه باشه.

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

•به شکل تصادفی فرزندی برای گره ی امیدبخش به دست آمده در مرحله ی گذشته ایجاد می کنیم . فرض می کنیم تعداد فرزندان امید بخش این گره برابر با m2 باشه.

•به همین ترتیب این روند رو ادامه میدهیم تا هیچ فرزند امیدبخشی پیدا نشه.

•حالا فرض کنیم که ti تعداد فرزندان یک گره در سطح iام باشه.

از اونجایی که همه ی ti فرزند مربوط به یک گره چک میشن و فقط mi فرزند امید بخش دارای فرزندانی هستن که چک میشن ، یک تخمین از تعداد کل گره های چک شده توسط الگوریتم عقبگرد برای یافتن تمام حل های ممکن عبارت خواهد بود از :

1+t0+m0t1+m0m1t2+…..+m0m1….mi-1ti+..

توی تصویر زیر الگوریتم تخمین مونت کارلو رو ملاحظه می فرمایید :

تخمین مونت کارلو

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