حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

اشتراک گذاری

مسئله Rod Cutting یا برش میله یکی از بهترین مسایل برای بررسی حل سوال با روش های بازگشتی (recursive) و برنامه نویسی پویا (dynamic programming) است.

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

  1.  الگوریتم بازگشتی یا Recursive
  2. الگوریتم برنامه نویسی پویا از بالا به پایین یا Dynamic programming Top Down
  3. الگوریتم برنامه نویسی پویا از پایین به بالا یا Dynamic programming Bottom Up

 

معرفی سوال برش میله یا Rod Cutting :

 

یک کارخانه، میله های آهنی (البته ورژن هایی دیگر از این مسئله با عنوان برش شیرینی و غیره هم موجود است) را از یک کارخانه ی دیگر می خرد و آن ها را به مشتری های خود می فروشد ، این کارخانه میله ها را در ۱۰ سایز مختلف می فروشد که در زیر اندازه ی هر میله را همراه با قیمتش می بینید:

 

۱۰

۹ ۸ ۷ ۶ ۵ ۴ ۳ ۲ ۱ اندازه
۳۰ ۲۴ ۲۰ ۱۷ ۱۷ ۱۰ ۹ ۸ ۵ ۱

قمیت

 

وقتی مشتری میله با طول ۴ سفارش می دهد کارخانه می تواند یک میله به طول چهار به او بدهد که قیمتش می شود ۹ دلار و یا میکله با طول ۴ را برش بدهد و دو میله با طول ۲ بدهد که قیمتش می شود ۱۰ دلار و یا … نحوه ی برش کاملا در اختیار کارخانه است.

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

 هدف این مسیله آن است که بیشترین سودی را که از انواع برش یک میله به دست می آید را مشخص کنیم.

 

الگوریتم و کد سوال برش میله ( Rod cutting ) با روش بازگشتی ( Recursive )

 

در این روش فضای حالات مسیله را به صورت بازگشتی و عقبگرد ( backtrack ) جست و جو می کنیم و راهی که بیشترین سود را ایجاد را پیدا می کنیم.

فرض کنید میله ای به طول ۴ را می خواهیم بفروشیم درخت حالات برش ها برای این میله به شکل زیر است:

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

همین طور که در بالا مشاهده می کنید بیشترین سود را زمانی می بریم که میله به طول چهار را به دو قسمت با طول دو برش دهیم و از آنجایی که هر برش به طول ۲ قیمتی برابر ۵ دلار دارد سود به دست آمده برابر ۱۰ دلار می شود در سایر حالت ها سود کم تر از ۱۰ دلار می شود.

 

تابع زیر به صورت بازگشتی و عقبگرد درخت بالا را جست و جو می کند و بیشترین سود ممکن را به دست می آورد.

p وکتوری است که مقادیر پیش فرض برش ها و قیمت آن ها را در آن نگه داشته ایم و n طول میله است.

 

 

و این هم کد کلی برنامه به صورت بازگشتی است که در main برنامه تابع را برای میله هایی با طول صفر تا بیست و یک فراخوانده ایم و زمان اجرای آن را به دست آورده ایم تا با دو روش دیگر مقایسه کنیم:

 

در تصویر زیر نتیجه را می بینید:

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

 

همان طور که در تصویر بالا می بینید ۳۱ ثانیه طول کشید تا برنامه جواب ها را محاسبه کرد ولی در روش های دیگر این زمان را به میلی ثانیه می رسانیم.

 

الگوریتم و کد سوال برش میله (Rod cutting) با روش برنامه نویسی پویا از بالا به پایین (Dynamic programming Top Down)

 

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

در الگوریتم برنامه نویسی پویا با روش بالا به پایین دقیقا همان کار الگوریتم بازگشتی را انجام می دهیم با این تفاوت که مقادیر تابع را در هر بار محاسبه در یک لیست یا hash table نگه می داریم تا بار بعدی که همان مقدار نیازمان شد دوباره حسابش نکنیم.

