نمایش نتایج 1 تا 18 از 18

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

  1. #1

    اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام
    نمی دونم جای این سوال تو این مبحث هست یا نه؟
    ولی می خواستم بدونم اینکه آیا کسی می دونه من چطوری می تونم تو dot net یه برنامه بنویسم که بتونم برای برش لوله ها در طول های متفاوت یه مقدار بهینه با کمترین پرت رو بدست بیارم؟
    آیا راهی وجود داره یا باید کلیه احتمال های مختلف رو امتحان کرد

    MErC
    Michka

  2. #2
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سوالت شبیه سوال 34 طراحی الگوریتم کنکور کارشناسی ارشد پارساله (سال 87).
    به نظر من جواب این سوال از نوع برنامه سازی پویا (dynamic programming) بدست میاد.
    با فرمولی شبیه این
    F(n,L) = min{F(n-1,L-Li) where 1<i<n}

    اما بعید میدونم بشه تو زمان چند جمله ای حلش کرد و این یه مساله NP Complete هستش با زمان نمایی. (شبیه مساله فروشنده دوره گرد)
    اما اگه بتونی یه سرچ با مضمون dynamic programming تو نت کنی حتما جوابای بهتری بدست میاری.

  3. #3

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام پسر ایرونی
    از راهنماییت ممنون ولی من زیاد از حرفات سر در نیاوردم
    لطفا میشه یه کم ساده تر بگی .
    من می خوام یه برنامه بنویسم که به عنوان مثال از 20 شاخه میله گرد 6 متری که دارم و 39 قطعه میله گرد با طول های متفاوت را می خواهم از 20 شاخه اولیه برش بدم.
    حالا سوال من اینه : چطور برش برم که کمترین پرت میله گرد رو داشته باشم.

    MErC
    Michka

  4. #4
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

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

  5. #5
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام
    من تونستم این الگوریتم رو با الگوریتم کوله پشتی معادل کنم.
    ببین فرض میکنیم شما یک شاخه مثلا به طول 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 بار اجرا حل میشه!!!(بعید میدونم)
    آخرین ویرایش به وسیله pesar irooni : چهارشنبه 09 اردیبهشت 1388 در 10:45 صبح

  6. #6

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام پسر ایرونی

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

    MerC
    Michka

  7. #7
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

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

  8. #8

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام
    من راستیتش زیاد سر در نیاوردم ولی یه حسابایی پیش خودم کردم به این صورت که
    اول بیام دو تا یا سه تا تیکه رو با هم جمع کنیم تا جایی که از طول میله ما کمتر باشه و پرت کمتری داشته باشه ، حالا بریم سر شاخه بعدی ، و یکی یکی شاخه ها رو کم کنیم . به این صورت هرچه جلوتر می ریم تعداد محاسبات هم کم میشه.
    تو مثال شما از جمع گذینه ها به اعداد زیر می رسیم :
    15 و 13 و 10
    که با مقایسه این اعداد و طول میله (16) گذینه اول قبول و حذف میشه و میریم سراغ شاخه بعدی و الی آخر

  9. #9
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    اوووووووووووووووووووه
    متاسفانه شما داری همون راه تست رو که گفتم زمانی فاکتوریلی داره بکار میبری. این روشی که میگی هرچی تعداد قطعاتت بیشتر بشه محاسباتش سر به فلک میزاره. سعی کن (یعنی حتما) از برنامه سازی پویا که از مباحث مهم تو علم طراحی الگوریتمه استفاده کنی.
    من سعی میکنیم در اسرع وقت کدش رو برات بزارم تا ببینی چقدر راحته.

  10. #10

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    مرسی
    ممنون میشم.

    Michka

  11. #11
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    به زبان 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();
    }
    }

    سعی کن با مقادیر مختلف چک کنی تا ببینی جوابش حتما درسته.
    آخرین ویرایش به وسیله pesar irooni : سه شنبه 15 اردیبهشت 1388 در 02:56 صبح

  12. #12
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام
    اینم برنامه ای که مساله شما رو با راه حلش نشون میده.
    من یه کلاس ساختم بنام 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();
    }


    با مقادیر مختلف امتحان کن و جوابت رو بگیر.
    آخرین ویرایش به وسیله pesar irooni : سه شنبه 15 اردیبهشت 1388 در 16:47 عصر

  13. #13

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    سلام
    مرسی از کمکت واقعا دستت درد نکنه.
    من زیاد C نیستم ولی از رو این کد ها برا خودم کد های VB شو می نویسم. واقعا ممنونم.

    mERc
    Michka

  14. #14
    کاربر تازه وارد
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    سن
    34
    پست
    32

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    حقیقتش من وقت نکردم جواب برو بچ رو بخونم و از درست و غلط بودنشون اطلاعی ندارم.
    من نفهمیدم هدف کمینه کردن تعداد میله‌گردهاست یا کمینه کردن میله‌های پرت شده. به نظر مساله کمینه کردن تعداد میله‌گردها واقعی تر میاد. چون ما میریم میگیم فلان تا میله گرد میخوایم. در این صورت جواب این مساله به صورت دقیق در اُردر چند جمله‌ای به دست نمیاد. ولی یه الگوریتم تقریبی با اُردر nlgn هست که ضریب تقریبش 2 هست.

  15. #15
    کاربر دائمی آواتار Sharif Lotfi
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Tehran
    سن
    50
    پست
    285

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    اگه تعداد بعدها بيشتر از يك باشه روش حل به چه صورت ميشه ؟

  16. #16
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    روش حل همون برنامه سازی پویاست. فقط زمان اجراتون خیلی بالاتر میره.
    راه اصلی استفاده از حالت چند بعدیه مثلا اگه سه تا شاخه داشته باشیم به طولهای L و K و M و n تا قطعه فرمولی به شکل (F(n,L,K,M رو باید حل کنیم که زمان باز کشتی اون (O(8^n رو داره که سر به فضا میزنه. البته 100% جواب درست رو میده.

  17. #17
    کاربر دائمی آواتار Sharif Lotfi
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Tehran
    سن
    50
    پست
    285

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    فرض كنيد 200 قطعه با طولهاي مختلف مثلا 2 و 3 و 5 و 7 متري داريم (از هر طول به تعداد مختلف)
    مي تونيم بگيم
    12=7+5
    و يا بگيم
    12=7+3+2
    و يا بگيم
    12=3+2+3+2+2
    و اونقدر قطعه هاي مختلف رو با هم بچينيم (يطوريكه جمع طولشون 12 متر بشه) كه ديگه جمع طول قطعه هاي باقيمانده كمتر از 12 متر باشه
    مي خوايم روشي پيدا كنيم كه بهترين انتخابها رو كنار هم بچينه و كمترين باقيمانده رو در انتها داشته باشيم
    الگوريتم خاصي به نظرتون ميرسه ؟ فكر مي كنم الگوريتمي كه قبلا گفتين تو اين روش كار نكنه.

  18. #18
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: اگلوریتم بهینه سازی برش طولی ( 1 بعدی )

    چرا ؟؟ جفتشون یه چیز میگن. الگوریتم شما هم عین همون قبلیه است. با این فرض که سیلندر 12 متر هست. قطعه ها هم که حالا با طولهای دیگه. فرقش اینه که تو هر مرحله به جز آخرین مرحله مقدار هدر رفتگی 0 هست.
    حالا با این فرض من فکر کنم روش حریصانه هم برای شما جواب میده که بسیار بسیار سریعتر از برنامه سازی پویاست. یعنی شما تو هر مرحله میای بزرگترین عنصر رو انتخاب میکنی(7) و بعد بازم 7 رو انتخاب میکنی که میبینی بیشتر از 12 میشه. میری سراغ بعدی و 5 رو انتخاب میکنی و یه مرحله ات تموم میشه.
    مرحله بعد بازم از بزرگترین استفاده میکنی و به همین ترتیب. از اونجایی که عناصر بزرگتر انتخاب میشند و در آخر کار شانس باقی موندن عناصر کوچکتر (در اینجا 2) بیشتر از بقیه ست، پس حتما مقدار باقیمونده کمترین مقداره.
    ((( البته با این فرض که عناصر شما دارای مجموعی هستند که برابر 12 حتما خواهند شد)))

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •