الگوریتم چوب بری ( کارگاه چوب )

[Alamat Soal]

سلام.
می خواستم اطلاعاتی در مورد الگوریتم چوب بری (بعضی ها میگن کارگاه چوب ) داشته باشم.
تو یه تستی اسمشو دیدم. علاقه مند شدم در موردش بیشتر بدونم. تو کتاب یا اینترنت مقاله ای پیدا نکردم.
معادل انگلیسیش رو هم نمی دونستم که بخوام انگلیسی سرچ کنم.:خجالت:
اگه کسی اطلاعاتی داره، ممنون میشم که بهم کمک کنه.
مرسی از همتون:لبخندساده:

[Alamat Soal]

خودم فهمیدم صورت مساله چیه.
میگه یک قطعه چوب به طول L داده شده . می خواهیم این چوب را از مختصات های x1 تاXn (X1<x2<.....Xn ) نسبت به ابتدای چوب از سمت چپ ببریم. برای این کار باید n بار یک قطعه چوب که در ابتدا همان قطعه چوب اصلی است را برداریم و در ماشین قرار دهیم و از نقطه ای ببریم و آن را به دو قطعه کوچک تر تقسیم کنیم.
می دانیم که هزینه برش قطعه چوبی به طول k برابر k است (هزینه بستگی به طول داره )
به چه ترتیب ما چوب اصلی را از نقاط داده شده ببریم تا مجموع هزینه برش ها کمینه شود؟
( اینکه دفع اول از X4ببریم یا مثلا از X2 دست خودمونه)
روش که فکر کردم دیدم تقریبا شبیه فروشنده دوره گرده .چون گفته کمینه بشه هم باید از برنامه نویسی پویا استفاده کنیم.
تا اینجاشو فهمیدم خودم. ولی بازم نیاز به کمک دارم. کسی میدونه چیزی در رابطه با این مطلب؟

[pesar irooni]

دوست عزیر به این سوال کاربردی که یکی از دوستان پرسیده بود یه نگاهی بنداز.(جوابهایی هم که من دادم ببین، از همون تست کنکور الهام گرفته)
http://www.barnamenevis.org/forum/showthread.php?t=156825

[usider]

الگوریتم بُرش چوب (Rod cutting ):

سلام . ظاهرا سوال شما در باره ی مساله ی بُرش چوب (Rod cutting ) است که یکی از سوال های کنکور ارشد مهندسی کامپیوتر سال 87 هم بوده . آدرسی که دوست شریف مون آقای "پسر ایرونی" دادن زیاد مربوط به این مساله نیست .
صورت مساله اینه :
فرض کنید نقش یه چوب بُر رو دارین . شما الوارهایی رو با متراژ زیاد (مثلا چهار متری ) از عمده فروشی خریداری می فرمائید و از اونجایی که مشتری های شما چوب ها رو با قطعه های کوچیکتر نیاز دارن پس شما باید الوار چهارمتری رو به قطعات کوچکتر تقسیم کنید . اما هر قطعه ای یک قیمت خاصی برای خودش داره مثلا قطعه ی یک متری یک دلار به فروش میره .قیمت دو متری سه دلار و ...

[usider]

الگوریتم بُرش چوب (Rod cutting ):

سلام . ظاهرا سوال شما در باره ی مساله ی بُرش چوب (Rod cutting ) است که یکی از سوال های کنکور ارشد مهندسی کامپیوتر سال 87 هم بوده . آدرسی که دوست شریف مون آقای "پسر ایرونی" دادن زیاد مربوط به این مساله نیست .
صورت مساله اینه :
فرض کنید نقش یه چوب بُر رو دارین . شما الوارهایی رو با متراژ زیاد (مثلا چهار متری ) از عمده فروشی خریداری می فرمائید و از اونجایی که مشتری های شما چوب ها رو با قطعه های کوچیکتر نیاز دارن پس شما باید الوار چهارمتری رو به قطعات کوچکتر تقسیم کنید . اما هر قطعه ای یک قیمت خاصی برای خودش داره مثلا قطعه ی یک متری یک دلار به فروش میره .قیمت دو متری سه دلار و ...

[usider]

وااااااااااای


من دیگه غلط بکنم بیام توی این سایت مزخرف

مدیرای این سایت از خودشون خجالت بکشن بخدا

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

حیف این همه کاربر . واقعا که

[usider]

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

[usider]

الگوریتم بُرش چوب (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 است در حالی که در رو مستقیم یا در روش تقسیم و غلبه یک مرتبه ی نمایی منتظر ما بود .

[usider]

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

این سایت برنامه نویسای ایرانه ؟

واقعا یه لحظه خجالت کشیدم از این که یه برنامه نویس ایرانی هستم