در تابع زیر سوال برش میله را با الگوریتم برنامه نویسی پویا با روش بالا به پایین حل کرده ایم:

وکتور remember همان ساختمان داده این است که مقادیر بدست آورده را در آن ذخیره می کنیم تا دوباره استفاده کنیم

، بقیه ی عملکردش هم دقیقا مثل روش قبلی است.

 

در زیر هم کد کلی برنامه را همراه main می بینید که بیشترین هزینه ی موجود را برای میله هایی با طول صفر تا ۹۹۹ حساب می کند.

 

 

در تصویر زیر جواب را برای میله هایی با طول ۰ تا ۲۱ مشاهده می کنید و همان طور که می بینید ۰ ثانیه طول کشیده است یعنی برنامه در چند میلی ثانیه تمام شده است در حالی که در روش قبل ۳۱ ثانیه طول کشیده بود.

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

 

ولی برای این که سرعت این روش را با روش بعدی اندازه بگیریم برنامه را برای میله هایی با طول ۰ تا ۹۹۹ اجرا کردم که در زیر نتایج آن را می بینید – زمان اجرایی برنامه ۱۱۲ ثانیه شد.

 

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

 

الگوریتم و کد سوال برش میله ( Rod cutting ) با روش برنامه نویسی پویا از پایین به بالا ( Dynamic programming Bottom Up )

 

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

برای فهمیدن کارکرد این الگوریتم به مراحل زیر توجه کنید:

برای به دست آوردن هزینه ی میله ای به طول ۱ به میله های دیگر نیاز نداریم چون میله ای به طول یک را نمی شود برش داد.

برای به دست آوردن هزینه ی میله ای به طول ۲ به بیشترین هزینه ممکن برای میله ای به طول یک نیاز داریم چون میله به طول دو را می توان برش نداد یا به میله هایی به طول یک برش داد ، ولی در مرحله ی قبل هزینه ی میله ای به طول ۱ را حساب کرده ایم.

برای بدست آوردن هزینه ی میله ای به طول ۳ بهبیشترین هزینه ممکن برای میله هایی به طول یک و دو نیار داریم ولی در مراحل قبل آن ها را به دست آورده ایم .

به همین ترتیب تا آخر.

در شکل زیر گراف ایده ی بالا را می بینید:

 

 

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

 

 

تابع زیر بیشترین سود ممکن را با الگوریتم برنامه نویسی پویا با روش پایین به بالا تولید می کند:

 

 

p وکتور قیمت هر برش است و n طول میله است. در زیر هم کد کلی برنامه را می بینید که بیشترین سود را برای میله هایی با اندازه ی ۰ تا ۹۹۹ را حساب کرده ایم

 

 

خروجی برنامه را در تصویر زیر می بینید ، در روش قبل برای همین ورودی برنامه ۱۱۲ ثانیه زمان برده بود در حالی که این روش ۲۱ ثانیه زمان می برد. ممکن است این سوال پیش بیاید  هر دو روش تکراری ها را حساب نمی کنند پس چرا دومی بسیار سریع تر است ؟ دلیلش این است در روش قبل چک می کرد آیا مقدار مورد نظر قبلا حساب شده است یا نه و همین طور تابع به صورت بازگشتی بود وقتی یک تابع فراخوانده می شود در call Stack آن تابع و تمام ورودی هایش کپی می شود به همین دلیل زمان بیشتری می برد در حالی که در دومی ساختار بازگشتی نداریم و مرتب یک تابع فراخوانده نمی شود و همین طور مطمین هستیم مقدار قبلی وجود دارد در حالی که در روش بالا به پایین چک می کردیم وجود دارد یا نه.

 

حل سوال برش میله با سه روش مختلف به زبان سی پلاس پلاس

 

 

 

هزینه ی سه الگوریتم :

 

الگوریتم بازگشتی اول هزنینه اش از مرتبه ی (O( 2 ^ n  است.

دو الگوریتم بعدی هزینه ی یکسانی دارند و هزینه آن ها از مرتبه ی  ( O( n ^ 2  است.

 

۴ نظر

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *