پاورپوینت فصل هشتم راهبرد عقبگرد (pptx) 105 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 105 اسلاید

قسمتی از متن PowerPoint (.pptx) :

راهبرد عقبگرد (Backtracking) راهبرد عقبگرد را برای حل مسائل را با یک مثال شروع می‌کنیم. مساله n وزیر (n-Queens) از جمله مسائل کلاسیک در این حوزه است. هدف در این مساله آن است تا n وزیر را در یک صفحه شطرنج n × n به گونه‌ای قرار دهیم تا هیچ دو وزیری همدیگر را تهدید نکنند. بنابراین هیچ دو وزیری در یک سطر، ستون و یا قطر قرار نخواهند گرفت. 2 راهبرد عقبگرد (Backtracking) به صورت کلی راهبرد عقبگرد برای حل مسائلی مفید هستند که .... می‌خواهیم یک توالی (sequence) را از … مجموعه‌ای مشخص از توالی‌ها به گونه‌ای انتخاب کنیم که .... توالی انتخاب شده معیارهای مشخصی را دارا باشد. در مساله n وزیر، توالی .... موقعیتی است که هر وزیر در آن قرار می‌گیرد مجموعه مشخص، ... n2 موقعیتی در صفحه شطرنج است که هر وزیر می‌تواند در آن قرار گیرد. پس مجموعه در این مثال n2 × ... n2 × n2 × عضو دارد. معیار نیز آن است که .... هیچ دو وزیری همدیگر را تهدید نکنند. 3 راهبرد عقبگرد عقبگرد، نسخه اصلاح شده‌ای از الگوریتم پیمایش عمقی درخت یا ... Depth First Search (DFS) می‌باشد. به طور کلی در الگوریتم‌های پیمایش عمقی درخت، از ریشه درخت کار پیمایش شروع می‌شود و ... تا حد امکان در شاخه‌ها کار پیمایش انجام می‌شود و سپس ... به ریشه بازگشت انجام می‌شود تا پیمایش در دیگر شاخه‌ها صورت پذیرد 4 راهبرد عقبگرد جهت یادآوری: 3 نوع پیمایش DFS وجود دارد: Pre-order ابتدا داده ریشه مشاهده می‌شود (یا المان جاری) زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود In-order (symmetric) ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود سپس داده ریشه مشاهده می‌شود (یا المان جاری) سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود Post-order ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود سپس داده ریشه مشاهده می‌شود (یا المان جاری) 5 راهبرد عقبگرد در ادامه درخت شکل زیر با پیمایش عمقی با رویکرد pre-order ، ... همان رویکرد راهبرد عقبگرد پیمایش می‌شود. 6 راهبرد عقبگرد به مساله n وزیر برمی‌گردیم. برای n=4، می‌خواهیم تکنیک عقبگرد را استفاده کنیم. پس وزیرها باید در صفحه شطرنج با ابعاد 4 × 4 قرار گیرند به گونه‌ایکه ... هیچ دو وزیری همدیگر را تهدید نکنند. در ابتدای کار برای چیدن وزیرها بی‌درنگ این مطلب به ذهن می‌رسد که ... هیچ دو وزیری نمی‌توانند در یک سطر قرار گیرند. بنابراین برای حل توالی خاصی که به دنبالش هستیم، اینگونه عمل می‌کنیم که ... هر وزیر را به سطر مشخصی تخصیص می‌دهیم و کنترل می‌کنیم که ... چه ستونی برای هر کدام سبب حل مساله می‌شود. در این مساله باتوجه به اینکه هر وزیر تنها می‌تواند در یکی از چهار ستون قرار گیرد ... بنابراین مجموعه توالی‌ها به تعداد ... 4 × 4 × 4 × 4 = 256 توالی کاندید دارد. 7 راهبرد عقبگرد به صورت زیر می‌توانیم راه حل‌های کاندید را ایجاد کنیم ... درختی ایجاد می‌کنیم که ... انتخاب ستونی برای وزیر اول (وزیر اول در کدام ستون قرار گیرد) در گره‌های سطح یک درخت باشد پس، ریشه چهار فرزند دارد که برای ریشه و همه گره‌های میانی در این درخت، فرزندانشان را از چپ به راست با 1 تا 4 شماره‌گزاری می‌کنیم. به همین ترتیب ... هر گره در سطح اول خود چهار فرزند دارد که ... ستون انتخابی برای وزیر دوم در گره‌های این سطح (سطح دوم) قرار دارد. این روند به همین ترتیب ادامه می‌یابد. 8 راهبرد عقبگرد 9