پاورپوینت الگوریتم مونت کارلو

دانلود پاورپوینت الگوریتم مونت کارلو Monte Carlo algorithm ppt
راهبرد عقبگرد (Backtracking)
راهبرد عقبگرد را برای حل مسائل را با یک مثال شروع می‌کنیم.
مساله n وزیر (n-Queens) از جمله مسائل کلاسیک در این حوزه است.
هدف در این مساله آن است تا n وزیر را در یک صفحه شطرنج n × n به گونه‌ای قرار دهیم تا هیچ دو وزیری همدیگر را تهدید نکنند.
بنابراین هیچ دو وزیری در یک سطر، ستون و یا قطر قرار نخواهند گرفت.
به صورت کلی راهبرد عقبگرد برای حل مسائلی مفید هستند که ….
می‌خواهیم یک توالی (sequence) را از …
مجموعه‌ای مشخص از توالی‌ها به گونه‌ای انتخاب کنیم که ….
توالی انتخاب شده معیارهای مشخصی را دارا باشد.
در مساله n وزیر، توالی ….
موقعیتی است که هر وزیر در آن قرار می‌گیرد
مجموعه مشخص، …
n2 موقعیتی در صفحه شطرنج است که هر وزیر می‌تواند در آن قرار گیرد. پس مجموعه در این مثال n2 × … n2 × n2 × عضو دارد.
معیار نیز آن است که ….
هیچ دو وزیری همدیگر را تهدید نکنند.

راهبرد عقبگرد
عقبگرد، نسخه اصلاح شده‌ای از الگوریتم پیمایش عمقی درخت یا …
Depth First Search (DFS) می‌باشد.
به طور کلی در الگوریتم‌های پیمایش عمقی درخت، از ریشه درخت کار پیمایش شروع می‌شود و …
تا حد امکان در شاخه‌ها کار پیمایش انجام می‌شود و سپس …
به ریشه بازگشت انجام می‌شود تا پیمایش در دیگر شاخه‌ها صورت پذیرد
جهت یادآوری: 3 نوع پیمایش DFS وجود دارد:
Pre-order
ابتدا داده ریشه مشاهده می‌شود (یا المان جاری)
زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود
زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود
In-order (symmetric)
ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود
سپس داده ریشه مشاهده می‌شود (یا المان جاری)
سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود
Post-order
ابتدا زیردرخت سمت چپ به صورت بازگشتی با همین رویکرد پیمایش می‌شود
سپس زیردرخت سمت راست به صورت بازگشتی با همین رویکرد پیمایش می‌شود
سپس داده ریشه مشاهده می‌شود (یا المان جاری)
در ادامه درخت شکل زیر با پیمایش عمقی با رویکرد pre-order ، …
همان رویکرد راهبرد عقبگرد پیمایش می‌شود.