ابزار کاربر
ابزار سایت
برنامه‌ریزی پویا
در برنامه‌ریزی پویا، مسأله را با کمک زیرمسأله‌های یکسان با مسأله اصلی ولی نه لزوماً مجزا حل می‌کنیم؛ به این صورت که جواب زیرمسأله‌ها را به دست می‌آوریم و با کمک آنها جواب مسأله‌ی اصلی را به دست می‌آوریم. دو نوع برنامه‌ریزی پویا وجود دارد:
- پایین به بالا: در روش پایین به بالا، ابتدا برای حالتهای کوچک مسأله حل می‌شود، سپس با ترکیب آنها حالتهای بزرگتر ساخته می‌شوند. برای این کار باید مقدار حالتهای پایه را داشته باشیم و رابطه‌ی بازگشتی برای ساختن حالتهای بزرگتر از روی این حالتها را هم بدانیم.
- بالا به پایین: در روش بالا به پایین، مسأله را به زیرمسأله‌هایی می‌شکنیم و جواب هر زیرمسأله را حساب می‌کنیم و توجه می‌کنیم که جواب زیرمسأله‌های تکراری را حساب نکنیم. در ابتدا به حالتها مقدار ناشناخته (مثلاً -۱ در حالتی که همه مقادیر مثبت هستند) می‌دهیم و هر بار به زیرمسأله با مقدار ناشناخته می‌رسیم، آن را حل می‌کنیم.
حل مسایل با برنامه‌ریزی پویا
ابتدا باید برای زیرمسأله‌ها ویژگی‌های کمی پیدا کنیم که بتوانند ابعاد جدول ذخیره مقادیر زیرمسأله‌ها باشند. مثالهایی از این کمی‌سازی عبارت اند از:
- بازه مقادیر صحیح گسسته برای یک متغیر با مقادیر صحیح در بازه معلوم
- یک ویژگی گسسته از مسأله مانند طول رشته
- یک عدد معادل رشته دودویی که یک زیرمجموعه را نشان می‌دهد (بیت $i$-ام ۰ باشد عضو در این زیرمجموعه نیست و ۱ باشد هست). به این روش
bit maskمی‌گویند. - ویژگی از مسأله که به سادگی قابل محاسبه است، مثل طول کوتاهترین مسیر در گراف.
- زیردرختی از یک درخت
تعداد ویژگی‌های مورد نیاز برای مشخص کردن یک زیرمسأله ابعاد (جدول) برنامه‌ریزی پویا را مشخص می‌کند.
مهم‌ترین قسمت حل مسأله با این روش تشخیص درست زیرمسأله‌ها است. همچنین می‌توان برای کم کردن زمان اجرا، از جستجوی دودویی روی بازه مقادیر یا نامساوی‌ها استفاده کرد.
برای اینکه مجموعه سازنده‌ی جواب را هم علاوه بر مقدار جواب در اختیار داشته باشیم، از یک جدول کمکی استفاده می‌کنیم که ابعاد یکسانی با جدول برنامه‌ریزی پویا دارد و نشان می‌دهد عملی که با آن به این خانه از جدول رسیده‌ایم چه بوده است. برای مثال به حل دو مسأله‌ی زیر توجه کنید:
سایر مسایل مهم در برنامه‌ریزی پویا در ادامه آمده‌اند:
مسایل نمونه
۱- مثلثی از اعداد داریم که از گوشه‌ی بالا سمت چپ شروع به حرکت می‌کنیم و به اعداد مجاور سطر پایین می‌توانیم برویم. بیشترین مجموعی که می‌توانیم به آن برسیم چقدر است؟
برای مثال در مثلث زیر، بیشترین مقدار را مسیر $1-3-9-1$ دارد که مجموع ۱۴ دارد.
1 2 3 1 5 9 9 1 1 1
جواب: به ترتیب سطرها را از بالا به پایین طی می‌کنیم و بیشترین مجموع مسیری که به هر عدد آن سطر می‌رسد را در جدول برنامه‌ریزی پویا نگه می‌داریم. همزمان در جدول نگه‌داری مسیر، ثبت می‌کنیم که از کدامیک از اعداد سطر قبل به این عدد رسیده‌ایم. مقدار بیشینه سطر آخر جواب مسأله است و با بازگشت از مسیر نگه‌داری شده، مسیر متناظر آن را به دست می‌آوریم.
اگر مسیر را لازم نداشته باشیم و فقط بیشترین عدد را بخواهیم، کافی است که فقط نتایج آخرین سطر را نگه‌داریم.
۲-تعداد پرانتزگذاری‌های مجاز به طول $2N, 1\leq N \leq 19$ که $K, 1\leq K \leq N$ پرانتز باز داشته باشند را به دست آورید. برای مثال $()1)$ یک پرانتزگذاری درست و $))()($ یک پرانتزگذاری نادرست است.
جواب: اگر پرانتزگذاری صحیح باشد، تعداد پرانتزهای باز و بسته‌ی آن برابر هستند. پس $K=N$. در این صورت به مسأله‌ی ترکیبیاتی اعداد کاتالان تبدیل می‌شود. برای محاسبه‌ی جواب، از برنامه‌ریزی پویا برای محاسبه ترکیب‌ها استفاده می‌کنیم.
۳-عمل جداسازی رشته‌ی $w=xy$ را به $u=yx$ تبدیل می‌کند. مثلاً کلمه‌ی $cutword$ با یک عمل جداسازی به $wordcut$ تبدیل می‌شود. دو کلمه به طول $2\leq N \leq 10^3$ داده شده است، به چند طریق می‌توان با $0\leq K \leq 10^5$ عمل جداسازی، کلمه‌ی اول را به کلمه‌ی دوم تبدیل کرد؟
جواب: مسأله را به صورت یک آرایه دو بعدی مدل کنید که سطرها متناظر مقادیر $K$ و ستونها متناظر محل برش کلمه هستند و درون خانه‌های جدول رشته‌ی متناظر وجود دارد. هر بار که در این جدول به رشته دوم می‌رسیم، جواب را یکی زیاد می‌کنیم (مقدار اولیه جواب صفر است). چون رابطه بازگشتی متناظر این کار فقط به سطر آخر بستگی دارد، نیازی به نگه داشتن مقادیر قبل از سطر آخر نداریم.
۴-پشته‌ای از $5\leq N \leq 2000$ سکه که $i$-امین سکه از بالا مقدار $1\leq C_i \leq 100000$ دارد، داده شده است. نفر اول بازی را با برداشتن ۱ یا ۲ سکه شروع می‌کند. هر یک از دو بازیکن باید در هر نوبت حداقل یک سکه و حداکثر به مقدار ۲ برابر مقدار سکه‌های برداشته شده توسط نفر قبلی در نوبت قبل، سکه بردارند. بازی وقتی تمام می‌شود که سکه‌ها تمام شوند. با فرض اینکه نفر دوم طوری بازی می‌کند که سود خودش را بیشینه کند، حداکثر مقداری که به نفر اول می‌رسد چقدر است؟
جواب: راهنمایی: زیرمسأله‌ها (وضعیت‌ها) با تعداد سکه‌های باقیمانده، مقداری که نفر اول تا کنون به دست آورده است، نوبت چه کسی است، آخرین نفری که بازی کرده چه مقداری برداشته است؛ مشخص می‌شوند.
۵-یک لانه مورچه $1\leq T \leq 1000$ خانواده مورچه دارد که آنها را با شماره‌های $1,…,T$ مشخص می‌کنیم و کلاً تعداد مورچه‌ها $A$ تا است. هر خانواده مورچه $1\leq N_i \leq 100$ مورچه دارد. مورچه‌هایی که از یک خانواده هستند می‌توانند گروه تشکیل بدهند. به چند حالت می‌توان گرو‌ه‌های با اندازه‌ی $S,S+1,…,B; (1\leq S\leq B \leq A)$ تشکیل داد؟ جواب را به پیمانه‌ی $1000000$ به دست آورید.
جواب: راهنمایی: برای هر خانواده و هر اندازه مجموعه جدا حساب کنید. برای ساخت جدول ترکیب‌ها پیمانه‌ی داده شده را در نظر بگیرید. (هر بار جواب را به این عدد باقیمانده بگیرید. این کار باعث می‌شود سرریز رخ ندهد.)
۶-حسن گاوهای خود را با اعداد دودویی با دقیقاً $1\leq K \leq 10$ رقم $1$ برچسب‌گذاری می‌کند. اولین رقم هر برچسب همیشه $1$ است. حسن برچسب‌ها را صعودی می‌زند و از کوچکترین عدد مجاز (دارای دو شرط گفته شده) شروع می‌کند. او حساب آخرین برچسبی که زده است را از دست داده است. برچسب $N (1\leq N \leq 10^7)$ام مورد نظر حسن را پیدا کنید.
جواب: راهنمایی: تعداد برچسب‌های مجاز با تعداد ارقام مجاز را محاسبه کنید و به دست بیاورید که برچسب $N$-ام چندرقمی است. می‌دانیم رقم اول آن $1$ است. از $N$ تعداد برچسب‌های مجاز با ارقام کمتر را حذف کنید $N'$. کوچکترین برچسب مجاز $K-1$ رقم $1$ در سمت راست دارد و بقیه ارقام آن به جز رقم اول $0$ است. جایگشت $(N'-1)$-ام این رشته دودویی جواب مسأله است. چون حداکثر تعداد ارقام برچسب ۲۴ رقم است و 0 \leq K-1 \leq 9$ است، می‌توان این جایگشت را در زمان مناسبی به دست آورد. (می‌توانید از تابع جایگشت بعدی کمک بگیرید)