حل سوال Rod Cutting با سه روش مختلف

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

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

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

 

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

 

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

 

۱۰

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

قمیت

 

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

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

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

 

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

 

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

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

state tree

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

 

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

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

 

 

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

 

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

recursive

 

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

 

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

 

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

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

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

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

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

 

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

 

 

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

rod cuting - DP Top Down

 

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

 

rod cuting - DP Top Down 2

 

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

 

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

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

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

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

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

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

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

 

 

dynamic programming

 

 

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

 

 

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

 

 

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

 

rod cuting - DP Down Top 2

 

 

 

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

 

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

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

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۴ comments

Leave a Reply

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