بخشی از پاورپوینت
اسلاید 1 :
راهبرد عقبگرد
Backtracking approach
درس طراحی الگوریتم ها
اسلاید 2 :
هزارتوی شمشادی
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اگر سعی کنید راه خود را در هزارتوی شمشادی بیابید، راهی ندارید جز دنبال کردن مسیری تا اینکه به بن بست برسید. در این حالت برمی گردید و راهی دیگر را امتحان می کنید.
در این حالت مسئله با یک جستجوی کورکورانه و بررسی تمام راه های ممکن حل می گردد.
اسلاید 3 :
تکنیک عقبگرد
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
مبنای کار تکنیک عقبگرد مشابه با راهیابی در هزارتو می باشد با این تفاوت که تمام راه های ممکن پیمایش نمی شود. بلکه در حل مسئله، برخی از راه ها که شرایط مورد نظر را ندارند، پیمایش نمی گردند.
از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که این دنباله، باید دارای شرایط خاصی باشد.
یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
هدف، چیدن n مهره وزیر در یک صفحه شطرنج n×n به طوریست که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.
اسلاید 4 :
جستجوی عمقی (اول عمق) درخت
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
در جستجوی عمقی (پیمایش preorder) ابتدا ریشه ملاقات می شود و سپس همه فرزندان آن به ترتیب از چپ به راست به صورت عمقی ملاقات خواهند شد.
در جستجوی عمقی یک مسیر را با عمق هرچه بیشتر دنبال می کنیم تا به حل یا بن بست برسیم. در بن بست آنقدر به عقب برمیگردیم تا به گرهی برسیم که فرزندان آن پیمایش نشده اند و سپس دوباره به مسیری دیگر با عمق هرچه بیشتر پیشرفت می کنیم.
اسلاید 5 :
عقبگرد
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
عقبگرد حالت اصلاح شده ی جستجوی عمقی یک درخت است.
الگوریتم عقبگرد همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می شوند که گره امیدبخش باشد و در گره جاری حلی وجود نداشته باشد.
گره را غیرامیدبخش گوییم اگر هنگام ملاقات گره معلوم شود که احتمالاً منجر به حل نمی شود.
در غیر اینصورت گره امیدبخش است.
تکنیک عقبگرد شامل انجام جستجوی عمقی در درخت فضای حالت، تعیین امیدبخش بودن گره و در صورت امید بخش نبودن، بازگشت به گره والد می شود.
اسلاید 6 :
درخت فضای حالت (State Space)
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
تمام مسیرهای ممکن (حل های کاندید) از یک درخت (مسئله) را درخت فضای حالت گویند.
به عنوان مثال بخشی از درخت فضای حالت برای مسئله n وزیر که در آن n=4
هر وزیر را به یک سطر انتساب داده شده و باید چک کرد کدام ترکیب از ستونهای صفحه به حل می انجامد.
تعداد حالات: 4×4×4×4
اسلاید 7 :
درخت فضای حالت هرس شده
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
تکنیک عقبگرد تمام فضای حالت را پیمایش نمی کند بلکه درخت فضای حالت را با تعیین امیدبخش نبودن برخی گره ها هرس کرده و فقط بخشی از کل فضای حالت را ملاقات می نماید.
زیر درخت شامل گره های بازبینی شده را درخت فضای حالت هرس شده گویند.
اسلاید 8 :
نمونه ای از درخت فضای حالت هرس شده
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اسلاید 9 :
الگوریتم کلی راهبرد عقبگرد
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
در این الگوریتم، تمام فرزندان یک گره امیدبخش بازبینی می شوند. درنتیجه کارایی کمتر است.
در این الگوریتم، به ازای هر گره، تنها فرزندانی از آن که امیدبخش باشند، بازبینی می گردند.
اسلاید 10 :
بخشی از درخت فضای حالت هرس شده برای نمونه ای از مسئله n وزیر (n=4)
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اسلاید 11 :
نمونه ای از مسئله n وزیر (n=4)
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اسلاید 12 :
مسئله n وزیر
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
برای ساده سازی، هر وزیر را به یک ردیف انتساب می دهیم.
در مسئله n وزیر، تابع امیدبخش باید چک کند که آیا دو وزیر در یک ستون یا قطر هستند یا خیر.
فرض کنیم col(i) ستونی باشد که وزیر iاُم در آن قرار دارد.
دو وزیر در یک ستون قرار دارند اگر: col(i) = col(k)
دو وزیر در یک قطر قرار دارند اگر: |col(i)-col(k)| = |i-k|
اسلاید 13 :
الگوریتم عقبگرد برای مسئله n وزیر
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اسلاید 14 :
تحلیل الگوریتم
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
تحلیل الگوریتم از لحاظ نظری دشوار است.
می توان حد بالایی برای تعداد گره های درخت فضای حالت هرس شده را با شمارش تعداد کل گره های درخت فضای حالت بدست آورد:
1 گره در سطح صفر، n گره در سطح 1، n2 گره در سطح 2 ، . و nn گره در سطح n
1+n+n2+n3+…+nn = (nn+1-1)/n-1
مثلاً برای n=8، 19،173،961 گره داریم.
ولی تعداد گره های درخت هرس شده خیلی کمتر از این میزان است.
می توان حد بالای گره های امیدبخش را با توجه به اینکه هیچ دو وزیری در یک ستون قرار نمی گیرند، بدست آورد.
1+n+n(n-1)+n(n-1)(n-2)+….+n!
مثلاً برای n=8، 109،601 گره امیدبخش داریم
اسلاید 15 :
تحلیل الگوریتم .
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
نتایج اجرای 3 الگوریتم مختلف برای مقایسه تعداد گره های پیمایش شده
الگوریتم1: جستجوی عمقی
الگوریتم 2: براساس اینکه هیچ دو وزیری روی یک سطر یا ستون نیستند
اسلاید 16 :
مسئله حاصل جمع زیرمجموعه ها
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
در اینجا n عدد صحیح مثبتِ wi (اوزان) و یک عدد صحیح مثبت W وجود دارد.
هدف یافتن تمام زیرمجموعه هایی از این n عدد صحیح است که حاصل جمع آنها برابر W باشد.
اسلاید 17 :
ایجاد درخت فضای حالت
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
از ریشه به طرف چپ میرویم تا w1 را در مجموعه بگنجانیم و به طرف راست میرویم اگر بخواهیم w1 را طرد نماییم.
به طور مشابه در سطوح بعدی نیز برای انتخاب یا عدم انتخاب وزن های دیگر به سمت چپ یا راست می رویم.
هنگامی که wi را در مجموعه می گنجانیم، wi را روی یالی که در آن قرار داده می شود می نویسیم و هنگامی که wi را طرد می کنیم، 0 می نویسیم.
اسلاید 18 :
مثال (n=3 و W=6)
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اسلاید 19 :
الگوریتم عقبگرد و تعیین امیدبخشی
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
اگر وزنها را به صورت صعودی مرتب کنیم، وقتی در سطح iاُم هستیم، wi+1 کمترین وزن باقیمانده است.
اگر weight مجموع وزنهای موجود در زیرمجموعه تا گره ای در سطح i باشد:
در صورتی که weight + wi+1 > W، این گره غیر امیدبخش است و باید عقبگرد نمود.
همچنین اگر total مجموع وزن اعداد باقیمانده باشد:
در صورتی که weight + total < W، این گره غیر امیدبخش است و باید عقبگرد کرد.
در صورتی که weight = W، گره شامل یک حل است و باید حل را چاپ کرد و عقبگرد نمود.
در غیر این صورت، گره امیدبخش است و فرزندان آن باید ملاقات شوند.
اسلاید 20 :
مثال (n=4 و W=13) با الگوریتم عقبگرد
درس طراحی الگوریتم ها - فصل پنجم: راهبرد عقبگرد - بیدکی
