الگوریتم بُرش چوب (Rod cutting ):
سلام . ظاهرا سوال شما در باره ی مساله ی بُرش چوب (Rod cutting ) است که یکی از سوال های کنکور ارشد مهندسی کامپیوتر سال 87 هم بوده . آدرسی که دوست شریف مون آقای "پسر ایرونی" دادن زیاد مربوط به این مساله نیست .
صورت مساله اینه :
فرض کنید نقش یه چوب بُر رو دارین . شما الوارهایی رو با متراژ زیاد (مثلا چهار متری ) از عمده فروشی خریداری می فرمائید و از اونجایی که مشتری های شما چوب ها رو با قطعه های کوچیکتر نیاز دارن پس شما باید الوار چهارمتری رو به قطعات کوچکتر تقسیم کنید . اما هر قطعه ای یک قیمت خاصی برای خودش داره مثلا قطعه ی یک متری یک دلار به فروش میره .قیمت دو متری سه دلار و ...
متراژ |
1 |
2 |
3 |
4 |
قیمت |
1 |
3 |
5 |
7 |
حالا مساله این است که شما قطعات چهار متری خود رو به چه اندازه هایی تقسیم کنید تا از فروش شون بیشترین سود رو بکنید .
پاسخ :
اگه تمام حالات ممکن رو برای برش دادن یک الوار چهار متری در نظر بگیریم 3^2 حالت وجود خواهد داشت . (2n-1 حالت با فرض کوچکترین قطعه = 1 متر) با هم حالت های موجود رو می بینیم :
{1+1+1+1}
{1+2+1}
{1+1+2}
{2+1+1}
{1+3}
{3+1}
{2+2}
{4}
خب حالت بهینه یکی از این حالت ها خواهد بود . در حالت عادی برای بدست آوردن 2n-1 حالت موجود و مقایسه ی تک تک اونا با هم با یه تابع با مرتبه ی زمانی نمایی روبرو خواهیم بود . اما یکی از راهکار های بهینه کردن این مساله استفاده از تابع های بازگشتی است . برای شروع باید تابع بازگشتی برای مساله تعریف کنیم و بعد الگوریتم بازگشتی مساله رو بنویسیم . ابتدا یک آرایه به نامp (اول کلمه ی priceبه معنی قیمت) انتخاب می کنیم . این آرایه قراره قیمت قطعه های برش خورده رو توی خودش جا بده . یعنیp[i] قیمت قطعه ایست که به متراژ i برش خورده است .فرض می کنیم که اولین برش روی الوار ما در نقطه ی i انجام میشه .پس الوار ما به دو قطعه ی i و n-i تقسیم شده است . پس سود حاصل از برش i برابر خواهد بود با Pi یا همان p[i] . برای اینکه این برش ( و به همراه آن سایر برش ها ) ما رو به بیشترین سود برسونه ، باید قسمت دیگر الوار را که n-i متر طول دارد را نیز به صورت بهینه برش دهیم . چون ما نمی دونیم که این متراژ چقدر است یا چگونه باید برش بخورد آن را به تابعی بنام r واگذار می کنیم . بنابر این داریم :
ri = یک برش بهینه به اندازه ی i متر
rn-i = سایر برش هایی که میشود در n-i متر تعبیه کرد تا به بهینگی برسیم .
بنابراین با اولین برش در نقطه ی i خواهیم داشت :
rn = Max (Pi+rn-i) , 1<=i<=n
حالا به یکی از سه روش "تقسیم و غلبه ، برنامه نویسی پویا از بالا به پائین و برنامه نویسی پویا از پائین به بالا " می تونیم الگوریتم لازم رو بنویسیم . من توی این جواب کوتاه ترین الگوریت مرو که پویای از پائین به بالاست رو مطرح می کنم :
CutRod(p,n)
{
int [] r = new int [] {0..n};
r[0]=0;
for (int j = 1 ; j<=n ; j++)
{
q = - infinity;
for ( int i = 1 ; i <=j; i ++ )
q = max (q,p[i]+r[j-i];
r[j] = q;
}
return r[n];
}
مرتبه ی زمانی این الگوریتم مثل هم نوع بالا به پائینش n2 است در حالی که در رو مستقیم یا در روش تقسیم و غلبه یک مرتبه ی نمایی منتظر ما بود .