بخشی از پاورپوینت
اسلاید 2 :
راهبرد عقبگرد (Backtracking)
راهبرد عقبگرد را برای حل مسائل را با یک مثال شروع میکنیم.
مساله n وزیر (n-Queens) از جمله مسائل کلاسیک در این حوزه است.
هدف در این مساله آن است تا n وزیر را در یک صفحه شطرنج n × n به گونهای قرار دهیم تا هیچ دو وزیری همدیگر را تهدید نکنند.
بنابراین هیچ دو وزیری در یک سطر، ستون و یا قطر قرار نخواهند گرفت.
اسلاید 3 :
راهبرد عقبگرد (Backtracking)
به صورت کلی راهبرد عقبگرد برای حل مسائلی مفید هستند که ..
میخواهیم یک توالی (sequence) را از …
مجموعهای مشخص از توالیها به گونهای انتخاب کنیم که ..
توالی انتخاب شده معیارهای مشخصی را دارا باشد.
در مساله n وزیر، توالی ..
موقعیتی است که هر وزیر در آن قرار میگیرد
مجموعه مشخص، .
n2 موقعیتی در صفحه شطرنج است که هر وزیر میتواند در آن قرار گیرد. پس مجموعه در این مثال n2 × . n2 × n2 × عضو دارد.
معیار نیز آن است که ..
هیچ دو وزیری همدیگر را تهدید نکنند.
اسلاید 4 :
راهبرد عقبگرد
عقبگرد، نسخه اصلاح شدهای از الگوریتم پیمایش عمقی درخت یا .
Depth First Search (DFS) میباشد.
به طور کلی در الگوریتمهای پیمایش عمقی درخت، از ریشه درخت کار پیمایش شروع میشود و .
تا حد امکان در شاخهها کار پیمایش انجام میشود و سپس .
به ریشه بازگشت انجام میشود تا پیمایش در دیگر شاخهها صورت پذیرد
اسلاید 5 :
راهبرد عقبگرد
جهت یادآوری: 3 نوع پیمایش DFS وجود دارد:
Pre-order
ابتدا داده ریشه مشاهده میشود (یا المان جاری)
زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش میشود
زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش میشود
In-order (symmetric)
ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش میشود
سپس داده ریشه مشاهده میشود (یا المان جاری)
سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش میشود
Post-order
ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش میشود
سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش میشود
سپس داده ریشه مشاهده میشود (یا المان جاری)
اسلاید 6 :
راهبرد عقبگرد
در ادامه درخت شکل زیر با پیمایش عمقی با رویکرد pre-order ، .
همان رویکرد راهبرد عقبگرد پیمایش میشود.
اسلاید 7 :
راهبرد عقبگرد
به مساله n وزیر برمیگردیم.
برای n=4، میخواهیم تکنیک عقبگرد را استفاده کنیم.
پس وزیرها باید در صفحه شطرنج با ابعاد 4 × 4 قرار گیرند به گونهایکه .
هیچ دو وزیری همدیگر را تهدید نکنند.
در ابتدای کار برای چیدن وزیرها بیدرنگ این مطلب به ذهن میرسد که .
هیچ دو وزیری نمیتوانند در یک سطر قرار گیرند.
بنابراین برای حل توالی خاصی که به دنبالش هستیم، اینگونه عمل میکنیم که .
هر وزیر را به سطر مشخصی تخصیص میدهیم و کنترل میکنیم که .
چه ستونی برای هر کدام سبب حل مساله میشود.
در این مساله باتوجه به اینکه هر وزیر تنها میتواند در یکی از چهار ستون قرار گیرد .
بنابراین مجموعه توالیها به تعداد .
4 × 4 × 4 × 4 = 256 توالی کاندید دارد.
اسلاید 8 :
راهبرد عقبگرد
به صورت زیر میتوانیم راه حلهای کاندید را ایجاد کنیم .
درختی ایجاد میکنیم که .
انتخاب ستونی برای وزیر اول (وزیر اول در کدام ستون قرار گیرد) در گرههای سطح یک درخت باشد
پس، ریشه چهار فرزند دارد
که برای ریشه و همه گرههای میانی در این درخت، فرزندانشان را از چپ به راست با 1 تا 4 شمارهگزاری میکنیم.
به همین ترتیب .
هر گره در سطح اول خود چهار فرزند دارد که .
ستون انتخابی برای وزیر دوم در گرههای این سطح (سطح دوم) قرار دارد.
این روند به همین ترتیب ادامه مییابد.
اسلاید 10 :
هر مسیری از ریشه به برگ یک راه حل (دنباله موردنظر) میتواند باشد.
درختی که با این تفصیل ساخته شد، درخت فضای حالت (state space tree) نامیده میشود.
به راحتی میتوان فهمید که تعداد برگهای این درخت ..
256 برگ میباشد که هر برگ متناظر با ..
یک راه حل کاندید میباشد.
در درخت فضای حالتی که در بالا مشاهده میشود، در هر گره زوج مرتب برچسب خورده است که به این معنا است که .
وزیر i ام در ستون j ام قرارگرفته است.
اسلاید 11 :
برای آنکه راه حلها را پیدا کنیم، .
هر راه حل کاندید (مسیر از ریشه به هر برگ) را چک میکنیم.
این چک کردن با پیمایش pre-order انجام میپذیرد.
[< 1, 1 >, < 2, 1 >, < 3, 1 >, < 4, 1 >]
[< 1, 1 >, < 2, 1 >, < 3, 1 >, < 4, 2 >]
[< 1, 1 >, < 2, 1 >, < 3, 1 >, < 4, 3 >]
[< 1, 1 >, < 2, 1 >, < 3, 1 >, < 4, 4 >]
[< 1, 1 >, < 2, 1 >, < 3, 2 >, < 4, 1 >]
اسلاید 12 :
پیمایشی که در اسلاید قبل آمده است، پیمایشی بسیار ساده است.
این پیمایش به علائمی که در طول مسیر وجود دارد توجهی نمیکند.
با توجه به علایم میتوان به جستجوی کاراتری رسید.
علایم میتوانند به ما بگویند که ادامه پیمایش این گره چیزی جز بنبست در پی نخواهد داشت.
اسلاید 13 :
در راهبرد عقبگرد، روند به این صورت است که .
بعد از اینکه متوجه شدیم که ادامه پیمایش یک گره چیزی جز بنبست در پی نحواهد داشت، .
به پدر آن گره بر میگردیم (عقبگرد) و پیمایش را با فزندان بعدی آن ادامه میدهیم.
گرهای را نامیدبخش (non-promise) مینامیم که .
بعد از مشاهده آن تعیین کنیم که ادامه پیمایش آن ما را به راه حل نمیرساند.
هر گرهای که شرط بالا را نداشته باشد را امیدبخش (promise) مینامیم.
اسلاید 14 :
بنابراین راهبرد عقبگرد یعنی .
برای حل مساله درخت فضای حالت آن را ایجاد کنیم
سپس جستجوی عمقی با رویکرد pre-order را در درخت فضای حالت انجام دهیم.
در هر گام از جستجو مشخص کنیم که آیا گرهای که الان در حال مشاهده آن هستیم، امید بخش هست یا نه .
چنانچه امیدبخش باشد، کار را ادامه میمیدهیم و ..
چنانچه امیدبخش نباشد، به گره پدر آن برمیگردیم.
این که با امیدبخش نبودن گرهای به پدر آن برگردیم و عملا گرههای فرزند آن را پیمایش نکنیم، به اصطلاح درخت در آن گره به بعد هرس(prune) میشود و .
درخت فضای حالت پیمایش شده با این رویکرد را .
درخت فضای حالت هرس شده (pruned state space tree) نامیده میشود.
اسلاید 15 :
الگوریتم عمومی رویکر عقبگرد به صورت زیر میباشد.
function checknode (v)
{
if (promising(v))
if (there is a solution at v)
write the solution;
else
for (each child u of v)
checknode(u);
}
اسلاید 16 :
در اولین گام، ریشه درخت به تابع checknode به عنوان پارامتر ارسال میشود.
وقتی تابع checknode با گرهای صدا زده میشود (گره در پیمایش مشاهده میشود) .
ابتدا چک میشود که آیا امیدبخش است یا خیر
چنانجه امیدبخش بود و راهحلی در آن گره وجود داشته باشد، .
راه حل چاپ میشود.
اگر راه حل در گره امیدبخشی وجود نداشت، ..
تمامی فرزندان آن صدا زده میشوند.
بسته به هر مساله، تابع promising متفاوت است که بایستی برای آن مساله پیادهسازی شود.
function checknode (v)
{
if (promising(v))
if (there is a solution at v)
write the solution;
else
for (each child u of v)
checknode(u);
}
اسلاید 19 :
کوئیز از جلسه قبل)
الف) درختی دودویی کامل با عمق 3 ترسیم کنید و گرههای آن را به صورت in-order پیمایش کنید (با اعداد فارسی داخل گرهها شمارهگذاری کنید)
ب) همان درخت را به صورت post-order پیمایش کنید (با اعداد انگلیسی بیرون گرهها شمارهگذاری کنید)
ج) همان درخت را به صورت pre-order پیمایش کنید (با اعداد فارسی بیرون گرهها)
د) زمانیکه برای مسالهای درخت فضای حالتش را متصور میشویم بدترین روش پیمایش درخت برای رسیدن به راهحل مساله کدام روش میباشد؟ چرایی پاسخ را کوتاه بیان فرمایید.
ه) راهبرد عقبگرد در حل مساله مشابه کدام روش پیمایش درخت است؟ تفاوت آنها را کوتاه بیان نمایید.
و) تابعی با نام checknode بنویسید که گرهای به آن داده شود و از آن گره درخت را بارویکرد عقبگرد در حل مساله پیمایش نماید.
اسلاید 20 :
راهبرد عقبگرد- مسئله n وزیر
در مساله n وزیر، تابع promising بایستی چک کند که آیا دو وزیر در ستون یا قطر یکسانی قرار دارند یا خیر.
چنانچه col(i) بیانگر ستونی باشد که وزیر در سطر iام در آن قرار دارد .
بنابراین برای چککردن اینکه وزیر سطر kام، در ستون یا قطر یکسانی با وزیر سطر iام قرار دارد یا خیر، میبایست روابط زیر را کنترل کنیم:
