مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== جستجوی کامل ======
بررسی تمامی حالت‌های ممکن برای رسیدن به جواب را جستجوی کامل می‌گویند. اگر حالت‌های مسأله زیاد باشند، زمان الگوریتم هم زیاد خواهد بود. با حالت‌بندی مسأله می‌توان حالت‌های غیرضروری را حذف کرد تا بتوان در زمان معقول مسأله را حل کرد.

مثالهایی از مسأله‌های با حالت‌های محدود رمزهای ۵ رقمی هستند که $10^5$ حالت دارند یا نام‌های ۵ حرفی که $\binom{26}{5}=65780$ حالت دارند.
====== تکنیک پس‌گرد ======
حل مسأله را می‌توان به صورت ساخت یک زیرمجموعه از مجموعه حالت‌های ممکن در نظر گرفت. با شروع از مجموعه تهی، هر بار یک عضو انتخاب نشده را به مجموعه فعلی اضافه می‌کنیم. با این کار یا به یک جواب میانی مجاز با اندازه‌ی بیشتر می‌رسیم یا به تناقض می‌رسیم و به آخرین حالت مجاز پس‌گرد می‌کنیم. در نهایت با پایان اندازه زیرمجموعه مجاز یا امتحان کردن همه‌ی اعضای مجموعه مرجع، تمامی جوابهای مجاز مسأله به دست می‌آیند.

این الگوریتم را می‌توان با استفاده از حلقه یا به صورت بازگشتی پیاده سازی کرد.

همچنین در کتابخانه استاندارد $C++$ با نام $algorithm.h$ تابع $next\_permutation(begin,end)$ وجود دارد که شروع و پایان یک آرایه را می‌گیرد و جایگشت‌های ممکن آن را تولید می‌کند. برای جزئیات بیشتر به [[http://www.cplusplus.com/reference/algorithm/next_permutation/|این صفحه]] مراجعه کنید.

**تحلیل**: به ازای یک مجموعه مرجع $n$ عضوی و مجموعه جواب $k$ عضوی، زمان اجرای الگوریتم $O(k^n)$ است. به همین دلیل برای مسایل با اندازه‌ی کوچک قابل اجرا است.

یکی از کاربردهای این روش پیدا کردن تمام جواب‌های ممکن یک مسأله است. بسیاری از الگوریتم‌ها یک جواب بهینه را پیدا می‌کنند.
====== پس‌گرد با هرس ======
می‌توانیم به روش پس‌گرد به صورت یک درخت نگاه کنیم که در ریشه‌ی آن مجموعه تهی و در هر یک از برگ‌های آن یک جایگشت مجاز وجود دارد. در روش پس‌گرد با هرس، تعدادی از شاخه‌های این درخت را به دلیل اینکه نمی‌توانند به جواب بهینه برسند، هرس می‌کنیم. در الگوریتم این کار به معنی ادامه ندادن بقیه حالت‌ها و پس‌گرد است.

مثلاً اگر قبلاً به جواب $x$ رسیده‌ایم و هدف بیشینه‌سازی است و در شاخه‌ای هستیم که مقدار فعلی آن $y$ است و مجموع مقادیر باقیمانده $r$ است و $y+r < x$ باشد، به این معنی است که در این شاخه نمی‌توانیم به جوابی به خوبی $x$ برسیم، پس به جواب بهینه نمی‌رسد و از همان جا پس‌گرد می‌کنیم.

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه