Printable View
سلام
نمی دونم جای این سوال تو این مبحث هست یا نه؟
ولی می خواستم بدونم اینکه آیا کسی می دونه من چطوری می تونم تو dot net یه برنامه بنویسم که بتونم برای برش لوله ها در طول های متفاوت یه مقدار بهینه با کمترین پرت رو بدست بیارم؟
آیا راهی وجود داره یا باید کلیه احتمال های مختلف رو امتحان کرد
MErC
Michka
سوالت شبیه سوال 34 طراحی الگوریتم کنکور کارشناسی ارشد پارساله (سال 87).
به نظر من جواب این سوال از نوع برنامه سازی پویا (dynamic programming) بدست میاد.
با فرمولی شبیه اینF(n,L) = min{F(n-1,L-Li) where 1<i<n}
اما بعید میدونم بشه تو زمان چند جمله ای حلش کرد و این یه مساله NP Complete هستش با زمان نمایی. (شبیه مساله فروشنده دوره گرد)
اما اگه بتونی یه سرچ با مضمون dynamic programming تو نت کنی حتما جوابای بهتری بدست میاری.
سلام پسر ایرونی
از راهنماییت ممنون ولی من زیاد از حرفات سر در نیاوردم
لطفا میشه یه کم ساده تر بگی .
من می خوام یه برنامه بنویسم که به عنوان مثال از 20 شاخه میله گرد 6 متری که دارم و 39 قطعه میله گرد با طول های متفاوت را می خواهم از 20 شاخه اولیه برش بدم.
حالا سوال من اینه : چطور برش برم که کمترین پرت میله گرد رو داشته باشم.
MErC
Michka
دقیقا سوالت همونیه که متوجه شدم و مربوط به برنامه سازی پویاست. این مساله رو نمیشه تو زمان چند جمله ای حل کرد و حلش زمان بسیار زیادی میگیره. اگه وقت کردم حتما دقیق تر جوابت رو مینویسم.
سلام
من تونستم این الگوریتم رو با الگوریتم کوله پشتی معادل کنم.
ببین فرض میکنیم شما یک شاخه مثلا به طول 16 متر داری و سه تا قطعه به طولهای 9 و 4 و 6. بهترین برش برای این قطعه برش میله های 6 و 9 که کمترین هدر رفتگی رو به ما میده.
فرض کن L طول شاخه ، L1 و L2 و L3 و ... هم طولهای قطعه ها باشند. یعنی در این مثال :
L = 16
L1 = 9 , L2 = 4 , L3 = 6
یک تابع بازگشتی تعریف میکنیم که هدفش مینیمم کردن مقدار پرتی میباشه که الهام گرفته از برنامه سازی پویا و خصوصا مساله کوله پشتی 0 و 1 :
F(n,L) = min {F(n-1,L) , F(n-1 ,L-Ln)}
و نقاط مرزیه:
F(0,K) = K
F(0,-K) = infinite
یعنی هنگامی که میخوایم میله n ام رو تست کنیم دو حالت داریم. یا میله n ام رو انتخاب نمیکنیم و ادامه مساله رو با (F(n-1,L حل میکنیم یا اینکه میله n ام رو انتخاب میکنیم و ادامه مساله رو با (F(n-1,L-Ln حل میکنیم و در آخر بین این دو تا کوچیکتر رو انتخاب میکنیم.
حالا مثالمون رو با این فرمول به صورت بازگشتی حل میکنیم
F(3,16) = min {F(2,16) , F(2,10) [L3]}
F(2,16) = min {F(1,16) , F(1,12) [L2]}
F(2,10) = min {F(1,10) , F(1,6) [L2]}
F(1,16) = min {F(0,16) , F(0,7) [L1]}
F(1,12) = min {F(0,12) , F(0,3) [L1]}
F(1,10) = min {F(0,10) , F(0,1) [L1]}
F(1,6) = min {F(0,6) , F(0,-3) [L1]}
F(0,16) = 16
F(0,7) = 7
F(0,12) = 12
F(0,3) = 3
F(0,10) = 10
F(0,1) = 1
F(0, 6) = 6
F(0,-3) = infinite // hamoon binahayate khodemoon ya masalan 1000
حالا که به نقاط پایانی رسیدیم یعنی دیگه قطعه ای برای تست نبود او نا تو فرمولامون جایگذاری میکنیم
توجه کن که اون توابعی که عدد کوچیکه سمت راسته میلش هم انتخاب میشه که جلوی // نوشتم
F(1,16) = min {F(0,16) , F(0,7) [L1]} = min {16 , 7} = 7 // L1
F(1,12) = min {F(0,12) , F(0,3) [L1]} = min {12 , 3} = 3 // L1
F(1,10) = min {F(0,10) , F(0,1) [L1]} = min {10 , 1} = 1 // L1
F(1,6) = min {F(0,6) , F(0,-3) [L1]} = min { 6 , 1000} = 6 // nothing
حالا مرحله بعد
F(2,16) = min {F(1,16) , F(1,12) [L2]} = min {7 , 3} = 3 // L1 + L2
F(2,10) = min {F(1,10) , F(1,6) [L2]} = min {1 , 6} = 1 // L1 + nothing
و در آخر جواب مساله بدست میاد:
F(3,16) = min {F(2,16) , F(2,10) [L3]} = min {3 , 1} = 1 // L1 + nothing + L3
یعنی با هدر رفتگی 1 و انتخاب میله های 1 و 3
این فقط برای یک شاخه بود. همونطور که قبلا گفتم زمان این مساله نمایی که در اینجا داریم (O(2^n یعنی برای 1 شاخه و سه تا قطعه 1+3^2 یعنی 16 بار تابع رو فراخوانی کردیم. حالا اگه بخوایم چند تا شاخه رو حساب کنیم دو راه به ذهن من رسید
راه اصلی استفاده از حالت چند بعدیه مثلا اگه سه تا شاخه داشته باشیم به طولهای L و K و M و n تا قطعه فرمولی به شکل (F(n,L,K,M رو باید حل کنیم که زمان باز کشتی اون (O(8^n رو داره که سر به فضا میزنه. البته 100% جواب درست رو میده.
راه دوم اینه که با همون فرمول اولی (یک بعدی) حل کنیم و بعد از تموم شدن اولین شاخه همون کار رو با یه شاخه دیگه و قطعه های باقیمونده انجام بدیم که من تست کردم جواب بهینه رو داد. یعنی نتونستم مثال نقضی ارائه کنم که با این روش دوم جواب بهینه نده.
اما اگه بتونی یه کم بیخیال پرتی و این جور حرفها بشی زمان اجرات سریعتر میشه. یعنی سعی کنی برای هر شاخه تعداد قطعه های کمتری رو تست کنی تا سریعتر حل بشه
تا اینجای کار شما برای انتخاب اولین شاخه باید تعداد اجرای تابع معادل 39^2 رو متحمل بشی (میتونی بزنی ماشین حساب ببینی چقدر میشه(حدود 550 میلیارد))
تازه این برای اولیشه. برای بقیش هم باید همین حدود (البته هر مرحله کمتر میشه) رو متحمل بشی.
امیدوارم فکر نکنی این راه با تست کردن یکیه. چون تست کردن زمان فاکتوریلی میخواد. یعنی برای اولین میله !39 حالت برای تست داری که یه رقم مافوق فضایی میشه (من نتونستم عددش رو بخونم (یه 2 با 46 تا صفر جلوش) اونم فقط برای اولین میله)
امیدوارم بتونی تو پروژه ات ازش استفاده کنی!!!
البته این چیزی بود که به ذهن من رسید. اگه بتونی یه روش حریصانه یا شبه حریصانه واسه این مساله پیدا کنند اونوقت با 39 بار اجرا حل میشه!!!(بعید میدونم)
سلام پسر ایرونی
از کمکت ممنونم ، یه راهی هم تو ذهن منه ، فک می کنم شبیه مال تو باشه ، بیایم از بین تیکه ها و با مقایسه کمترین پرتی شروع به برش کنیم و گذینه ها رو حذف کنیم. این باعث میشه وقتی جلوتر میریم دایره امتحان کردن ما کمتر میشه
MerC
Michka
این الگوریتمی که نوشتم نگاه نکن طولانیه. کدش 4 خطه. اگه خواستی برات مینویسم.
من نفهمیدم منظورت چیه ؟ چطوری میخوای کمترین پرتی رو پیدا کنی که بخوای از اون شروع کنی. امیدوارم منظورت مقایسه بصورت تک تک نباشه؟؟!!
سلام
من راستیتش زیاد سر در نیاوردم ولی یه حسابایی پیش خودم کردم به این صورت که
اول بیام دو تا یا سه تا تیکه رو با هم جمع کنیم تا جایی که از طول میله ما کمتر باشه و پرت کمتری داشته باشه ، حالا بریم سر شاخه بعدی ، و یکی یکی شاخه ها رو کم کنیم . به این صورت هرچه جلوتر می ریم تعداد محاسبات هم کم میشه.
تو مثال شما از جمع گذینه ها به اعداد زیر می رسیم :
15 و 13 و 10
که با مقایسه این اعداد و طول میله (16) گذینه اول قبول و حذف میشه و میریم سراغ شاخه بعدی و الی آخر
اوووووووووووووووووووه:عصب نی++:
متاسفانه شما داری همون راه تست رو که گفتم زمانی فاکتوریلی داره بکار میبری. این روشی که میگی هرچی تعداد قطعاتت بیشتر بشه محاسباتش سر به فلک میزاره. سعی کن (یعنی حتما) از برنامه سازی پویا که از مباحث مهم تو علم طراحی الگوریتمه استفاده کنی.
من سعی میکنیم در اسرع وقت کدش رو برات بزارم تا ببینی چقدر راحته.
مرسی
ممنون میشم.
Michka
به زبان C# و تو console app برنامش رو برات نوشتم
کل الگوریتم تابع GetLessWaste هست.
البته این برنامه فقط کمترین مقدار هدر رفتگی رو میده. اگه وقت کردم برات جوابایی که این مقدار از اونا به دست میاد رو هم مینویسم
class Program
{
static ArrayList lenght = new ArrayList();
static int GetLessWaste(int n, int cylinder)
{
if (n == 0)
{
if (cylinder < 0)
return 1000;
else
return cylinder;
}
else
{
return Math.Min(GetLessWaste(n - 1, cylinder), GetLessWaste(n - 1, cylinder - (int)lenght[n - 1]));
}
}
static void Main(string[] args)
{
lenght.Add(9); lenght.Add(4); lenght.Add(6);
Console.WriteLine(GetLessWaste(lenght.Count, 16));
Console.ReadLine();
}
}
سعی کن با مقادیر مختلف چک کنی تا ببینی جوابش حتما درسته.
سلام
اینم برنامه ای که مساله شما رو با راه حلش نشون میده.
من یه کلاس ساختم بنام Snip که تمام کارا تو اون انجام میشه.
متد GetLessWaste کمترین مقدار هدر رفتگی رو نشون میده.
متد GetSolution جواب رو بصورت آرایه برمیگردونه. یعنی میگه چه قطعه هایی باید استفاده کنی تا کمتریم مقدار هدر رفتگی رو داشته باشی.
class Snip
{
private ArrayList lenght = new ArrayList();
private ArrayList selectedSlices = new ArrayList();
public Snip()
{
//--------------------------------------
//Create Array List, add some numbers
//--------------------------------------
Random rnd = new Random();
for (int i = 0; i < 10; i++)
lenght.Add(rnd.Next(100));
}
public Snip(ArrayList SegmentLenghts)
{
lenght = SegmentLenghts;
}
public int GetLessWaste(int n, int cylinder)
{
if (n == 0)
{
if (cylinder < 0)
return 1000;
else
return cylinder;
}
else
{
return Math.Min(GetLessWaste(n - 1, cylinder),GetLessWaste(n - 1, cylinder - (int)lenght[n - 1]));
}
}
public ArrayList GetSolution(int n, int cylinder)
{
int lessWaste = GetLessWaste(n,cylinder);
for (int i=n; i>0;i--)
{
if (lessWaste == GetLessWaste(i - 1, cylinder - (int)lenght[i - 1]))
{
selectedSlices.Add(lenght[i - 1]);
cylinder -= (int)lenght[i - 1];
}
}
return selectedSlices;
}
}
اینم که main برنامست که من قطعاتمون رو که اندازه های مختلفی داره در قالب آرایه lenght و اندازه لوله مون که قراره بریده بشه در قالب cylinder به متدهای کلاس Snip فرستادم.
static void Main(string[] args)
{
ArrayList lenght = new ArrayList();
int cylinder =44;
lenght.Add(9); lenght.Add(4); lenght.Add(6); lenght.Add(10); lenght.Add(12);
Snip s = new Snip(lenght);
Console.WriteLine("minimum waste for this problem is "+s.GetLessWaste(lenght.Count, cylinder));
Console.WriteLine("and the selected slices are :");
foreach (int i in s.GetSolution(lenght.Count, cylinder))
Console.Write(i + "\t");
Console.ReadLine();
}
با مقادیر مختلف امتحان کن و جوابت رو بگیر.
سلام
مرسی از کمکت واقعا دستت درد نکنه.
من زیاد C نیستم ولی از رو این کد ها برا خودم کد های VB شو می نویسم. واقعا ممنونم.
mERc
Michka
حقیقتش من وقت نکردم جواب برو بچ رو بخونم و از درست و غلط بودنشون اطلاعی ندارم.
من نفهمیدم هدف کمینه کردن تعداد میله‌گردهاست یا کمینه کردن میله‌های پرت شده. به نظر مساله کمینه کردن تعداد میله‌گردها واقعی تر میاد. چون ما میریم میگیم فلان تا میله گرد میخوایم. در این صورت جواب این مساله به صورت دقیق در اُردر چند جمله‌ای به دست نمیاد. ولی یه الگوریتم تقریبی با اُردر nlgn هست که ضریب تقریبش 2 هست.
اگه تعداد بعدها بيشتر از يك باشه روش حل به چه صورت ميشه ؟
روش حل همون برنامه سازی پویاست. فقط زمان اجراتون خیلی بالاتر میره.
نقل قول:
راه اصلی استفاده از حالت چند بعدیه مثلا اگه سه تا شاخه داشته باشیم به طولهای L و K و M و n تا قطعه فرمولی به شکل (F(n,L,K,M رو باید حل کنیم که زمان باز کشتی اون (O(8^n رو داره که سر به فضا میزنه. البته 100% جواب درست رو میده.
فرض كنيد 200 قطعه با طولهاي مختلف مثلا 2 و 3 و 5 و 7 متري داريم (از هر طول به تعداد مختلف)
مي تونيم بگيم
12=7+5
و يا بگيم
12=7+3+2
و يا بگيم
12=3+2+3+2+2
و اونقدر قطعه هاي مختلف رو با هم بچينيم (يطوريكه جمع طولشون 12 متر بشه) كه ديگه جمع طول قطعه هاي باقيمانده كمتر از 12 متر باشه
مي خوايم روشي پيدا كنيم كه بهترين انتخابها رو كنار هم بچينه و كمترين باقيمانده رو در انتها داشته باشيم
الگوريتم خاصي به نظرتون ميرسه ؟ فكر مي كنم الگوريتمي كه قبلا گفتين تو اين روش كار نكنه.
چرا ؟؟ جفتشون یه چیز میگن. الگوریتم شما هم عین همون قبلیه است. با این فرض که سیلندر 12 متر هست. قطعه ها هم که حالا با طولهای دیگه. فرقش اینه که تو هر مرحله به جز آخرین مرحله مقدار هدر رفتگی 0 هست.
حالا با این فرض من فکر کنم روش حریصانه هم برای شما جواب میده که بسیار بسیار سریعتر از برنامه سازی پویاست. یعنی شما تو هر مرحله میای بزرگترین عنصر رو انتخاب میکنی(7) و بعد بازم 7 رو انتخاب میکنی که میبینی بیشتر از 12 میشه. میری سراغ بعدی و 5 رو انتخاب میکنی و یه مرحله ات تموم میشه.
مرحله بعد بازم از بزرگترین استفاده میکنی و به همین ترتیب. از اونجایی که عناصر بزرگتر انتخاب میشند و در آخر کار شانس باقی موندن عناصر کوچکتر (در اینجا 2) بیشتر از بقیه ست، پس حتما مقدار باقیمونده کمترین مقداره.
((( البته با این فرض که عناصر شما دارای مجموعی هستند که برابر 12 حتما خواهند شد)))