برنامه نویسی داینامیک؛ راه حل الگوریتم های پیچیده

برنامه نویسی داینامیک، یک روش حل مسئله است که در علوم کامپیوتر، کاربرد های زیادی دارد. این روش برای حل مسائل بسیار پیچیده استفاده میشود، و روش کار آن، به این صورت است که ابتدا مسئله بزرگ تر را، به ریزمسئله های کوچک تر تبدیل میکند و آنها را حل میکند و پاسخ این ریزمسئله ها را، نگهداری میکند و از آن برای حل ریز مسائل بعدی و در نهایت مسئله نهایی استفاده میکند.

برنامه نویسی داینامیک چیست؟

برنامه نویسی داینامیک، روشی است که در آن سعی میکنیم مسئله بزرگ را، تبدیل به مسائل کوچک تر کنیم و آنها را حل کنیم، از کنار هم قرار دادن جواب ریز مسئله ها، به جواب مسئله های پیچیده تر میرسیم و در نهایت میتوانیم که مسئله نهایی را حل کنیم.

چرا باید از برنامه نویسی داینامیک استفاده کنیم؟

برنامه نویسی داینامیک، بسیار پر کاربرد است به دلیل اینکه، در حل مسائل دشوار و پیچیده، بسیار کمک میکند و در عین حال از سرعت بالایی برخوردار است، در این روش، منابع به روش درستی مدیریت میشود و به دلیل ذخیره سازی جواب ریز مسائل، از تکرار محاسبات، جلوگیری میشود.

چطور یک الگوریتم با روش داینامیک بنویسیم؟

برنامه نویسی داینامیک از دو قسمت بسیار مهم، تشکیل شده است؛ خرد کردن مسئله و ذخیره سازی جواب ها. در ابتدا باید ببینیم که ساده ترین شکل مسئله چیست و جواب آن را به دست بیاوریم و در هر مرحله، مسئله را یک قدم بزرگ تر میکنیم و از جواب های ذخیره شده قبلی، استفاده میکنیم تا مسئله جدید را حل کنیم و این روند تا جایی ادامه پیدا میکند که مسئله نهایی را حل کنیم.

مثالی برای درک بهتر

در مقاله قبلی با مسئله کوله پشتی، آشنا شدیم و در این مقاله میخواهیم که با روش داینامیک آن مسئله را حل کنیم. ما به عنوان یک سارق، وارد فروشگاه شده ایم و میخواهیم با ارزش ترین کالاهایی را، که میتوانیم در کوله پشتی مان جا بدهیم با خودمان برداریم، ظرفیت کوله پشتی محدود است و بسیار مهم است که بدانیم کدام کالاها را برداریم.

کالاها این سه مورد است و کوله پشتی ما، فقط 4 کیلو گرم وزن را میتواند تحمل کند.

در مرحله اول باید مسئله بزرگ را، به یک مسئله کوچک تر تبدیل کنیم، برای مثال اگر ما یک کوله پشتی داشتیم که فقط یک کیلوگرم را میتوانست تحمل کند، و فروشگاه هم فقط پاوربانک داشت، در این صورت بهترین کار این بود که همان پاوربانک را برداریم و در نهایت 2.5 میلیون سود میکردیم. حالا باید این جواب را ذخیره کنیم که در مراحل بعدی بتوانیم از آن استفاده کنیم، برای این کار از یک گرید استفاده میکنیم.

مرحله بعدی این است که فرض کنیم کوله بزرگ تری میتوانیم داشته باشیم و همین مسئله را مجددا حل کنیم، بعد از این مرحله، جدول ما به صورت زیر خواهد بود.

حالا فرض میکنیم که فروشگاه ما، یک کالای دیگر هم دارد و آن لپ تاپ است، لپ تاپ 4 کیلو گرم وزن دارد پس آن را فقط میتوانیم در کوله پشتی 4 کیلویی، قرار بدهیم اگر این کار بکنیم، ارزش نهایی کوله پشتی مان، 7 میلیون تومان خواهد بود و این نسبت به جواب قبلی که برای کوله پشتی 4 کیلویی داشتیم بهتر است، پس این کار را انجام میدهیم.

حالا همین مسئله را، باید با این فرض حل کنیم که کالای اسپیکر هم در فروشگاه وجود دارد، اسپیکر 3 کیلو گرم وزن دارم، اگر بخواهیم کوله 3 کیلوگرمی را، با اسپیکر پر کنیم، 5 میلیون تومان سود میکنیم و این بهتر از جواب قبلی است پس این کار را انجام میدهیم.

اگر بخواهیم اسپیکر را در کوله 4 کیلوگرمی قرار بدهیم، 1 کیلوگرم اضافه میماند که با توجه به جواب های قبلی بهترین کاری که میتوانی با 1 کیلوگرم انجام بدهیم این است که پاوربانک را برداریم که ارزش آن 2.5 میلیون است، در نتیجه مجموع ارزش کالاهایی که برداشتیم 7.5 میلیون تومان میشود که از جواب قبلی بهتر است. گرید ما در نهایت به شکل زیر خواهد بود.

بهترین جواب، برای این مسئله این است که پاوربانک و اسپیکر را برداریم که مجموع قیمت آنها میشود 7.5 میلیون تومان.

جمع بندی

در این مقاله، با روش برنامه نویسی داینامیک آشنا شدیم که از روش های پرکاربرد حل مسئله در علوم کامپیوتر است و در موضوعات مختلف استفاده میشود، البته باید توجه داشته باشیم که این مبحث، یک مبحث پیچیده است و طبیعتا مطالعه یک مقاله برای یادگیری کامل آن کافی نیست، اما سعی کردیم که در این مقاله، با مفاهیم کلی و طرز فکر برنامه نویسی داینامیک، آشنا شویم.

امیدوارم مطالعه این مقاله برایتان مفید بوده باشد، خیلی ممنون میشم که نظرتون رو بهم بگید.

اگر این مطلب برایتان مفید بود، پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده را دنبال کنید.

خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.